Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
 
(не показано 17 промежуточных версий 1 участника)
Строка 3: Строка 3:


== Постановка задачи ==
== Постановка задачи ==
''Очередь с приоритетами'' представляет собой абстрактную структуру данных, поддерживающую множество из Q элементов, каждому из которых присвоено значение, называемое ключом, а также следующий набор операций [4, 7].
''Очередь с приоритетами'' представляет собой абстрактную структуру данных, поддерживающую множество из Q элементов, каждому из которых присвоено значение, называемое ''ключом'', а также следующий набор операций [4, 7].


'''insert'''(Q, x, k): вставка элемента x с ключом k в Q.
'''insert'''(Q, x, k): вставка элемента x с ключом k в Q.
Строка 18: Строка 18:
'''decrease-key'''(Q, x, k): уменьшение текущего ключа k' элемента x до k, предполагая, что k < k'.
'''decrease-key'''(Q, x, k): уменьшение текущего ключа k' элемента x до k, предполагая, что k < k'.


'''meld'''(<math>Q_1, Q_2</math>): получая на вход очереди с приоритетами <math>Q_1</math> и <math>Q_2</math>, выдает очередь с приоритетом <math>Q_1 \cup Q_2</math>.
'''meld'''(<math>Q_1, Q_2</math>): на входе очереди с приоритетами <math>Q_1</math> и <math>Q_2</math>, на выходе – очередь с приоритетом <math>Q_1 \cup Q_2</math>.




Заметим, что операция delete-min может быть реализована как комбинация find-min и последующей delete, decrease-key – как delete с последующей insert, а meld – как серия find-min, delete и insert. Однако существуют и более эффективные реализации decrease-key и meld [4, 7].
Заметим, что операция '''delete-min''' может быть реализована как комбинация '''find-min''' и последующей '''delete''', '''decrease-key''' – как '''delete''' с последующей '''insert''', а '''meld''' – как серия '''find-min''', '''delete''' и '''insert'''. Однако существуют и более эффективные реализации '''decrease-key''' и '''meld''' [4, 7].




Строка 40: Строка 40:
Нижеследующая информация будет полезной для более полного понимания результатов, приведенных в разделе «Основные результаты».
Нижеследующая информация будет полезной для более полного понимания результатов, приведенных в разделе «Основные результаты».


• Стандартная RAM-машина моделирует ход выполнения программы, написанной на стандартном языке программирования, таком как С. Помимо прямой и косвенной адресации и условных переходов, программа может содержать функции (например, сложение и умножение), выполняемые над константным количеством слов. Память разделена на два слова с линейной адресацией, начинающейся с 0. Время выполнения программы равно количеству выполненных команд, а объем памяти – номеру максимального использованного адреса. Длина слова представляет собой машинно-зависимый параметр, достаточно большой для хранения ключа, и является по меньшей мере логарифмической относительно количества входных ключей, что обеспечивает возможность их адресации.
• Стандартная ''пословная'' RAM-машина моделирует ход выполнения программы, написанной на стандартном языке программирования, таком как С. Помимо прямой и косвенной адресации и условных переходов, программа может содержать функции (например, сложение и умножение), выполняемые над константным количеством слов. Память разделена на два слова с линейной адресацией, начинающейся с 0. Время выполнения программы равно количеству выполненных команд, а объем памяти – номеру максимального использованного адреса. Длина слова представляет собой машинно-зависимый параметр, достаточно большой для хранения ключа, и является по меньшей мере логарифмической относительно количества входных ключей, что обеспечивает возможность их адресации.


• Машина с указателями аналогична RAM-машине за тем исключением, что с адресами нельзя производить какие-либо действия.
• Машина с указателями аналогична пословной RAM-машине за тем исключением, что с адресами нельзя производить какие-либо действия.


• Класс сложности <math>AC^0</math> включает схемы константной глубины с неограниченным коэффициентом разветвления по входу [18]. Под стандартными операциями <math>AC^0</math> понимают операции, доступные в C, такие, что функции над словами принадлежат к <math>AC^0</math>. К примеру, в их число входит сложение, но не умножение.
• Класс сложности <math>AC^0</math> включает схемы константной глубины с неограниченным коэффициентом разветвления по входу [18]. Под стандартными операциями <math>AC^0</math> понимаются операции, доступные в C, такие, что функции над словами принадлежат к <math>AC^0</math>. К примеру, в их число входит сложение, но не умножение.


• Целочисленные ключи ссылаются на неотрицательные целые числа. Если же входные ключи представляют собой целые числа со знаком, корректный порядок ключей можно получить в результате переключения битов, содержащих знаки, и интерпретации их как беззнаковых целых чисел. Аналогичные действия можно произвести для чисел с плавающей запятой и дробных чисел [14].
• Целочисленные ключи ссылаются на неотрицательные целые числа. Если же входные ключи представляют собой целые числа со знаком, корректный порядок ключей можно получить в результате переключения битов, содержащих знаки, и интерпретации их как беззнаковых целых чисел. Аналогичные действия можно произвести для чисел с плавающей запятой и дробных чисел [14].
Строка 51: Строка 51:


== Основные результаты ==
== Основные результаты ==
Основными результатами являются две редукции из очередей с приоритетами к сортировке. Более сильная из этих редукций, изложенная в теореме 1, касается целочисленных очередей с приоритетами, выполняющихся на стандартной пословной RAM-машине.
'''Теорема 1. Если для некоторой неубывающей функции S до n целочисленных ключей могут быть отсортированы за время S(n) на ключ, целочисленная очередь с приоритетами может быть реализована с поддержкой операции find-min за константное время и операций обновления, т. е. вставки и удаления, за время S(n) + O(1). Здесь n равно текущему количеству ключей в очереди. Редукция использует линейный объем памяти и выполняется на стандартной пословной RAM-машине, на которой каждый целочисленный ключ хранится в одном слове.'''
Вышеприведенная редукция задает новые границы для линейных требований к объему памяти для целочисленных очередей с приоритетами, улучшая предыдущие границы, представленные в работах [8, 14] и [5], соответственно.
1. ('''Детерминированный случай''') время обновления O(log log n) при помощи алгоритма сортировки из [9].
2. ('''Рандомизированный''') ожидаемое время обновления <math>O(\sqrt{log \; log \; n})</math> при помощи алгоритма сортировки из [10].
3. ('''Рандомизированный с выполнением операции decrease-key за время O(1)''') ожидаемое время обновления <math>O \Big( (log \; n)^{\frac{1}{2 - \epsilon}} \Big)</math> для слов длиной, больше или равной log n, и любого константного <math>\epsilon > 0</math> при помощи алгоритма сортировки из [3].
Редукция из теоремы 1 использует атомарные кучи [6], которые мало того что очень сложны сами по себе, но к тому же используют операции, не входящие в <math>AC^0</math>. Следующая, несколько более слабая рекурсивная редукция, не ограничивающая область определения ключей, является полностью комбинаторной.
'''Теорема 2. Пусть дана программа сортировки, выполняющая сортировку до n ключей за время S(n) на ключ. Очередь с приоритетами может быть реализована с поддержкой операции find-min за константное время и операций обновления – за время T(n), где n – текущее количество ключей в очереди, а T(n) удовлетворяет следующему условию рекуррентности:'''
<math>T(n) = O(S(n) + T(log^2 \; n))</math>
'''Редукция выполняется на машине с указателями с использованием линейного объема памяти и только стандартными операциями из <math>AC^0</math>. Обращения к значениям ключей производятся только программой сортировки.'''
Данная редукция обеспечивает следующие новые границы для очередей с приоритетами, не поддерживаемые теоремой 1, причем первые две позиции улучшают предыдущие границы, представленные в работах [13] и [16], соответственно.
1. ('''Детерминированный для стандартного алгоритма класса сложности <math>AC^0</math>''') время обновления <math>O((log \; log \; n)^{1 + \epsilon})</math> для любого константного <math>\epsilon > 0</math> при помощи стандартного алгоритма сортировки целых чисел класса <math>AC^0</math> из работы [10].
2. ('''Рандомизированный для стандартного алгоритма <math>AC^0</math>''') ожидаемое время обновления O(log log n) при помощи стандартного алгоритма сортировки целых чисел класса <math>AC^0</math> из работы [16].
3. ('''Строки из <math>l</math> слов''') ожидаемое время обновления <math>O(l + log \; log \; n)</math> для детерминированного и <math>O(l + \sqrt{log \; log \; n})</math> – для рандомизированного случая при помощи алгоритма сортировки строк из [10].
'''Редукция в теореме 1'''
Пусть дана процедура сортировки, выполняющая сортировку до n ключей за время S(n) на ключ. Очередь с приоритетами строится следующим образом.
Структура данных состоит из двух основных компонентов: отсортированного списка ключей и множества буферов обновления. Список ключей разбит на два небольших сегмента, каждый из которых поддерживается в виде атомарной кучи, обеспечивающей константное время выполнения операций обновления и поиска на этом сегменте. Каждый буфер обновления имеет разную емкость и поддерживает обновления (вставка / удаление) со значениями ключей в разных диапазонах. Буферы меньшей емкости предназначены для обновления с ключами меньшей величины. Атомарная куча используется для определения за константное время того, какой буфер обновления содержит новое обновление. Когда буфер обновления соберет достаточно обновлений, они вначале проходят этап сортировки, а затем – этап слияния. На этапе слияния каждое обновление применяется к соответствующему сегменту списка ключей, а также фиксируются инварианты размеров сегментов и диапазонов буферов обновления. Эти этапы выполняются не немедленно, а в фиксированные временные отрезки в рамках общего периода времени. Буфер обновления продолжает принимать новые обновления, при этом некоторые ранее принятые им обновления все еще могут находиться на этапе сортировки, а некоторые более поздние – на этапе слияния. При получении каждого нового обновления на связанном с ним этапе сортировки на него тратится S(n) времени, а на этапе слияния – O(1) времени. Эта стратегия позволяет доводить этапы сортировки и слияния до завершения к моменту очередного заполнения буфера обновления, обеспечивая плавность прохождения обновлениями нужных этапов и сохраняя время обновления S(n) + O(1) в худшем случае. Кроме того, ограничения на размер и емкость гарантируют, что даже самый маленький ключ в структуре данных доступен за время O(1). Далее изложим эту технологию более подробно.
'''Отсортированный список ключей''': отсортированный список содержит большинство ключей в структуре данных, в том числе минимальный ключ, и называется ''базовым списком''. Этот список разбит на ''базовые сегменты'', каждый из которых содержит <math> \Theta((log \; n)^2)</math> ключей. Ключи в каждом сегменте поддерживаются в виде атомарной кучи, так что если становится известно, что новое обновление должно быть применено к конкретному сегменту, оно может быть применено за время O(1). Если базовый сегмент становится слишком большим или слишком маленьким, он разбивается на две части либо объединяется со смежным сегментом.
'''Буферы обновления''': базовые сегменты отделяются друг от друга ''базовыми разделителями'', из которых O(log n) выбираются в качестве ''верхних разделителей'', так что количество ключей в базовом списке под i-м (i > 0) верхним разделителем <math>s_i</math> составляет <math>\Theta (4^i(log \; n)^2)</math>. Эти разделители располагаются в атомарной куче. По мере изменений базового списка верхние разделители перемещаются по необходимости с тем, чтобы сохранить их экспоненциальное распределение.
С каждым верхним разделителем <math>s_i</math>, i > 1, ассоциированы три буфера: ''входной буфер'', ''буфер сортировки'' и ''буфер слияния'', каждый емкостью в <math>4^i</math> ключа. Верхний разделитель <math>s_i</math> работает по циклу, состоящему из <math>4^i</math> шагов. В начале цикла входной буфер пуст, буфер сортировки содержит не более <math>4^i</math> обновлений, а буфер слияния – отсортированный список из не более чем <math>4^i</math> обновлений. На каждом шаге можно принять обновление во входной буфер, потратить <math>O(4^i) = S(n)</math> времени на буфер сортировки и O(1) времени на слияние отсортированного списка в буфере слияния, при этом <math>O(4^i)</math> базовых разделителя находятся в интервале <math>[s_{i - 2}, s_{i + 1})</math> (предполагая <math>s_0 = 0, s_{-1} = - \infty)</math>, и сканирование на наличие нового <math>s_i</math> среди них. Данная реализация гарантирует, что все ключи в буферах разделителя <math>s_i</math> находятся в интервале <math>[s_{i - 2}, s_{i + 1})</math>. Таким образом, после <math>4^i</math> таких шагов цикла отсортированный список корректно слит с базовым списком, найдено новое значение <math>s_i</math> и создан новый отсортированный список. Затем буфер сортировки принимает на себя роль буфера слияния, входной буфер становится буфером сортировки, а пустой буфер слияния становится новым входным буфером.
'''Обработка обновлений''': при получении нового ключа обновления k (вставка или удаление) атомарная куча с верхними разделителями позволяет за время O(1) найти разделитель <math>s_i</math>, такой, что <math>k \in [s_{i - 1}, s_i)</math>. Если <math>k \in [s_0, s_1)</math>, определяется его положение среди O(1) базовых разделителей под <math>s_1</math>, и соответствующий базовый сегмент обновляется за время O(1) с использованием атомарной кучи над ключами этого сегмента. Если <math>k \in [s_{i - 1}, s_i)</math> для некоторого i > 1, обновление размещается во входном буфере <math>s_i</math>, выполняя один шаг цикла <math>s_i</math> за время S(n) + O(1). Кроме того, во время каждого обновления выбирается еще один разделитель <math>s_r</math> в порядке круговой очереди, и фрагмент (1/log n) шага цикла <math>s_r</math> выполняется за время O(1). Применение <math>s_r</math> гарантирует, что после каждых <math>O((log \; n)^2)</math> обновлений выполняется некоторое перемещение каждого верхнего разделителя.
Операция '''find-min''' возвращает минимальный элемент базового списка, доступный за время O(1).
'''Редукция в теореме 2'''
Данную редукцию можно получить из предыдущей редукции в результате замены всех атомарных куч системами буферов, разработанными для верхних разделителей.
'''Последующие улучшения'''
В работе [1] Алструп и др. представили редукцию общего вида, преобразующую очередь с приоритетами с поддержкой операции вставки за время O(1) с сохранением всех остальных границ. Эту редукцию можно использовать для снижения стоимости вставки до константной в теоремах 1 и 2.
== Применение ==
Доказательства эквивалентности, приведенные в [15], могут использоваться для перевода известных результатов сортировки в новые результаты для очередей с приоритетами для целых чисел и строк в различных вычислительных моделях (см. раздел. «Основные результаты»). Эти результаты также можно рассматривать как новые способы доказательства нижних границ для сортировки посредством очередей с приоритетами.
Новая очередь с приоритетами на RAM-машине, соответствующая приведенным в теореме 1 границам и поддерживающая операцию '''decrease-key''' за время O(1), представлена в работе [17]. Это построение сочетает экспоненциальные деревья поиска Андерссона [2] и очереди с приоритетами, упомянутые в теореме 1. Редукция в теореме 1 также использована в [12] для разработки адаптивного алгоритма сортировки целых чисел для пословной RAM-машины. Редукции из очередей с приоритетами, допускающих слияние, к сортировке, представленные в [11], используют редукции из очередей с приоритетами, не допускающих слияния, к сортировке, представленные в [15].
== Открытые вопросы ==
Как упоминалось выше, комбинаторная редукция для машин с указателями, приведенная в теореме 2, является более слабой, чем редукция для пословных RAM-машин. Например, для гипотетического алгоритма сортировки с линейным временем выполнения теорема 1 предлагает очередь с приоритетами с временем обновления O(1), а теорема 2 – с временем обновления <math>2^{O(log^* \; n)}</math>. Остается открытым вопрос о том, можно ли устранить или уменьшить этот разрыв.
== См. также ==
* [[Сортировка без явного задания параметров кэша]]
* [[Внешние сортировка и перестановка]]
* [[Сортировка строк]]
* [[Построение суффиксного дерева в RAM-модели]]
== Литература ==
1. Alstrup, S., Husfeldt, T., Rauhe, T., Thorup, M.: Black box for constant-time insertion in priority queues (note). ACM TALG 1(1),102-106(2005)
2. Andersson, A.: Faster deterministic sorting and searching in linear space. In: Proc. 37th FOCS, 1998, pp. 135-141
3. Andersson, A., Hagerup, T., Nilsson, S., Raman, R.: Sorting in linear time? J. Comp. Syst. Sci. 57, 74-93 (1998). Announced at STOC'95
4. Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge, MA (2001)
5. Fredman, M., Willard, D.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47, 424-436 (1993). Announced at STOC'90
6. Fredman, M., Willard, D.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48,533-551 (1994)
7. Fredman, M., Tarjan, R.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596-615(1987)
8. Han, Y.: Improved fast integer sorting in linear space. Inf. Comput. 170(8), 81-94 (2001). Announced at STACS'00 and SODA'01
9. Han, Y.: Deterministic sorting in O(nloglogn) time and linear space. J. Algorithms 50(1), 96-105 (2004). Announced at
STOC'02
10. Han, Y.,Thorup, M.: Integer sorting in O(nlog log n) expected time and linear space. In: Proc. 43rd FOCS, 2002, pp. 135-144
11. Mendelson, R., Tarjan, R., Thorup, M., Zwick, U.: Melding priority queues. ACM TALG 2(4), 535-556 (2006). Announced at SODA'04
12. Pagh, A., Pagh, R., Thorup, M.: On adaptive integer sorting. In: Proc. 12th ESA, 2004, pp. 556-579
13. Thorup, M.: Faster deterministic sorting and priority queues in linear space. In: Proc. 9th SODA, 1998, pp. 550-555
14. Thorup, M.: On RAM priority queues. SIAM J. Comput. 30(1), 86-109 (2000). Announced at SODA'96
15. Thorup, M.: Equivalence between priority queues and sorting. In: Proc. 43rd FOCS, 2002, pp. 125-134
16. Thorup, M.: Randomized sorting in O(nloglogn) time and linear space using addition, shift, and bit-wise boolean operations. J. Algorithms 42(2), 205-230 (2002). Announced at SODA'97
17. Thorup, M.: Integer priority queues with decrease key in constant time and the single source shortest paths problem. J. Comput. Syst. Sci. (special issue on STOC'03) 69(3), 330-353 (2004)
18. Vollmer, H.: Introduction to circuit complexity: a uniform approach. Springer, New York (1999)
19. Willard, D.: Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree. SIAM J. Comput. 29(3), 1030-1049 (2000). Announced at SODA'92
[[Категория: Совместное определение связанных терминов]]

Текущая версия от 11:21, 7 декабря 2024

Ключевые слова и синонимы

Куча

Постановка задачи

Очередь с приоритетами представляет собой абстрактную структуру данных, поддерживающую множество из Q элементов, каждому из которых присвоено значение, называемое ключом, а также следующий набор операций [4, 7].

insert(Q, x, k): вставка элемента x с ключом k в Q.

find-min(Q): возврат элемента Q с минимальным ключом; Q не изменяется.

delete(Q, x, k): удаление элемента x с ключом k из Q.


Помимо этого, нередко поддерживаются также следующие операции.

delete-min(Q): удаление элемента с минимальным ключом из Q и возврат измененного множества.

decrease-key(Q, x, k): уменьшение текущего ключа k' элемента x до k, предполагая, что k < k'.

meld([math]\displaystyle{ Q_1, Q_2 }[/math]): на входе очереди с приоритетами [math]\displaystyle{ Q_1 }[/math] и [math]\displaystyle{ Q_2 }[/math], на выходе – очередь с приоритетом [math]\displaystyle{ Q_1 \cup Q_2 }[/math].


Заметим, что операция delete-min может быть реализована как комбинация find-min и последующей delete, decrease-key – как delete с последующей insert, а meld – как серия find-min, delete и insert. Однако существуют и более эффективные реализации decrease-key и meld [4, 7].


Очереди с приоритетами широко применяются на практике, в том числе для событийного моделирования, планирования заданий на совместно используемом компьютере, а также вычисления кратчайших путей, минимальных остовных лесов, паросочетания с минимальной стоимостью, оптимального ветвления и т. п. [4, 7].


Очередь с приоритетами может тривиально использоваться для сортировки; для этого вначале необходимо вставить все подлежащие сортировке ключи в очередь и затем последовательно извлекать текущий минимальный ключ. Основным вкладом работы [15] является редукция, демонстрирующая, что обратное также верно. Из результатов работы [15] следует, что очереди с приоритетами вычислительно эквивалентны сортировке, а именно, что асимптотически стоимость сортировки в пересчете на ключ равна времени обновления очереди с приоритетами.


Аналогичный [15] результат, представленный в работе [14], представляет собой очереди с монотонными приоритетами (что означает, что извлекаемые минимальные значения являются неубывающими) с амортизированными временными границами. Напротив, очереди с приоритетами общего вида с границами для худшего случая были построены в [15].


Помимо установления эквивалентности между очередями с приоритетами и сортировкой, редукции в работе [15] также используются для преобразования нескольких известных результатов для сортировки в новые результаты для очередей с приоритетами.


Контекст и история

Нижеследующая информация будет полезной для более полного понимания результатов, приведенных в разделе «Основные результаты».

• Стандартная пословная RAM-машина моделирует ход выполнения программы, написанной на стандартном языке программирования, таком как С. Помимо прямой и косвенной адресации и условных переходов, программа может содержать функции (например, сложение и умножение), выполняемые над константным количеством слов. Память разделена на два слова с линейной адресацией, начинающейся с 0. Время выполнения программы равно количеству выполненных команд, а объем памяти – номеру максимального использованного адреса. Длина слова представляет собой машинно-зависимый параметр, достаточно большой для хранения ключа, и является по меньшей мере логарифмической относительно количества входных ключей, что обеспечивает возможность их адресации.

• Машина с указателями аналогична пословной RAM-машине за тем исключением, что с адресами нельзя производить какие-либо действия.

• Класс сложности [math]\displaystyle{ AC^0 }[/math] включает схемы константной глубины с неограниченным коэффициентом разветвления по входу [18]. Под стандартными операциями [math]\displaystyle{ AC^0 }[/math] понимаются операции, доступные в C, такие, что функции над словами принадлежат к [math]\displaystyle{ AC^0 }[/math]. К примеру, в их число входит сложение, но не умножение.

• Целочисленные ключи ссылаются на неотрицательные целые числа. Если же входные ключи представляют собой целые числа со знаком, корректный порядок ключей можно получить в результате переключения битов, содержащих знаки, и интерпретации их как беззнаковых целых чисел. Аналогичные действия можно произвести для чисел с плавающей запятой и дробных чисел [14].

• Атомарные кучи Фредмана и Уилларда [6] использовались в одной из редукций в работе [15]. Такие кучи способны поддерживать операции обновления и поиска в множествах из [math]\displaystyle{ O(log^2 \; n) }[/math] ключей за время O(1) в худшем случае [19]. Однако атомарные кучи используют операции умножения, не принадлежащие к [math]\displaystyle{ AC^0 }[/math].

Основные результаты

Основными результатами являются две редукции из очередей с приоритетами к сортировке. Более сильная из этих редукций, изложенная в теореме 1, касается целочисленных очередей с приоритетами, выполняющихся на стандартной пословной RAM-машине.


Теорема 1. Если для некоторой неубывающей функции S до n целочисленных ключей могут быть отсортированы за время S(n) на ключ, целочисленная очередь с приоритетами может быть реализована с поддержкой операции find-min за константное время и операций обновления, т. е. вставки и удаления, за время S(n) + O(1). Здесь n равно текущему количеству ключей в очереди. Редукция использует линейный объем памяти и выполняется на стандартной пословной RAM-машине, на которой каждый целочисленный ключ хранится в одном слове.


Вышеприведенная редукция задает новые границы для линейных требований к объему памяти для целочисленных очередей с приоритетами, улучшая предыдущие границы, представленные в работах [8, 14] и [5], соответственно.

1. (Детерминированный случай) время обновления O(log log n) при помощи алгоритма сортировки из [9].

2. (Рандомизированный) ожидаемое время обновления [math]\displaystyle{ O(\sqrt{log \; log \; n}) }[/math] при помощи алгоритма сортировки из [10].

3. (Рандомизированный с выполнением операции decrease-key за время O(1)) ожидаемое время обновления [math]\displaystyle{ O \Big( (log \; n)^{\frac{1}{2 - \epsilon}} \Big) }[/math] для слов длиной, больше или равной log n, и любого константного [math]\displaystyle{ \epsilon \gt 0 }[/math] при помощи алгоритма сортировки из [3].


Редукция из теоремы 1 использует атомарные кучи [6], которые мало того что очень сложны сами по себе, но к тому же используют операции, не входящие в [math]\displaystyle{ AC^0 }[/math]. Следующая, несколько более слабая рекурсивная редукция, не ограничивающая область определения ключей, является полностью комбинаторной.


Теорема 2. Пусть дана программа сортировки, выполняющая сортировку до n ключей за время S(n) на ключ. Очередь с приоритетами может быть реализована с поддержкой операции find-min за константное время и операций обновления – за время T(n), где n – текущее количество ключей в очереди, а T(n) удовлетворяет следующему условию рекуррентности:

[math]\displaystyle{ T(n) = O(S(n) + T(log^2 \; n)) }[/math]

Редукция выполняется на машине с указателями с использованием линейного объема памяти и только стандартными операциями из [math]\displaystyle{ AC^0 }[/math]. Обращения к значениям ключей производятся только программой сортировки.


Данная редукция обеспечивает следующие новые границы для очередей с приоритетами, не поддерживаемые теоремой 1, причем первые две позиции улучшают предыдущие границы, представленные в работах [13] и [16], соответственно.

1. (Детерминированный для стандартного алгоритма класса сложности [math]\displaystyle{ AC^0 }[/math]) время обновления [math]\displaystyle{ O((log \; log \; n)^{1 + \epsilon}) }[/math] для любого константного [math]\displaystyle{ \epsilon \gt 0 }[/math] при помощи стандартного алгоритма сортировки целых чисел класса [math]\displaystyle{ AC^0 }[/math] из работы [10].

2. (Рандомизированный для стандартного алгоритма [math]\displaystyle{ AC^0 }[/math]) ожидаемое время обновления O(log log n) при помощи стандартного алгоритма сортировки целых чисел класса [math]\displaystyle{ AC^0 }[/math] из работы [16].

3. (Строки из [math]\displaystyle{ l }[/math] слов) ожидаемое время обновления [math]\displaystyle{ O(l + log \; log \; n) }[/math] для детерминированного и [math]\displaystyle{ O(l + \sqrt{log \; log \; n}) }[/math] – для рандомизированного случая при помощи алгоритма сортировки строк из [10].


Редукция в теореме 1

Пусть дана процедура сортировки, выполняющая сортировку до n ключей за время S(n) на ключ. Очередь с приоритетами строится следующим образом.


Структура данных состоит из двух основных компонентов: отсортированного списка ключей и множества буферов обновления. Список ключей разбит на два небольших сегмента, каждый из которых поддерживается в виде атомарной кучи, обеспечивающей константное время выполнения операций обновления и поиска на этом сегменте. Каждый буфер обновления имеет разную емкость и поддерживает обновления (вставка / удаление) со значениями ключей в разных диапазонах. Буферы меньшей емкости предназначены для обновления с ключами меньшей величины. Атомарная куча используется для определения за константное время того, какой буфер обновления содержит новое обновление. Когда буфер обновления соберет достаточно обновлений, они вначале проходят этап сортировки, а затем – этап слияния. На этапе слияния каждое обновление применяется к соответствующему сегменту списка ключей, а также фиксируются инварианты размеров сегментов и диапазонов буферов обновления. Эти этапы выполняются не немедленно, а в фиксированные временные отрезки в рамках общего периода времени. Буфер обновления продолжает принимать новые обновления, при этом некоторые ранее принятые им обновления все еще могут находиться на этапе сортировки, а некоторые более поздние – на этапе слияния. При получении каждого нового обновления на связанном с ним этапе сортировки на него тратится S(n) времени, а на этапе слияния – O(1) времени. Эта стратегия позволяет доводить этапы сортировки и слияния до завершения к моменту очередного заполнения буфера обновления, обеспечивая плавность прохождения обновлениями нужных этапов и сохраняя время обновления S(n) + O(1) в худшем случае. Кроме того, ограничения на размер и емкость гарантируют, что даже самый маленький ключ в структуре данных доступен за время O(1). Далее изложим эту технологию более подробно.


Отсортированный список ключей: отсортированный список содержит большинство ключей в структуре данных, в том числе минимальный ключ, и называется базовым списком. Этот список разбит на базовые сегменты, каждый из которых содержит [math]\displaystyle{ \Theta((log \; n)^2) }[/math] ключей. Ключи в каждом сегменте поддерживаются в виде атомарной кучи, так что если становится известно, что новое обновление должно быть применено к конкретному сегменту, оно может быть применено за время O(1). Если базовый сегмент становится слишком большим или слишком маленьким, он разбивается на две части либо объединяется со смежным сегментом.


Буферы обновления: базовые сегменты отделяются друг от друга базовыми разделителями, из которых O(log n) выбираются в качестве верхних разделителей, так что количество ключей в базовом списке под i-м (i > 0) верхним разделителем [math]\displaystyle{ s_i }[/math] составляет [math]\displaystyle{ \Theta (4^i(log \; n)^2) }[/math]. Эти разделители располагаются в атомарной куче. По мере изменений базового списка верхние разделители перемещаются по необходимости с тем, чтобы сохранить их экспоненциальное распределение.


С каждым верхним разделителем [math]\displaystyle{ s_i }[/math], i > 1, ассоциированы три буфера: входной буфер, буфер сортировки и буфер слияния, каждый емкостью в [math]\displaystyle{ 4^i }[/math] ключа. Верхний разделитель [math]\displaystyle{ s_i }[/math] работает по циклу, состоящему из [math]\displaystyle{ 4^i }[/math] шагов. В начале цикла входной буфер пуст, буфер сортировки содержит не более [math]\displaystyle{ 4^i }[/math] обновлений, а буфер слияния – отсортированный список из не более чем [math]\displaystyle{ 4^i }[/math] обновлений. На каждом шаге можно принять обновление во входной буфер, потратить [math]\displaystyle{ O(4^i) = S(n) }[/math] времени на буфер сортировки и O(1) времени на слияние отсортированного списка в буфере слияния, при этом [math]\displaystyle{ O(4^i) }[/math] базовых разделителя находятся в интервале [math]\displaystyle{ [s_{i - 2}, s_{i + 1}) }[/math] (предполагая [math]\displaystyle{ s_0 = 0, s_{-1} = - \infty) }[/math], и сканирование на наличие нового [math]\displaystyle{ s_i }[/math] среди них. Данная реализация гарантирует, что все ключи в буферах разделителя [math]\displaystyle{ s_i }[/math] находятся в интервале [math]\displaystyle{ [s_{i - 2}, s_{i + 1}) }[/math]. Таким образом, после [math]\displaystyle{ 4^i }[/math] таких шагов цикла отсортированный список корректно слит с базовым списком, найдено новое значение [math]\displaystyle{ s_i }[/math] и создан новый отсортированный список. Затем буфер сортировки принимает на себя роль буфера слияния, входной буфер становится буфером сортировки, а пустой буфер слияния становится новым входным буфером.


Обработка обновлений: при получении нового ключа обновления k (вставка или удаление) атомарная куча с верхними разделителями позволяет за время O(1) найти разделитель [math]\displaystyle{ s_i }[/math], такой, что [math]\displaystyle{ k \in [s_{i - 1}, s_i) }[/math]. Если [math]\displaystyle{ k \in [s_0, s_1) }[/math], определяется его положение среди O(1) базовых разделителей под [math]\displaystyle{ s_1 }[/math], и соответствующий базовый сегмент обновляется за время O(1) с использованием атомарной кучи над ключами этого сегмента. Если [math]\displaystyle{ k \in [s_{i - 1}, s_i) }[/math] для некоторого i > 1, обновление размещается во входном буфере [math]\displaystyle{ s_i }[/math], выполняя один шаг цикла [math]\displaystyle{ s_i }[/math] за время S(n) + O(1). Кроме того, во время каждого обновления выбирается еще один разделитель [math]\displaystyle{ s_r }[/math] в порядке круговой очереди, и фрагмент (1/log n) шага цикла [math]\displaystyle{ s_r }[/math] выполняется за время O(1). Применение [math]\displaystyle{ s_r }[/math] гарантирует, что после каждых [math]\displaystyle{ O((log \; n)^2) }[/math] обновлений выполняется некоторое перемещение каждого верхнего разделителя.


Операция find-min возвращает минимальный элемент базового списка, доступный за время O(1).


Редукция в теореме 2

Данную редукцию можно получить из предыдущей редукции в результате замены всех атомарных куч системами буферов, разработанными для верхних разделителей.


Последующие улучшения

В работе [1] Алструп и др. представили редукцию общего вида, преобразующую очередь с приоритетами с поддержкой операции вставки за время O(1) с сохранением всех остальных границ. Эту редукцию можно использовать для снижения стоимости вставки до константной в теоремах 1 и 2.

Применение

Доказательства эквивалентности, приведенные в [15], могут использоваться для перевода известных результатов сортировки в новые результаты для очередей с приоритетами для целых чисел и строк в различных вычислительных моделях (см. раздел. «Основные результаты»). Эти результаты также можно рассматривать как новые способы доказательства нижних границ для сортировки посредством очередей с приоритетами.


Новая очередь с приоритетами на RAM-машине, соответствующая приведенным в теореме 1 границам и поддерживающая операцию decrease-key за время O(1), представлена в работе [17]. Это построение сочетает экспоненциальные деревья поиска Андерссона [2] и очереди с приоритетами, упомянутые в теореме 1. Редукция в теореме 1 также использована в [12] для разработки адаптивного алгоритма сортировки целых чисел для пословной RAM-машины. Редукции из очередей с приоритетами, допускающих слияние, к сортировке, представленные в [11], используют редукции из очередей с приоритетами, не допускающих слияния, к сортировке, представленные в [15].

Открытые вопросы

Как упоминалось выше, комбинаторная редукция для машин с указателями, приведенная в теореме 2, является более слабой, чем редукция для пословных RAM-машин. Например, для гипотетического алгоритма сортировки с линейным временем выполнения теорема 1 предлагает очередь с приоритетами с временем обновления O(1), а теорема 2 – с временем обновления [math]\displaystyle{ 2^{O(log^* \; n)} }[/math]. Остается открытым вопрос о том, можно ли устранить или уменьшить этот разрыв.

См. также

Литература

1. Alstrup, S., Husfeldt, T., Rauhe, T., Thorup, M.: Black box for constant-time insertion in priority queues (note). ACM TALG 1(1),102-106(2005)

2. Andersson, A.: Faster deterministic sorting and searching in linear space. In: Proc. 37th FOCS, 1998, pp. 135-141

3. Andersson, A., Hagerup, T., Nilsson, S., Raman, R.: Sorting in linear time? J. Comp. Syst. Sci. 57, 74-93 (1998). Announced at STOC'95

4. Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge, MA (2001)

5. Fredman, M., Willard, D.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47, 424-436 (1993). Announced at STOC'90

6. Fredman, M., Willard, D.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48,533-551 (1994)

7. Fredman, M., Tarjan, R.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596-615(1987)

8. Han, Y.: Improved fast integer sorting in linear space. Inf. Comput. 170(8), 81-94 (2001). Announced at STACS'00 and SODA'01

9. Han, Y.: Deterministic sorting in O(nloglogn) time and linear space. J. Algorithms 50(1), 96-105 (2004). Announced at STOC'02

10. Han, Y.,Thorup, M.: Integer sorting in O(nlog log n) expected time and linear space. In: Proc. 43rd FOCS, 2002, pp. 135-144

11. Mendelson, R., Tarjan, R., Thorup, M., Zwick, U.: Melding priority queues. ACM TALG 2(4), 535-556 (2006). Announced at SODA'04

12. Pagh, A., Pagh, R., Thorup, M.: On adaptive integer sorting. In: Proc. 12th ESA, 2004, pp. 556-579

13. Thorup, M.: Faster deterministic sorting and priority queues in linear space. In: Proc. 9th SODA, 1998, pp. 550-555

14. Thorup, M.: On RAM priority queues. SIAM J. Comput. 30(1), 86-109 (2000). Announced at SODA'96

15. Thorup, M.: Equivalence between priority queues and sorting. In: Proc. 43rd FOCS, 2002, pp. 125-134

16. Thorup, M.: Randomized sorting in O(nloglogn) time and linear space using addition, shift, and bit-wise boolean operations. J. Algorithms 42(2), 205-230 (2002). Announced at SODA'97

17. Thorup, M.: Integer priority queues with decrease key in constant time and the single source shortest paths problem. J. Comput. Syst. Sci. (special issue on STOC'03) 69(3), 330-353 (2004)

18. Vollmer, H.: Introduction to circuit complexity: a uniform approach. Springer, New York (1999)

19. Willard, D.: Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree. SIAM J. Comput. 29(3), 1030-1049 (2000). Announced at SODA'92