Изменения

[[Файл:ListABCD.jpg|250px|thumb|right|Для такого списка команда операция <tex>\mathrm{order(D,B)}</tex> выдаст <tex>\mathrm{false}</tex>.]]'''List order maintance''' (рус. <i>поддержание порядка в списке</i>) {{---}} проблема поддержки поддержания списка со следующими командамиоперациями:

* <tex>\mathrm{order(p, q)}</tex> {{---}} командаоперация, возвращающая <tex>\mathrm{true}</tex> , если <tex>p</tex> в списке находится до <tex>q</tex> и <tex>\mathrm{false}</tex> иначе.

Структура данных подходит Существует реализация такой структуры, где <tex>\mathrm{order(p, q)}</tex> выполняется за истинную <tex>O(1)</tex>, а операции добавления и для односвязныхудаления за амортизационную <tex>O(1)</tex>.Проблема поддержания порядка в списке возникает, и для двусвязных списковк примеру, при реализации [[Персистентные структуры данных|полностью персистентного дерева поиска]].

Рассмотрим реализацию списка с командой порядкаВсе операции, где все операции выполняются за амортизационную кроме <tex>O\mathrm{order(1p,q)</tex>. Дадим каждому элементу списка метки длины <tex>u</tex> из битов. Пусть <tex>u:\dfrac{n}{2}<2^u \leqslant 2n</tex>, где <tex>n</tex> - количество элементов в списке. Если после добавления или удаления элементов <tex>u</tex> перестанет удовлетворять неравенству, пересчитаем все метки заново. Пересчет меток занимает амортизационно за <tex>O(1)</tex> по аналогии может выполнить обычный [[Список|двусвязный список]], но с саморасширяющимся массивомего помощью невозможно получить информацию о порядке объектов. Пусть метки идут по возрастанию Для реализации этой операции каждому узлу можно сопоставить некоторое число так, чтобы все числа строго возрастали от начала к концу списка. Таким образом, тогда операцию эти числа, которые в дальнейшим будут называться <texb>\mathrm{order(p,q)}метками</texb> можно сделать, сравнив метки за <tex>O(1)</tex>. Теперь опишем взаимодействие с метками при выполнении других командзадают порядок на элементах списка.

Для выполнения Ответить на запрос <tex>\mathrm{removeorder(p,q)}</tex> можно за <tex>O(1)</tex>, просто удалим элемент сравнив метки <tex>p</tex> вместе с его меткой, проверим, удовлетворяет ли и <tex>q</tex>. Добавление меток никак не влияет на реализацию операции <tex>u\mathrm{remove(p)}</tex> неравенству, если нет - пересчитаем. Для Однако реализацию <tex>\mathrm{insert(p,q)}</tex> существуют два возможных случаяпотребуется изменить:при добавлении нового элемента <tex>q</tex> после узла <tex>p</tex>, узлу <tex>q</tex> необходимо присвоить метку, которая строго больше предыдущего элемента и строго меньше следующего. В какой-то момент возникнет ситуация, что новой метки не найдётся, тогда метки можно перераспределить среди элементов списка так, чтобы для узла <tex>q</tex> нашлась метка. Далее будет рассмотрен алгоритм, который позволяет эффективно реализовать эту идею.

Метка === Алгоритм за O(logn) ======= Способ хранения меток ====Метки будут храниться в виде чисел в двоичной системе счисления. Требуется выбрать такую длину для меток, чтобы перераспределения не случались слишком часто. Если <tex>ru</tex>: {{---}} длина каждой метки, то для начала пусть <tex>u:n<2^u \mathrm{r.label}>\mathrm{p.label} + 1leqslant 2n</tex>, где <tex>rn</tex> {{---}} следующий за количество элементов в списке. Если после добавления элементов какому-то элементу не хватит метки, увеличим <tex>u</tex> на <tex>1</tex> и пересчитаем все метки заново, распределив их равномерно. Заметим, что сразу после перераспределения меток, в среднем, между каждыми двумя элементами списка будет только одна свободная метка, так как при переходе к новому <tex>pu</tex> элемент количество меток будет примерно в спискедва раза больше количества элементов списка. Тогда между метками Если же после удаления элемента из списка <tex>p2^u</tex> и станет в <tex>r4</tex> есть свободная метка, которую мы дадим раза больше <tex>q:\mathrm{q.label} = \dfrac{\mathrm{p.label}+\mathrm{r.label}}{2}n</tex>. После этого опять проверим , уменьшим <tex>u</tex> на соответствие неравенству<tex>1</tex>.Пересчет меток занимает амортизационно <tex>O(1)</tex> по аналогии с [[Файл:UBitTreeListABCDДинамический массив | саморасширяющимся массивом]]. Однако очевидно, что в таком случае операция добавления за <tex>O(1)</tex> работать не будет, так как, если потребуется добавить между двумя элементами списка больше одного элемента, то новым элементам меток не хватит, и придется провести лишнее перераспределение меток, которое будет рассмотрено ниже.jpg|350px|thumb|right|Точка - метка Позже, в листе используетсядоказательстве времени работы, значение <tex>u</tex> будет несколько уточнено.]]

