4522
правки
Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями
Материал из WEGA
Эквивалентность между очередями с приоритетами и сортировкой (посмотреть исходный код)
Версия от 13:47, 18 февраля 2019
, 18 февраля 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 78: | Строка 78: | ||
Данная редукция обеспечивает следующие новые границы для очередей с приоритетами, не поддерживаемые теоремой 1, причем первые две позиции улучшают предыдущие границы, представленные в работах [13] и [16], соответственно. | Данная редукция обеспечивает следующие новые границы для очередей с приоритетами, не поддерживаемые теоремой 1, причем первые две позиции улучшают предыдущие границы, представленные в работах [13] и [16], соответственно. | ||
1. ('''Детерминированный для стандартного алгоритма класса сложности <math>AC^0</math>''') время обновления <math>O((log \; log \; n)^{1 + \epsilon})</math> для любого константного <math>\epsilon > 0</math> | 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]. | 2. ('''Рандомизированный для стандартного алгоритма <math>AC^0</math>''') ожидаемое время обновления O(log log n) при помощи стандартного алгоритма сортировки целых чисел класса <math>AC^0</math> из работы [16]. | ||
3. ('''Строки из l слов''') ожидаемое время обновления O(l + log log n) для детерминированного и <math>O(l + \sqrt{log \; log \; n})</math> – для рандомизированного случая при помощи алгоритма сортировки строк из [10]. | 3. ('''Строки из <math>l</math> слов''') ожидаемое время обновления <math>O(l + log \; log \; n)</math> для детерминированного и <math>O(l + \sqrt{log \; log \; n})</math> – для рандомизированного случая при помощи алгоритма сортировки строк из [10]. | ||
| Строка 90: | Строка 90: | ||
Структура данных состоит из двух основных компонентов: отсортированного списка ключей и множества буферов обновления. Список ключей разбит на два небольших сегмента, каждый из которых поддерживается в виде атомарной кучи, обеспечивающей константное время выполнения операций обновления и поиска на этом сегменте. Каждый буфер обновления имеет разную емкость | Структура данных состоит из двух основных компонентов: отсортированного списка ключей и множества буферов обновления. Список ключей разбит на два небольших сегмента, каждый из которых поддерживается в виде атомарной кучи, обеспечивающей константное время выполнения операций обновления и поиска на этом сегменте. Каждый буфер обновления имеет разную емкость и поддерживает обновления (вставка / удаление) со значениями ключей в разных диапазонах. Буферы меньшей емкости предназначены для обновления с ключами меньшей величины. Атомарная куча используется для определения за константное время того, какой буфер обновления содержит новое обновление. Когда буфер обновления соберет достаточно обновлений, они вначале проходят этап сортировки, а затем – этап слияния. На этапе слияния каждое обновление применяется к соответствующему сегменту списка ключей, а также фиксируются инварианты размеров сегментов и диапазонов буферов обновления. Эти этапы выполняются не немедленно, а в фиксированные временные отрезки в рамках общего периода времени. Буфер обновления продолжает принимать новые обновления, при этом некоторые ранее принятые им обновления все еще могут находиться на этапе сортировки, а некоторые более поздние – на этапе слияния. При получении каждого нового обновления на связанном с ним этапе сортировки на него тратится S(n) времени, а на этапе слияния – O(1) времени. Эта стратегия позволяет доводить этапы сортировки и слияния до завершения к моменту очередного заполнения буфера обновления, обеспечивая плавность прохождения обновлениями нужных этапов и сохраняя время обновления S(n) + O(1) в худшем случае. Кроме того, ограничения на размер и емкость гарантируют, что даже самый маленький ключ в структуре данных доступен за время O(1). Далее изложим эту технологию более подробно. | ||
