4430
правок
Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями
Материал из WEGA
Эквивалентность между очередями с приоритетами и сортировкой (посмотреть исходный код)
Версия от 14:37, 6 февраля 2019
, 6 февраля 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 51: | Строка 51: | ||
== Основные результаты == | == Основные результаты == | ||
Основными результатами являются две редукции из очередей с приоритетами к сортировке. Более сильная из этих редукций, изложенная в теореме 1, касается целочисленных очередей с приоритетами, выполняющихся на стандартной пословной RAM-машине. | |||
Теорема 1. Если для некоторой неубывающей функции S до n целочисленных ключей могут быть отсортированы за время S(n) на ключ, целочисленная очередь с приоритетами может быть реализована с поддержкой операции find-min за константное время и операций обновления, т. е. вставки и удаления, за время S(n) + O(1). Здесь n равно текущему количеству ключей в очереди. Редукция использует линейный объем памяти и выполняется на стандартной пословной RAM-машине, на которой каждый целочисленный ключ хранится в одном слове. | |||
Вышеприведенная редукция задает новые границы для линейных требований к объему памяти для целочисленных очередей с приоритетами, улучшая предыдущие границы, представленные в работах [8, 14] и [5], соответственно. | |||
1. (Детерминированный) время обновления O(loglog n) при помощи алгоритма сортировки из [ ]. | |||
2. (Рандомизированный) ожидаемое время обновления O(loglog n) при помощи алгоритма сортировки из [10]. | |||
3. (Рандомизированный с выполнением операции decrease-key за время O(1)) ожидаемое время обновления O I (log n) <2~e) ) для слов длиной > log n и любого константного e > 0 при помощи алгоритма сортировки из [3]. | |||
Редукция из теоремы 1 использует атомарные кучи [6], которые мало того что очень сложны сами по себе, но к тому же используют операции, не входящие в AC0. Следующая, несколько более слабая рекурсивная редукция, не ограничивающая область определения ключей, является полностью комбинаторной. | |||
Теорема 2. Пусть дана программа сортировки, выполняющая сортировку до n ключей за время S(n) на ключ. Очередь с приоритетами может быть реализована с поддержкой операции find-min за константное время и операций обновления – за время T(n), где n – текущее количество ключей в очереди, а T(n) удовлетворяет следующему условию рекуррентности: | |||
T(n) = O (S(n) + T(log2 и)) : | |||
Редукция выполняется на машине с указателями с использованием линейного объема памяти и только стандартными операциями из AC0. Обращения к значениям ключей производятся только программой сортировки. | |||
Данная редукция обеспечивает следующие новые границы для очередей с приоритетами, не поддерживаемые теоремой 1, причем первые две позиции улучшают предыдущие границы, представленные в работах [ ] и [16], соответственно. | |||
1. (Детерминированный для стандартного алгоритма класса сложности AC0) время обновления O ((log log n)1+е) для любого константного e > 0 при помощи стандартного алгоритма сортировки целых чисел класса AC0 из работы [10]. | |||
2. (Рандомизированный для стандартного алгоритма AC0) ожидаемое время обновления O (log log n) при помощи стандартного алгоритма сортировки целых чисел класса AC0 из работы [16]. | |||
3. (Строки из 1 слова) ожидаемое время обновления O(l + loglog n) для детерминированного и O l + ploglog n – для рандомизированного случая при помощи алгоритма сортировки строк из [10]. | |||
'''Редукция в теореме 1''' | |||
Пусть дана процедура сортировки, выполняющая сортировку до n ключей за время S(n) на ключ. Очередь с приоритетами строится следующим образом. | |||
Структура данных состоит из двух основных компонентов: отсортированного списка ключей и множества буферов обновления. Список ключей разбит на два небольших сегмента, каждый из которых поддерживается в виде атомарной кучи, обеспечивающей константное время выполнения операций обновления и поиска на этом сегменте. Каждый буфер обновления имеет разную емкость объем и поддерживает обновления (вставка / удаление) со значениями ключей в разных диапазонах. Буферы меньшей емкости предназначены для обновления ключей меньшей величины. Атомарная куча используется для определения за константное время того, какой буфер обновления содержит новое обновление. Когда буфер обновления соберет достаточно обновлений, они вначале проходят этап сортировки, а затем – этап слияния. На этапе слияния каждое обновление применяется к соответствующему сегменту списка ключей, а также фиксируются инварианты размеров сегментов и диапазонов буферов обновления. Эти этапы выполняются не немедленно, а в фиксированные временные отрезки в рамках общего периода времени. Буфер обновления продолжает принимать новые обновления, при этом некоторые ранее принятые им обновления все еще могут находиться на этапе сортировки, а некоторые более поздние – на этапе слияния. При получении каждого нового обновления на связанном с ним этапе сортировки на него тратится S(n) времени, а на этапе слияния – O(1) времени. Эта стратегия позволяет доводить этапы сортировки и слияния до завершения к моменту очередного заполнения буфера обновления, обеспечивая плавность прохождения обновлениями нужных этапов и сохраняя время обновления S(n) + O(1) в худшем случае. Кроме того, ограничения на размер и емкость гарантируют, что даже самый маленький ключ в структуре данных доступен за время O(1). Далее изложим эту технологию более подробно. | |||
'''Отсортированный список ключей''': | |||