В случае, если между метками <tex>p</tex> и <tex>q</tex> свободной метки нет, нам придется пересчитать Все метки следующим образом. Построим виртуальное дерево отрезков над всеми возможными метками, где будут храниться в каждом узле будем хранить [[Сверхбыстрый цифровой бор | цифровом боре]] высоты <tex>1u</tex> бит. В листьях будем хранить(там представлены не только используемые метки, используется ли уже эта меткаа вообще все возможные заданной длины). Пусть Введем некоторые обозначения:* <tex>\mathrm{weight(x)}</tex> {{---}} это количество помеченных (используемых) листьев (меток) в поддереве узла <tex>x</tex>, а ;* <tex>\mathrm{size(x)}</tex> {{---}} это количество всех листьев в поддереве <tex>x</tex>. Для любой <tex>1<\alpha<2</tex> будем считать, что узел дерева переполнен, если ;* <tex>\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}>\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>. Именно наличие переполненности мы и будем хранить во всех нелистовых узлах. Стоит заметить, что все листья всегда непереполнены. В худшем случае: <tex> \dfrac{\mathrm{weight(leave)}}{\mathrm{size(leave)}} = 1 = \dfrac{1}{\alpha^{\mathrm{height(x)}}} = \dfrac{1}{\alpha^{0---}}высота узла </tex>. Получается, что чем выше, тем более разреженными должны быть поддеревья непереполненных узлов.[[Файл:UBitTreeExample.jpg|350px|thumb|right|Пример виртуального дерева отрезков над метками, где узел с крестиком - переполненный узел, а с галочкой - непереполненный для <tex>\alpha=1,5x</tex>в цифровом боре.]]

Тогда, как только мы получаем команду вставить элемент, которому не хватает метки, мы поднимаемся вверх от метки элемента <tex>p</tex>, пока не найдем первый непереполненный узел. Может случиться такое, что на всем пути до корня мы не найдем ни одного непереполненного узла. Чтобы этого избежать, изменим требования к <tex>u</tex> позже. Как только мы нашли первый непереполненный узел, переназначим метки Также в каждом узле дополнительно будет храниться:* в его поддереве так, чтобы они находились друг от друга на одинаковых расстояниях (места точно хватит, так как <tex>\dfracлистьях {\mathrm{weight(x)---}}используется ли уже эта метка;[[Файл:UBitTreeExample.jpg|350px|thumb|right|Пример цифрового бора для меток, где узел с крестиком {size(x){---}\leqslant\dfrac{1}переполненный узел, а с галочкой {\alpha^{\mathrm{height(x)}---}}непереполненный для </tex>\alpha=1, если узел непереполненный). После этого плотность распределения всех занятых листьев составит примерно 5</tex>\dfrac.]]* в нелистовых узлах {1}{\alpha^{\mathrm{height(x)---}}}</tex>является ли узел переполненным.

Тогда чтобы после перераспределения меток в поддереве узла <texb>xПереполненным</texb>назовем узел, мы заново пришли к этому же узлу за перераспределением, нужно, чтобы его сын снова переполнился. Если для которого для выбранного <tex>y\alpha</tex> {{---}} сын (<tex>x1<\alpha<2</tex>, то он переполнится, когда ) выполнено <tex>\dfrac{\mathrm{weight(yx)}}{\mathrm{size(yx)}}>\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}}</tex>. Чтобы это произошлоВ листьях не хранится наличие переполненности, требуется, чтобы было сделано еще так как в листьях не может быть переполнения. В крайнем случае для листа: <tex>\dfrac{\mathrm{sizeweight(yx)}*(\dfrac{1}{\alpha^{\mathrm{heightsize(x) - 1}}} - = 1 \ngtr 1 = \dfrac{1}{\alpha^{\mathrm{height(x)}0}}) = \mathrm{size(y)}*\dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}}</tex> добавлений.

