Изменения

[[Файл: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>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{{---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>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>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>u</tex>* С другой стороны, следующее перераспределение меток произойдет, чтобы корень никогда не переполнялся: когда <tex>\dfrac{\mathrm{weight(rootx)}}{\mathrm{size(root)}} < \dfrac{1}{\alpha^{\mathrm{height(root)}}} \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|y-fast-tree для меток.]]<center>Улучшим время работы операции добавления до <tex>O\dfrac{\mathrm{size(x)}}{\alpha^{\mathrm{height(1x)</tex>, для этого будем использовать <tex>}}} = \dfrac{2\mathrm{size(y-fast-tree)}}{\alpha^{\mathrm{height(x)}}}</tex> (улучшенный цифровой бор). Внутри каждого кусочка будем тоже присваивать каждому элементу метку, от <tex>0</texcenter> до   Получается, что за <tex>\dfrac{2^\mathrm{2u-1size(y)}}</tex> жадно, тогда у каждого элемента списка будет две метки: глобальная и локальная. Глобальная задает кусочек, локальная {\alpha^{\mathrm{---height(x)}}} положение элемента внутри кусочка. Стоит заметить, что внутри кусочка никогда не будет проблемы, что кому-то не хватит метки или придется сделать перераспределение меток, так как, если мы каждый раз в качестве метки будем брать среднее значение, то для того, чтобы был конфликт из-за меток, нужно больше, чем </tex>2uопераций перераспределения меток требуется сделать </tex> ключей \mathrm{size(противоречит условиюy). А глобальные метки будут организованы в структуру, описанную выше. Глобальные метки для кусочков нам придется менять, когда один из кусочков переполнился, тогда разделим кусочек на два, присвоив метку второму методом, описанным выше } \cdot \dfrac{\alpha - 1}{\alpha^{\mathrm{height(поднимемся до первого непереполненногоx). Каждый кусочек будет иметь <tex>u}}}</tex> занятых метокопераций добавления. АналогичноИспользуя [[Амортизационный анализ | метод предоплаты]], когда в каком-то кусочке слишком мало ключей становитсявидим, мы его сливаем с соседним. Внутри кусочков мы ключи присваиваем что если за каждую операцию добавления брать <tex>O(\dfrac{2}{\alpha-1)}</tex>монет, а, аналогичный приведенному выше, анализ показывает, чтото за добавления накопится достаточное количество монет, чтобы потребовалось перераспределение глобальных меток, требуется <tex>\Omega(u)</tex> изменений локальных меток. За эти изменения накопим расплатиться за следующую операцию перераспределения в узле <tex>O(u)x</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(nu)</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 для меток.]]Предыдущий алгоритм работает за константное время амортизационно предложили ''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]