http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=178.178.21.24&* 2026-05-20T09:08:29Z Вклад участника MediaWiki 1.30.0 http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D1%82%D0%B5%D0%BA&diff=22716 2012-05-24T19:43:45Z

<p>178.178.21.24: Отмена правки 22715 участника Yurik (обсуждение)</p> <hr /> <div>{{Определение<br /> |definition=Персистентными структурами данных называются такие структуры, что при всяком их изменении остается доступ ко всем предыдущим версиям этой структуры.<br /> }}<br /> <br /> Рассмотрим такую структуру на примере стека.<br /> <br /> <br /> == Наивная реализация ==<br /> <br /> Самое простое и очевидное решение этой задачи — честное копирование стека при каждой операции. &lt;br&gt;<br /> Очевидно, что это не самое эффективное решение. Сложность одной операции составляет &lt;tex&gt;O(n)&lt;/tex&gt; и количество требуемой памяти — &lt;tex&gt;O(n * n)&lt;/tex&gt;.<br /> <br /> == Эффективная реализация ==<br /> <br /> <br /> Попробуем решить задачу эффективнее. Заведем массив указателей, ссылающихся на каждую версию стека. <br /> <br /> Вместо n копий стека будем хранить n первых элементов. Тогда операции push и pop будут иметь следующий вид:&lt;br&gt;<br /> * &lt;tex&gt;push(x, i)&lt;/tex&gt; - создает новый элемент со значением x, который ссылается на элемент с номером i как на предыдущий элемент в стеке.<br /> * &lt;tex&gt;pop(i)&lt;/tex&gt; - возвращает значение, хранящееся в элементе с номером i и копирует элемент, предыдущий для него.<br /> Результирующие стеки будут иметь номер n + 1.<br /> <br /> <br /> <br /> == Пример ==<br /> <br /> Пусть изначально у нас есть один пустой стек. Для удобства, будем хранить его как «голову» с пометкой пустого стека:<br /> &lt;br&gt;<br /> [[Файл:B5bb212f3702e565498c4412e13242a7.jpg|Картинка]]&lt;br&gt;<br /> &lt;br&gt;<br /> &lt;br&gt;<br /> Далее выполним &lt;tex&gt;push(1, 5)&lt;/tex&gt;. Создается новая вершина со значением 5, ссылающаяся на 1-ую:<br /> &lt;br&gt;<br /> [[Файл:612b6fe1562242b3a455b2abb698dfc9.jpg|nothumb]]&lt;br&gt;<br /> &lt;br&gt;<br /> Аналогично выполним &lt;tex&gt;push(2, 10)&lt;/tex&gt; и &lt;tex&gt;push(1, 6)&lt;/tex&gt;:<br /> &lt;br&gt;&lt;br&gt;<br /> [[Файл:2beb71892fd79b675e095d5432827d03.jpg|nothumb]]<br /> &lt;br&gt;<br /> <br /> Очевидно, что все 4 стека сейчас верно построены и легко восстанавливаются. Давайте теперь попробуем выполнить последовательно операции &lt;tex&gt;pop(2)&lt;/tex&gt; и &lt;tex&gt;pop(3)&lt;/tex&gt;:<br /> <br /> &lt;br&gt;<br /> * &lt;tex&gt;pop(2)&lt;/tex&gt; возвращает 5 и копирует 1-ую вершину. Результирующий пятый стек — пустой.<br /> &lt;br&gt;<br /> [[Файл:3ab7456751529d76c5f1392d5d3b5fcb.jpg|nothumb]]<br /> <br /> &lt;br&gt;&lt;br&gt;<br /> <br /> * &lt;tex&gt;pop(3)&lt;/tex&gt; возвращает 10 и копирует 2-ую вершину: получаем шестой стек.<br /> &lt;br&gt;&lt;br&gt;<br /> [[Файл:Eced2ebbcee643d6c87576b0d3460785.jpg|nothumb]]&lt;br&gt;<br /> &lt;br&gt;<br /> <br /> В итоге мы имеем доступ ко всем версиям стека за &lt;tex&gt;O(1)&lt;/tex&gt; времени и &lt;tex&gt;O(n)&lt;/tex&gt; памяти (массив длины n и n самих &quot;стеков&quot;).<br /> <br /> == См. также==<br /> <br /> * [[Стек]]<br /> * [[Персистентный дек]]<br /> <br /> == Ссылки ==<br /> <br /> * [http://habrahabr.ru/blogs/algorithm/113585/ Персистентный стек - статья на хабре]<br /> <br /> [[Категория:Дискретная математика и алгоритмы]]<br /> <br /> [[Категория: Структуры данных ]]</div>

178.178.21.24