65
правок
Изменения
Better structure
[[Файл:ListABCD.jpg|250px|thumb|right|Для такого списка команда <tex>\mathrm{order(D,B)}</tex> выдаст <tex>\mathrm{false}</tex>.]]
'''List order maintance''' (русск. <i>поддержка порядка в списке</i>) {{---}} проблема поддержки списка со следующими командамиоперациями:
* <tex>\mathrm{insert(p, q)}</tex> {{---}} вставка нового элемента <tex>p</tex> в список сразу после <tex>q</tex>;
* <tex>\mathrm{remove(p)}</tex> {{---}} удаление элемента <tex>p</tex> из списка;
* <tex>\mathrm{order(p, q)}</tex> {{---}} команда, возвращающая <tex>\mathrm{true}</tex> , если <tex>p</tex> в списке находится до <tex>q</tex> и <tex>\mathrm{false}</tex> иначе.
== Алгоритм за O(logn) ==
[[Файл:ListABCDwithMarks.jpg|250px|thumb|right|Пример расставления меток для списка, <tex>u=3</tex>.]]
Рассмотрим реализацию списка с командой порядка, где все операции выполняются за амортизационную <tex>O(1logn)</tex>.
Дадим каждому элементу списка метки длины <tex>u</tex> из битов. Метки будем хранить в виде [[Сверхбыстрый цифровой бор | цифрового бора]]. Пусть <tex>u:\dfrac{n}{2}<2^u \leqslant 2n</tex>, где <tex>n</tex> {{---}} количество элементов в списке. Если после добавления или удаления элементов <tex>u</tex> перестанет удовлетворять неравенству, пересчитаем все метки заново. Пересчет меток занимает амортизационно <tex>O(1)</tex> по аналогии с саморасширяющимся массивом. Пусть метки идут по возрастанию от начала к концу списка, тогда операцию <tex>\mathrm{order(p,q)}</tex> можно сделать, сравнив метки за <tex>O(1)</tex>. Теперь опишем взаимодействие с метками при выполнении других команд.
* Для выполнения <tex>\mathrm{remove(p)}</tex> просто удалим элемент <tex>p</tex> вместе с его меткой, проверим, удовлетворяет ли <tex>u</tex> неравенству, если нет {{---}} пересчитаем. * Для <tex>\mathrm{insert(p,q)}</tex> существуют два возможных случая:** Метка <tex>r</tex>: <tex>\mathrm{r.label}>\mathrm{p.label} + 1</tex>, где <tex>r</tex> {{---}} следующий за <tex>p</tex> элемент в списке. Тогда между метками <tex>p</tex> и <tex>r</tex> есть свободная метка, которую мы дадим <tex>q:\mathrm{q.label} = \dfrac{\mathrm{p.label}+\mathrm{r.label}}{2}</tex>. После этого опять проверим <tex>u</tex> на соответствие неравенству. [[Файл:UBitTreeListABCD.jpg|350px|thumb|right|Точка {{---}} метка в листе используется.]]** В случае, если между метками <tex>p</tex> и <tex>q</tex> свободной метки нет, нам придется пересчитать метки следующим образом:
[[Файл:UBitTreeExample.jpg|350px|thumb|right|Пример цифрового бора для меток, где узел с крестиком {{---}} переполненный узел, а с галочкой {{---}} непереполненный для <tex>\alpha=1,5</tex>.]]
Тогда, как только мы получаем команду вставить элемент, которому не хватает метки, мы поднимаемся вверх от метки элемента <tex>p</tex>, пока не найдем первый непереполненный узел. Может случиться такое, что на всем пути до корня мы не найдем ни одного непереполненного узла. Чтобы этого избежать, изменим требования к <tex>u</tex> позже. Как только мы нашли первый непереполненный узел, переназначим метки в его поддереве так, чтобы они находились друг от друга на одинаковых расстояниях (места точно хватит, так как <tex>\dfrac{\mathrm{weight(x)}}{size(x)}\leqslant\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>, если узел непереполненный). После этого плотность распределения всех занятых листьев составит примерно <tex>\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>. * Тогда, чтобы после перераспределения меток в поддереве узла <tex>x</tex>, мы заново пришли к этому же узлу за перераспределением, нужно, чтобы его сын снова переполнился. Если <tex>y</tex> {{---}} сын <tex>x</tex>, то он переполнится, когда <tex>\dfrac{\mathrm{weight(y)}}{\mathrm{size(y)}}>\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}}</tex>. Чтобы это произошло, требуется, чтобы было сделано еще <tex>\mathrm{size(y)}*(\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}} - \dfrac{1}{\alpha^{\mathrm{height(x)}}}) = \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>.
== Алгоритм за O(1) ==
[[Файл:GlobalandLocalLabelstoConst.jpg|350px|thumb|right|y-fast-tree для меток.]]
Улучшим время работы операции добавления до <tex>O(1)</tex>, для этого будем использовать <tex>\mathrm{y-fast-tree}</tex> (улучшенный цифровой бор). Внутри каждого кусочка будем тоже присваивать каждому элементу метку, от <tex>0</tex> до <tex>2^{2u-1}</tex> жадно, тогда у каждого элемента списка будет две метки: глобальная и локальная. Глобальная задает кусочек, локальная {{---}} положение элемента внутри кусочка. Стоит заметить, что внутри кусочка никогда не будет проблемы, что кому-то не хватит метки или придется сделать перераспределение меток, так как, если мы каждый раз в качестве метки будем брать среднее значение, то для того, чтобы был конфликт из-за меток, нужно больше, чем <tex>2u</tex> ключей (противоречит условию). А глобальные метки будут организованы в структуру, описанную выше. Глобальные метки для кусочков нам придется менять, когда один из кусочков переполнился, тогда разделим кусочек на два, присвоив метку второму методом, описанным выше (поднимемся до первого непереполненного). Каждый кусочек будет иметь <tex>u</tex> занятых меток. Аналогично, когда в каком-то кусочке слишком мало ключей становится, мы его сливаем с соседним. Внутри кусочков мы ключи присваиваем за <tex>O(1)</tex>, а, аналогичный приведенному выше, анализ показывает, что, чтобы потребовалось перераспределение глобальных меток, требуется <tex>\Omega(u)</tex> изменений локальных меток. За эти изменения накопим <tex>O(u)</tex> монет для изменения глобальных меток, тогда операция добавления работает за константное время.
== Использование памяти ==
Из-за того, что <tex>u</tex> зависит от выбранной <tex>\alpha</tex>, <tex>\alpha</tex> сильно влияет на реализацию. Увеличивая <tex>\alpha</tex>, мы уменьшаем стоимость операции добавления (количество монет, которые надо брать: <tex>\dfrac{2}{\alpha-1}</tex>), но увеличиваем <tex>u</tex>, значит, больше памяти нужно, а, уменьшая <tex>\alpha</tex>, мы выигрываем в памяти, но проигрываем во времени операции добавления. Так как для реализации структуры мы используем <tex>\mathrm{y-fast-tree}</tex>, требуется <tex>O(n)</tex> памяти.
== Послесловие ==
Впервые реализацию такой структуры данных со всеми операциями за константное время амортизационно предложили <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 Статья "Two Simplified Algorithms for Maintaining Order in a List"]</ref> более простое доказательство, изложенное выше, впервые описанное в их статье ''Two simlified algorithms for maintaining order in a list''. Послесловие их статьи таково: Dietz and Sleator is quite influential With its tags and its proofs by potential
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.
== См. также==
* [[Персистентный стек]]
* [[Сверхбыстрый цифровой бор]]
* [[Персистентные структуры данных]]
== Примечания ==
<references />
== Источники информации ==
* [https://www.lektorium.tv/lecture/14321 Lectorium {{---}} лекция А.С. Станкевича]
* [https://en.wikipedia.org/wiki/Order-maintenance_problem Wikipedia {{---}} order maintance problem]
[[Категория:Дискретная математика и алгоритмы]]
