List order maintenance — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (переименовал List order maintance в List order maintenance: неправильное название)
м (rollbackEdits.php mass rollback)
 
(не показано 26 промежуточных версий 4 участников)
Строка 1: Строка 1:
[[Файл:ListABCD.jpg|250px|thumb|right|Для такого списка команда <tex>\mathrm{order(D,B)}</tex> выдаст <tex>\mathrm{false}</tex>.]]
+
[[Файл:ListABCD.jpg|250px|thumb|right|Для такого списка операция <tex>\mathrm{order(D,B)}</tex> выдаст <tex>\mathrm{false}</tex>.]]
'''List order maintance''' {{---}} проблема поддержки списка со следующими командами:
+
'''List order maintance''' (рус. <i>поддержание порядка в списке</i>) {{---}} проблема поддержания списка со следующими операциями:
 
* <tex>\mathrm{insert(p, q)}</tex> {{---}} вставка нового элемента <tex>p</tex> в список сразу после <tex>q</tex>;
 
* <tex>\mathrm{insert(p, q)}</tex> {{---}} вставка нового элемента <tex>p</tex> в список сразу после <tex>q</tex>;
 
* <tex>\mathrm{remove(p)}</tex> {{---}} удаление элемента <tex>p</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> иначе.
+
* <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>.
 +
Проблема поддержания порядка в списке возникает, к примеру, при реализации [[Персистентные структуры данных|полностью персистентного дерева поиска]].
  
 
== Алгоритм ==
 
== Алгоритм ==
 +
=== Идея ===
 
[[Файл:ListABCDwithMarks.jpg|250px|thumb|right|Пример расставления меток для списка, <tex>u=3</tex>.]]
 
[[Файл:ListABCDwithMarks.jpg|250px|thumb|right|Пример расставления меток для списка, <tex>u=3</tex>.]]
Рассмотрим реализацию списка с командой порядка, где все операции выполняются за амортизационную <tex>O(1)</tex>.
+
Все операции, кроме <tex>\mathrm{order(p,q)}</tex>, за <tex>O(1)</tex> может выполнить обычный [[Список|двусвязный список]], но с его помощью невозможно получить информацию о порядке объектов. Для реализации этой операции каждому узлу можно сопоставить некоторое число так, чтобы все числа строго возрастали от начала к концу списка. Таким образом, эти числа, которые в дальнейшим будут называться <b>метками</b>, задают порядок на элементах списка.
Дадим каждому элементу списка метки длины <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>\mathrm{order(p,q)}</tex> можно за <tex>O(1)</tex>, просто сравнив метки <tex>p</tex> и <tex>q</tex>. Добавление меток никак не влияет на реализацию операции <tex>\mathrm{remove(p)}</tex>. Однако реализацию <tex>\mathrm{insert(p,q)}</tex> потребуется изменить: при добавлении нового элемента <tex>q</tex> после узла <tex>p</tex>, узлу <tex>q</tex> необходимо присвоить метку, которая строго больше предыдущего элемента и строго меньше следующего. В какой-то момент возникнет ситуация, что новой метки не найдётся, тогда метки можно перераспределить среди элементов списка так, чтобы для узла <tex>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> на соответствие неравенству.
+
=== Алгоритм за O(logn) ===
[[Файл:UBitTreeListABCD.jpg|350px|thumb|right|Точка - метка в листе используется.]]
+
==== Способ хранения меток ====
 +
Метки будут храниться в виде чисел в двоичной системе счисления. Требуется выбрать такую длину для меток, чтобы перераспределения не случались слишком часто. Если <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>p</tex> и <tex>q</tex> свободной метки нет, нам придется пересчитать метки следующим образом. Построим виртуальное дерево отрезков над всеми возможными метками, где в каждом узле будем хранить <tex>1</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>. Получается, что чем выше, тем более разреженными должны быть поддеревья непереполненных узлов.
+
Все метки будут храниться  в [[Сверхбыстрый цифровой бор | цифровом боре]] высоты <tex>u</tex> (там представлены не только используемые метки, а вообще все возможные заданной длины). Введем некоторые обозначения:
[[Файл:UBitTreeExample.jpg|350px|thumb|right|Пример виртуального дерева отрезков над метками, где узел с крестиком - переполненный узел, а с галочкой - непереполненный для <tex>\alpha=1,5</tex>.]]
+
* <tex>\mathrm{weight(x)}</tex> {{---}} количество помеченных (используемых) листьев (меток) в поддереве узла  <tex>x</tex>;
 +
* <tex>\mathrm{size(x)}</tex> {{---}} количество всех листьев в поддереве <tex>x</tex>;
 +
* <tex>\mathrm{height(x)}</tex> {{---}} высота узла <tex>x</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>.  
+
Также в каждом узле дополнительно будет храниться:
 +
