Изменения
→Способ хранения меток
[[Файл: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> иначе.
== Алгоритм ==
=== Идея ===
[[Файл:ListABCDwithMarks.jpg|250px|thumb|right|Пример расставления меток для списка, <tex>u=3</tex>.]]
== Применение ==Перераспределение меток ====Перераспределение меток потребуется выполнить в случае, когда для нового элемента не будет свободной метки. Пусть требуется выполнить операцию <tex>\mathrm{insert(p, q)}</tex>, но метка, следующая за меткой <tex>q</tex> уже присвоена элементу <tex>z</tex>. Тогда будем подниматься вверх от метки <tex>z</tex> до тех пор, пока не будет найден первый непереполненный узел. Может случиться такое, что на всем пути до корня не встретится ни одного непереполненного узла. Чтобы этого избежать, уточним границы <tex>u</tex> позже. Как только будет найден первый непереполненный узел, переназначим метки в поддереве этого узла так, чтобы они находились друг от друга на одинаковых расстояниях (места точно хватит, так как <tex>\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}\leqslant\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>, если узел непереполненный). После этого между занятыми метками будет не меньше <tex>\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>. Чтобы это произошло, требуется, чтобы было сделано еще добавлений:
<center>
<tex>\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>\mathrm{weight(x)}</tex> станет больше
<center>
<tex>\dfrac{\mathrm{size(x)}}{\alpha^{\mathrm{height(x)}}} = \dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} </tex>.
</center>
Получается, что за <tex>\dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} </tex> операций перераспределения меток требуется сделать <tex>\mathrm{size(y)} \cdot \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>u</tex>: <tex>\dfrac{\mathrm{weight(root)}}{\mathrm{size(root)}} < \dfrac{1}{\alpha^{\mathrm{height(root)}}} \Rightarrow \dfrac{n}{2^u} < \dfrac{1}{\alpha ^u} \Rightarrow u \geqslant \log_{\frac{ 2}{\alpha}} n</tex>. Тогда операция добавления работает за <tex>O(\log n)</tex>.
=== Алгоритм за O(1) ===
[[Файл:GlobalandLocalLabelstoConst.jpg|350px|thumb|right|y-fast-tree для меток.]]
Предыдущий алгоритм работает за логарифм из-за того, что слишком часто приходится перераспределять метки. Используем <tex>\mathrm{y}{-}\mathrm{fast}{-}\mathrm{trie}</tex> (модифицированный цифровой бор), чтобы улучшить время работы операции добавления до <tex>O(1)</tex>.
У каждого элемента списка будет две метки: глобальная и локальная. Глобальная задает блок, локальная {{---}} положение элемента внутри блока. Описание взаимодействия с метками:
* <b>локальные метки</b> внутри каждого блока каждому элементу от <tex>0</tex> до <tex>2^{2u-1}</tex> будут жадно присвоены. Стоит заметить, что внутри блока никогда не будет проблемы, что кому-то не хватит метки или придется сделать перераспределение меток, так как, если каждый раз в качестве метки брать среднее значение, то для того, чтобы был конфликт из-за меток, нужно больше, чем <tex>2u</tex> ключей (противоречит условию);
* <b>глобальные метки</b> будут организованы в структуру, использовавшуюся в реализации операции за логарифмическое время. Глобальные метки для блоков придется менять, когда один из блоков переполнился. Тогда блок будет разделен на два, метка второму будет присвоена методом, описанным выше (поднимемся до первого непереполненного). Каждый блок будет иметь <tex>u</tex> занятых меток. Аналогично, когда в каком-то блок становится слишком мало ключей, он будет слит с соседним.
Внутри блоков присваиваются ключи за <tex>O(1)</tex>, а аналогичный приведенному выше анализ показывает, что к перераспределению глобальных меток приводит<tex>\Omega(u)</tex> изменений локальных меток. За эти изменения будет накоплено <tex>O(u)</tex> монет для изменения глобальных меток, тогда операция добавления работает за константное время.
== Использование памяти ==
Выбор <tex>\alpha</tex> сильно влияет на реализацию структуры, так как <tex>u</tex> зависит от выбранной <tex>\alpha</tex>. С увеличением <tex>\alpha</tex>, уменьшается стоимость операции добавления (количество монет, которые надо брать: <tex>\dfrac{2}{\alpha-1}</tex>), но увеличивается <tex>u</tex>, значит, требуется больше памяти, а, уменьшая <tex>\alpha</tex>, получаем выигрыш в памяти, но проигрыш во времени операции добавления. Так как для реализации структуры используется <tex>\mathrm{y}{-}\mathrm{fast}{-}\mathrm{trie}</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 Статья Michael A. Bender "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
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 {{---}} Wikipedia: order maintance problem] [[Категория:Дискретная математика и алгоритмы]Order Maintance Problem]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Амортизационный анализ]]
[[Категория: Структуры данных]]