С другой стороны, следующее перераспределение меток произойдет, когда <tex>\mathrm{weight(x)} = \dfrac{\mathrm{size(x)}}{\alpha^{\mathrm{height(x)}}} = \dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} </tex>. Получается== Доказательство времени работы ====Рассмотрим, что за <tex>\dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} </tex> операций перераспределения как часто происходит перераспределение меток требуется сделать <tex>\mathrm{size(y)}*\dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}}</tex> операций добавления. Тогда если за каждую операцию добавления брать <tex>\dfrac{2}{\alpha-1}</tex> монет, то за добавления накопится столько монет, чтобы расплатиться за следующую операцию перераспределения в узле <tex>x</tex>. Проблема в том, что таким образом надо платить за каждый уровень, а количество уровней (бит) равно <tex>u</tex>. Тогда амортизированная стоимость добавления <tex>O(u)</tex>. :

Теперь выберем такое * Если в поддереве узла было проведено перераспределение меток, то повторное перераспределение меток в поддереве узла <tex>x</tex> потребуется, когда сын этого узла снова переполнится. Если <tex>y</tex> {{---}} сын <tex>ux</tex>, чтобы корень никогда не переполнялся: то он переполнится, когда <tex>\dfrac{\mathrm{weight(rooty)}}{\mathrm{size(rooty)}} < >\dfrac{1}{\alpha^{\mathrm{height(rootx)}}} \Rightarrow \dfrac{n}{2^u} < \dfrac{- 1}{\alpha ^u} \Rightarrow u \geqslant \log_{\dfrac{ 2}{\alpha}} n</tex>. Тогда операция добавления работает за логарифмическое время от <tex>n</tex>Чтобы это произошло, требуется, а не за константное.чтобы было сделано еще добавлений:

[[Файл:GlobalandLocalLabelstoConst.jpg|350px|thumb|right|Визуализация локальных и глобальных меток.]]<center>Улучшим время работы операции добавления до <tex>O\mathrm{size(y)} \cdot (\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}} - \dfrac{1}{\alpha^{\mathrm{height(x)}}}) = \mathrm{size(y)} \cdot \dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}}</tex>;</center>  * С другой стороны, следующее перераспределение меток произойдет, для этого разобьем весь список на кусочки длины от когда <tex>\dfracmathrm{u}{2weight(x)}</tex> до станет больше <center><tex>2u\dfrac{\mathrm{size(x)}}{\alpha^{\mathrm{height(x)}}} = \dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} </tex>. Внутри каждого кусочка будем тоже присваивать каждому элементу метку</center>  Получается, от что за <tex>0\dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} </tex> до операций перераспределения меток требуется сделать <tex>2^\mathrm{size(y)} \cdot \dfrac{2u\alpha -1}{\alpha^{\mathrm{height(x)}}}</tex> жадно, тогда у каждого элемента списка будет две метки: глобальная и локальнаяопераций добавления. Глобальная задает кусочекИспользуя [[Амортизационный анализ | метод предоплаты]], локальная - положение элемента внутри кусочка. Стоит заметить, что внутри кусочка никогда не будет проблемывидим, что кому-то не хватит метки или придется сделать перераспределение меток, так как, если мы каждый раз в качестве метки будем за каждую операцию добавления брать среднее значение, то для того, чтобы был конфликт из-за меток, нужно больше, чем <tex>2u\dfrac{2}{\alpha-1}</tex> ключей (противоречит условию). А глобальные метки будут организованы в структурумонет, описанную выше. Глобальные метки для кусочков нам придется менятьто за добавления накопится достаточное количество монет, когда один из кусочков переполнился, тогда разделим кусочек на два, присвоив метку второму методом, описанным выше (поднимемся до первого непереполненного). Каждый кусочек будет иметь чтобы расплатиться за следующую операцию перераспределения в узле <tex>ux</tex> занятых меток. Аналогично Однако таким образом требуется платить за каждый уровень, когда в каком-то кусочке слишком мало ключей становится, мы его сливаем с соседним. Внутри кусочков мы ключи присваиваем за <tex>Oа количество уровней (1бит)равно </tex>, а, аналогичный приведенному выше, анализ показывает, что, чтобы потребовалось перераспределение глобальных меток, требуется <tex>\Omega(u)</tex> изменений локальных меток. За эти изменения накопим Тогда амортизированная стоимость добавления составляет <tex>O(u)</tex> монет для изменения глобальных меток, тогда операция добавления работает за константное время.== Использование памяти ==

== Послесловие = Алгоритм за O(1) === Впервые реализацию такой структуры данных со всеми операциями [[Файл:GlobalandLocalLabelstoConst.jpg|350px|thumb|right|y-fast-tree для меток.]]Предыдущий алгоритм работает за константное время предложили ''Dietz'' и ''Sleator''логарифм из-за того, однако их доказательство времени работы было намного сложнее вышеизложенного анализа. Поэтому позже группа ученых во главе с ''Michael Aчто слишком часто приходится перераспределять метки. Bender'' разработала более простое доказательствоИспользуем <tex>\mathrm{y}{-}\mathrm{fast}{-}\mathrm{trie}</tex> (модифицированный цифровой бор), изложенное выше, впервые описанное в их статье ''Two simlified algorithms for maintaining order in a list''чтобы улучшить время работы операции добавления до <tex>O(1)</tex>. Послесловие их статьи таково:

Is == Послесловие == Впервые реализацию такой структуры данных со всеми операциями за константное время амортизационно предложили<ref>[http://www.cs.cmu.edu/~sleator/papers/maintaining-order.html Статья Dietz and Sleator "Two algorithms for maintaining order in a list"]</ref> ''Dietz'' и ''Sleator'', однако их доказательство времени работы было намного сложнее вышеизложенного анализа. Поэтому позже группа ученых во главе с ''Michael A. Bender'' разработала<ref>[http://link.springer.com/chapter/10.1007%2F3-540-45749-6_17 Статья Michael A. Bender "Two Simplified Algorithms for Maintaining Order in a pain List"]</ref> более простое доказательство, изложенное выше, впервые описанное в их статье ''Two simlified algorithms for maintaining order in the assa list''. Послесловие их статьи таково:

Dietz and Sleator is quite influential With its tags and its proofs by potential But to teach it in class Is a pain in the ass So our new result is preferential.

* [https://www.lektorium.tv/lecture/14321 Lectorium {{---}} Лекция А.С. Станкевича]* [https://en.wikipedia.org/wiki/Order-maintenance_problem {{---}} Wikipedia: order maintance problem]* [http://link.springer.com/chapter/10.1007%2F3-540-45749-6_17 {{---}} Статья ''Michael A. Bender'' с описанием более простого доказательства.] [[Категория:Дискретная математика и алгоритмы]Order Maintance Problem]