List order maintenance

Для такого списка команда [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]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:\dfrac{n}{2}\lt 2^u \leqslant 2n[/math], где [math]n[/math] — количество элементов в списке. Если после добавления или удаления элементов [math]u[/math] перестанет удовлетворять неравенству, пересчитаем все метки заново. Пересчет меток занимает амортизационно [math]O(1)[/math] по аналогии с саморасширяющимся массивом. Позже, в доказательстве времени работы, значение [math]u[/math] будет несколько уточнено.

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

• в листьях — используется ли уже эта метка;

Пример цифрового бора для меток, где узел с крестиком — переполненный узел, а с галочкой — непереполненный для [math]\alpha=1,5[/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]\mathrm{weight(x)}[/math] — это количество помеченных (используемых) листьев (меток) в поддереве узла [math]x[/math], а [math]\mathrm{size(x)}[/math] — это количество всех листьев в поддереве [math]x[/math]. В листьях мы не храним наличие переполненности, так как все листья всегда непереполнены. В крайнем случае: [math] \dfrac{\mathrm{weight(leave)}}{\mathrm{size(leave)}} = 1 = \dfrac{1}{\alpha^{\mathrm{height(x)}}} = \dfrac{1}{\alpha^{0}}[/math].

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

Перераспределение меток потребуется выполнить в случае, когда для нового элемента нет свободной метки. Ниже будет описан способ выполнения перераспределения меток: как только требуется вставить элемент [math]p[/math], которому не хватает метки, будем подниматься вверх от метки элемента, следующего за [math]q[/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)} = \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]u[/math] зависит от выбранной [math]\alpha[/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] памяти.

Послесловие

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

См. также

• Список
• Персистентный стек
• Сверхбыстрый цифровой бор
• Персистентные структуры данных

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

• Lectorium — Лекция А.С. Станкевича
• Wikipedia — Order Maintance Problem