* в листьях {{---}} используется ли уже эта метка;
 +
[[Файл:UBitTreeExample.jpg|350px|thumb|right|Пример цифрового бора для меток, где узел с крестиком {{---}} переполненный узел, а с галочкой {{---}} непереполненный для <tex>\alpha=1,5</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> добавлений.
+
<b>Переполненным</b> назовем узел, для которого для выбранного <tex>\alpha</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(x)}}{\mathrm{size(x)}} = 1 \ngtr 1 = \dfrac{1}{\alpha^{0}} = \dfrac{1}{\alpha^{\mathrm{height(x)}}} </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>\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>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_{\dfrac{ 2}{\alpha}} n</tex>. Тогда операция добавления работает за логарифмическое время от <tex>n</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>. Чтобы это произошло, требуется, чтобы было сделано еще добавлений:
  
[[Файл:GlobalandLocalLabelstoConst.jpg|350px|thumb|right|Визуализация локальных и глобальных меток.]]
+
<center>
Улучшим время работы операции добавления до <tex>O(1)</tex>, для этого разобьем весь список на кусочки длины от <tex>\dfrac{u}{2}</tex> до <tex>2u</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>\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) ===
Впервые реализацию такой структуры данных со всеми операциями за константное время предложили ''Dietz'' и ''Sleator'', однако их доказательство времени работы было намного сложнее вышеизложенного анализа. Поэтому позже группа ученых во главе с ''Michael A. Bender'' разработала более простое доказательство, изложенное выше, впервые описанное в их статье ''Two simlified algorithms for maintaining order in a list''. Послесловие их статьи таково:
+
[[Файл:GlobalandLocalLabelstoConst.jpg|350px|thumb|right|y-fast-tree для меток.]]
 +
Предыдущий алгоритм работает за логарифм из-за того, что слишком часто приходится перераспределять метки. Используем <tex>\mathrm{y}{-}\mathrm{fast}{-}\mathrm{trie}</tex> (модифицированный цифровой бор), чтобы улучшить время работы операции добавления до <tex>O(1)</tex>.  
  
 +
У каждого элемента списка будет две метки: глобальная и локальная. Глобальная задает блок, локальная {{---}} положение элемента внутри блока. Описание взаимодействия с метками:
  
Dietz and Sleator is quite influential
+
* <b>локальные метки</b> внутри каждого блока каждому элементу от <tex>0</tex> до <tex>2^{2u-1}</tex> будут жадно присвоены. Стоит заметить, что внутри блока никогда не будет проблемы, что кому-то не хватит метки или придется сделать перераспределение меток, так как, если каждый раз в качестве метки брать среднее значение, то для того, чтобы был конфликт из-за меток, нужно больше, чем <tex>2u</tex> ключей (противоречит условию);
 +
* <b>глобальные метки</b> будут организованы в структуру, использовавшуюся в реализации операции за логарифмическое время. Глобальные метки для блоков придется менять, когда один из блоков переполнился. Тогда блок будет разделен на два, метка второму будет присвоена методом, описанным выше (поднимемся до первого непереполненного). Каждый блок будет иметь <tex>u</tex> занятых меток. Аналогично, когда в каком-то блок становится слишком мало ключей, он будет слит с соседним.
  
With its tags and its proofs by potential
+
Внутри блоков присваиваются ключи за <tex>O(1)</tex>, а аналогичный приведенному выше анализ показывает, что к перераспределению глобальных меток приводит<tex>\Omega(u)</tex> изменений локальных меток. За эти изменения будет накоплено <tex>O(u)</tex> монет для изменения глобальных меток, тогда операция добавления работает за константное время.
  
But to teach it in class
+
== Использование памяти ==
 +
Выбор <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> памяти.
  
Is a pain in the ass
+
== Послесловие ==
 +
Впервые реализацию такой структуры данных со всеми операциями за константное время амортизационно предложили<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''. Послесловие их статьи таково:
  
So our new result is preferential.
+
  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 {{---}} Лекция А.С. Станкевича]
+
* [https://www.lektorium.tv/lecture/14321 Lectorium {{---}} Лекция А.С. Станкевича]
* [https://en.wikipedia.org/wiki/Order-maintenance_problem {{---}} Wikipedia: order maintance problem]
+
* [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'' с описанием более простого доказательства.]
 
 
 
[[Категория:Дискретная математика и алгоритмы]]
 
  
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Амортизационный анализ]]
 
[[Категория: Амортизационный анализ]]
 
[[Категория: Структуры данных]]
 
[[Категория: Структуры данных]]

Текущая версия на 19:15, 4 сентября 2022

Для такого списка операция [math]\mathrm{order(D,B)}[/math] выдаст [math]\mathrm{false}[/math].

