Изменения

[[Файл: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>.Список с командой Проблема поддержания порядка используется в разных алгоритмах и структурахсписке возникает, к примеру, в при реализации [[Персистентные структуры данных|полностью персистентного дерева поиска]].

== Алгоритм за O(logn) ===== Идея ===

Рассмотрим реализацию списка с командой порядкаВсе операции, где все операции выполняются за амортизационную кроме <tex>O\mathrm{order(lognp,q)}</tex>. Дадим каждому элементу списка метки длины , за <tex>uO(1)</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>uq</tex> неравенству, если нет {{---}} пересчитаем. * Для Добавление меток никак не влияет на реализацию операции <tex>\mathrm{insertremove(p,q)}</tex> существуют два возможных случая:** Метка <tex>r</tex>: . Однако реализацию <tex>\mathrm{r.label}>\mathrm{insert(p.label,q)} + 1</tex>, где потребуется изменить: при добавлении нового элемента <tex>rq</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> свободной метки нетнашлась метка. Далее будет рассмотрен алгоритм, нам придется пересчитать метки следующим образом:который позволяет эффективно реализовать эту идею.

=== Алгоритм за O(logn) ======= Способ хранения меток ====Метки будут храниться в виде чисел в двоичной системе счисления. Требуется выбрать такую длину для меток, чтобы перераспределения не случались слишком часто. Если <tex>u</tex> {{---}} длина каждой метки, то для начала пусть <tex>u:n<2^u \leqslant 2n</tex>, где <tex>n</tex> {{---}} количество элементов в списке. Если после добавления элементов какому-то элементу не хватит метки, увеличим <tex>u</tex> на <tex>1</tex> и пересчитаем все метки заново, распределив их равномерно. Заметим, что сразу после перераспределения меток, в среднем, между каждыми двумя элементами списка будет только одна свободная метка, так как при переходе к новому <tex>u</tex> количество меток будет примерно в два раза больше количества элементов списка. Если же после удаления элемента из списка <tex>2^u</tex> станет в <tex>4</tex> раза больше <tex>n</tex>, уменьшим <tex>u</tex> на <tex>1</tex>. Пересчет меток занимает амортизационно <tex>O(1)</tex> по аналогии с [[Динамический массив | саморасширяющимся массивом]]. Однако очевидно, что в таком случае операция добавления за <tex>O(1)</tex> работать не будет, так как, если потребуется добавить между двумя элементами списка больше одного элемента, то новым элементам меток не хватит, и придется провести лишнее перераспределение меток, которое будет рассмотрено ниже. Позже, в доказательстве времени работы, значение <tex>u</tex> будет несколько уточнено. Все метки хранятся будут храниться в [[Сверхбыстрый цифровой бор | цифровом боре ]] высоты <tex>u</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{weightheight(x)}}</tex> {\mathrm{size(x)---}}высота узла <tex>\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>. Получается, что, чем выше, тем более разреженными должны быть поддеревья непереполненных узлов.используется ли уже эта метка;

* С другой стороныПолучается, следующее перераспределение меток произойдет, когда что за <tex>\mathrm{weight(x)} = \dfrac{2\mathrm{size(xy)}}{\alpha^{\mathrm{height(x)}}} = \dfrac{2</tex> операций перераспределения меток требуется сделать <tex>\mathrm{size(y)}\cdot \dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}} </tex>операций добавления. ПолучаетсяИспользуя [[Амортизационный анализ | метод предоплаты]], видим, что если за каждую операцию добавления брать <tex>\dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}-1} </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>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_{\dfracfrac{ 2}{\alpha}} n</tex>. Тогда операция добавления работает за логарифмическое время от <tex>O(\log n)</tex>.

=== Алгоритм за O(1) ===

Улучшим время работы операции добавления до <tex>O(1)</tex>Предыдущий алгоритм работает за логарифм из-за того, для этого будем использовать что слишком часто приходится перераспределять метки. Используем <tex>\mathrm{y}{-}\mathrm{fast}{-tree}\mathrm{trie}</tex> (улучшенный модифицированный цифровой бор). Внутри каждого кусочка будем тоже присваивать каждому элементу метку, от <tex>0</tex> чтобы улучшить время работы операции добавления до <tex>2^{2u-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>u\alpha</tex> зависит от выбранной сильно влияет на реализацию структуры, так как <tex>\alphau</tex>, зависит от выбранной <tex>\alpha</tex> сильно влияет на реализацию. Увеличивая С увеличением <tex>\alpha</tex>, мы уменьшаем уменьшается стоимость операции добавления (количество монет, которые надо брать: <tex>\dfrac{2}{\alpha-1}</tex>), но увеличиваем увеличивается <tex>u</tex>, значит, требуется больше памяти нужно, а, уменьшая <tex>\alpha</tex>, мы выигрываем получаем выигрыш в памяти, но проигрываем проигрыш во времени операции добавления. Так как для реализации структуры мы используем используется <tex>\mathrm{y}{-}\mathrm{fast}{-tree}\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''. Послесловие их статьи таково:

* [https://www.lektorium.tv/lecture/14321 Lectorium {{---}} лекция Лекция А.С. Станкевича]* [https://en.wikipedia.org/wiki/Order-maintenance_problem Wikipedia {{---}} order maintance problem] [[Категория:Дискретная математика и алгоритмы]Order Maintance Problem]