List order maintance (рус. поддержание порядка в списке) — проблема поддержания списка со следующими операциями:

  • [math]\mathrm{insert(p, q)}[/math] — вставка нового элемента [math]p[/math] в список сразу после [math]q[/math];
  • [math]\mathrm{remove(p)}[/math] — удаление элемента [math]p[/math] из списка;
  • [math]\mathrm{order(p, q)}[/math] — операция, возвращающая [math]\mathrm{true}[/math] , если [math]p[/math] в списке находится до [math]q[/math] и [math]\mathrm{false}[/math] иначе.

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

Алгоритм

Идея

Пример расставления меток для списка, [math]u=3[/math].

Все операции, кроме [math]\mathrm{order(p,q)}[/math], за [math]O(1)[/math] может выполнить обычный двусвязный список, но с его помощью невозможно получить информацию о порядке объектов. Для реализации этой операции каждому узлу можно сопоставить некоторое число так, чтобы все числа строго возрастали от начала к концу списка. Таким образом, эти числа, которые в дальнейшим будут называться метками, задают порядок на элементах списка.

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

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

Способ хранения меток

Метки будут храниться в виде чисел в двоичной системе счисления. Требуется выбрать такую длину для меток, чтобы перераспределения не случались слишком часто. Если [math]u[/math] — длина каждой метки, то для начала пусть [math]u:n\lt 2^u \leqslant 2n[/math], где [math]n[/math] — количество элементов в списке. Если после добавления элементов какому-то элементу не хватит метки, увеличим [math]u[/math] на [math]1[/math] и пересчитаем все метки заново, распределив их равномерно. Заметим, что сразу после перераспределения меток, в среднем, между каждыми двумя элементами списка будет только одна свободная метка, так как при переходе к новому [math]u[/math] количество меток будет примерно в два раза больше количества элементов списка. Если же после удаления элемента из списка [math]2^u[/math] станет в [math]4[/math] раза больше [math]n[/math], уменьшим [math]u[/math] на [math]1[/math]. Пересчет меток занимает амортизационно [math]O(1)[/math] по аналогии с саморасширяющимся массивом. Однако очевидно, что в таком случае операция добавления за [math]O(1)[/math] работать не будет, так как, если потребуется добавить между двумя элементами списка больше одного элемента, то новым элементам меток не хватит, и придется провести лишнее перераспределение меток, которое будет рассмотрено ниже. Позже, в доказательстве времени работы, значение [math]u[/math] будет несколько уточнено.

Все метки будут храниться в цифровом боре высоты [math]u[/math] (там представлены не только используемые метки, а вообще все возможные заданной длины). Введем некоторые обозначения:

  • [math]\mathrm{weight(x)}[/math] — количество помеченных (используемых) листьев (меток) в поддереве узла [math]x[/math];
  • [math]\mathrm{size(x)}[/math] — количество всех листьев в поддереве [math]x[/math];
  • [math]\mathrm{height(x)}[/math] — высота узла [math]x[/math] в цифровом боре.

Также в каждом узле дополнительно будет храниться:

  • в листьях — используется ли уже эта метка;
Пример цифрового бора для меток, где узел с крестиком — переполненный узел, а с галочкой — непереполненный для [math]\alpha=1,5[/math].
  • в нелистовых узлах — является ли узел переполненным.

Переполненным назовем узел, для которого для выбранного [math]\alpha[/math] ([math]1\lt \alpha\lt 2[/math]) выполнено [math]\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}\gt \dfrac{1}{\alpha^{\mathrm{height(x)}}}[/math]. В листьях не хранится наличие переполненности, так как в листьях не может быть переполнения. В крайнем случае для листа: [math] \dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}} = 1 \ngtr 1 = \dfrac{1}{\alpha^{0}} = \dfrac{1}{\alpha^{\mathrm{height(x)}}} [/math].

Перераспределение меток

Перераспределение меток потребуется выполнить в случае, когда для нового элемента не будет свободной метки. Пусть требуется выполнить операцию [math]\mathrm{insert(p, q)}[/math], но метка, следующая за меткой [math]q[/math] уже присвоена элементу [math]z[/math]. Тогда будем подниматься вверх от метки [math]z[/math] до тех пор, пока не будет найден первый непереполненный узел. Может случиться такое, что на всем пути до корня не встретится ни одного непереполненного узла. Чтобы этого избежать, уточним границы [math]u[/math] позже. Как только будет найден первый непереполненный узел, переназначим метки в поддереве этого узла так, чтобы они находились друг от друга на одинаковых расстояниях (места точно хватит, так как [math]\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}\leqslant\dfrac{1}{\alpha^{\mathrm{height(x)}}}[/math], если узел непереполненный). После этого между занятыми метками будет не меньше [math]\alpha^{\mathrm{height(x)}}[/math] свободных меток.

Доказательство времени работы

Рассмотрим, как часто происходит перераспределение меток:

  • Если в поддереве узла было проведено перераспределение меток, то повторное перераспределение меток в поддереве узла [math]x[/math] потребуется, когда сын этого узла снова переполнится. Если [math]y[/math] — сын [math]x[/math], то он переполнится, когда [math]\dfrac{\mathrm{weight(y)}}{\mathrm{size(y)}}\gt \dfrac{1}{\alpha^{\mathrm{height(x) - 1}}}[/math]. Чтобы это произошло, требуется, чтобы было сделано еще добавлений:

[math]\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)}}}[/math];


  • С другой стороны, следующее перераспределение меток произойдет, когда [math]\mathrm{weight(x)}[/math] станет больше

[math]\dfrac{\mathrm{size(x)}}{\alpha^{\mathrm{height(x)}}} = \dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} [/math].


Получается, что за [math]\dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} [/math] операций перераспределения меток требуется сделать [math]\mathrm{size(y)} \cdot \dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}}[/math] операций добавления. Используя метод предоплаты, видим, что если за каждую операцию добавления брать [math]\dfrac{2}{\alpha-1}[/math] монет, то за добавления накопится достаточное количество монет, чтобы расплатиться за следующую операцию перераспределения в узле [math]x[/math].

Однако таким образом требуется платить за каждый уровень, а количество уровней (бит) равно [math]u[/math]. Тогда амортизированная стоимость добавления составляет [math]O(u)[/math].

Для того, чтобы на пути к корню точно встретился непереполненный узел, требуется уточнить границы [math]u[/math]: [math]\dfrac{\mathrm{weight(root)}}{\mathrm{size(root)}} \lt \dfrac{1}{\alpha^{\mathrm{height(root)}}} \Rightarrow \dfrac{n}{2^u} \lt \dfrac{1}{\alpha ^u} \Rightarrow u \geqslant \log_{\frac{ 2}{\alpha}} n[/math]. Тогда операция добавления работает за [math]O(\log n)[/math].

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

y-fast-tree для меток.

Предыдущий алгоритм работает за логарифм из-за того, что слишком часто приходится перераспределять метки. Используем [math]\mathrm{y}{-}\mathrm{fast}{-}\mathrm{trie}[/math] (модифицированный цифровой бор), чтобы улучшить время работы операции добавления до [math]O(1)[/math].

У каждого элемента списка будет две метки: глобальная и локальная. Глобальная задает блок, локальная — положение элемента внутри блока. Описание взаимодействия с метками:

  • локальные метки внутри каждого блока каждому элементу от [math]0[/math] до [math]2^{2u-1}[/math] будут жадно присвоены. Стоит заметить, что внутри блока никогда не будет проблемы, что кому-то не хватит метки или придется сделать перераспределение меток, так как, если каждый раз в качестве метки брать среднее значение, то для того, чтобы был конфликт из-за меток, нужно больше, чем [math]2u[/math] ключей (противоречит условию);
  • глобальные метки будут организованы в структуру, использовавшуюся в реализации операции за логарифмическое время. Глобальные метки для блоков придется менять, когда один из блоков переполнился. Тогда блок будет разделен на два, метка второму будет присвоена методом, описанным выше (поднимемся до первого непереполненного). Каждый блок будет иметь [math]u[/math] занятых меток. Аналогично, когда в каком-то блок становится слишком мало ключей, он будет слит с соседним.

Внутри блоков присваиваются ключи за [math]O(1)[/math], а аналогичный приведенному выше анализ показывает, что к перераспределению глобальных меток приводит[math]\Omega(u)[/math] изменений локальных меток. За эти изменения будет накоплено [math]O(u)[/math] монет для изменения глобальных меток, тогда операция добавления работает за константное время.

Использование памяти

Выбор [math]\alpha[/math] сильно влияет на реализацию структуры, так как [math]u[/math] зависит от выбранной [math]\alpha[/math]. С увеличением [math]\alpha[/math], уменьшается стоимость операции добавления (количество монет, которые надо брать: [math]\dfrac{2}{\alpha-1}[/math]), но увеличивается [math]u[/math], значит, требуется больше памяти, а, уменьшая [math]\alpha[/math], получаем выигрыш в памяти, но проигрыш во времени операции добавления. Так как для реализации структуры используется [math]\mathrm{y}{-}\mathrm{fast}{-}\mathrm{trie}[/math], требуется [math]O(n)[/math] памяти.

Послесловие

Впервые реализацию такой структуры данных со всеми операциями за константное время амортизационно предложили[1] Dietz и Sleator, однако их доказательство времени работы было намного сложнее вышеизложенного анализа. Поэтому позже группа ученых во главе с Michael A. Bender разработала[2] более простое доказательство, изложенное выше, впервые описанное в их статье 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.

См. также

Примечания

Источники информации