4430
правок
Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями
Материал из WEGA
Эквивалентность между очередями с приоритетами и сортировкой (посмотреть исходный код)
Версия от 13:42, 7 февраля 2019
, 7 февраля 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 93: | Строка 93: | ||
'''Отсортированный список ключей''': | '''Отсортированный список ключей''': отсортированный список содержит большинство ключей в структуре данных, в том числе минимальный ключ, и называется базовым списком. Этот список разбит на базовые сегменты, каждый из которых содержит ©((log n)2) ключей. Ключи в каждом сегменте поддерживаются в виде атомарной кучи, так что если становится известно, что новое обновление должно быть применено к конкретному сегменту, оно может быть применено за время O(1). Если базовый сегмент становится слишком большим или слишком маленьким, он разбивается на две части либо объединяется со смежным сегментом. | ||
'''Буферы обновления''': базовые сегменты отделяются друг от друга базовыми разделителями, из которых O(log n) выбираются в качестве верхних разделителей, так что количество ключей в базовом списке под i-м верхним разделителем (i > 0) составляет & (4'(log и)2). Эти разделители располагаются а атомарной куче. По мере изменений базового списка верхние разделители перемещаются по необходимости с тем, чтобы сохранить их экспоненциальное распределение. | |||
С каждым верхним разделителем si, i > 1, ассоциированы три буфера: входной буфер, буфер сортировки и буфер слияния, каждый емкостью в 4i ключа. Верхний разделитель si работает по циклу, состоящему из 4i шагов. В начале цикла входной буфер пуст, буфер сортировки содержит не более 4i обновлений, а буфер слияния – отсортированный список из не более чем 4i обновлений. На каждом этапе можно принять обновление во входной буфер, потратить O(4i) = S(n) времени на буфер сортировки и O(1) времени на слияние отсортированного списка в буфере слияния, в то время как O(4i) базовых разделителя находятся в интервале [s,_2,s;+i) (предполагая s0 = 0, s-i = — oo), и сканирование на наличие нового si среди них. Данная реализация гарантирует, что все ключи в буферах разделителя si находятся в интервале [s,_2; si+1). Таким образом, после 4i таких шагов цикла отсортированный список корректно слит с базовым списком, найдено новое значение si и создан новый отсортированный список. Затем буфер сортировки принимает на себя роль буфера слияния, входной буфер становится буфером сортировки, а пустой буфер слияния становится новым входным буфером. | |||
'''Обработка обновлений''': при получении нового ключа обновления k (вставка или удаление) атомарная куча с верхними разделителями позволяет за время O(1) найти разделитель si, такой, что k 2 [s,_i,s,). Если к 2 [S0;S1), его положение определяется между O(1) базовыми разделителями под s1, и соответствующий базовый сегмент обновляется за время O(1) с использованием атомарной кучи над ключами этого сегмента. Если k 2 [s,-_i, si) для некоторого i > 1, обновление размещается во входном буфере si, выполняя один шаг цикла si за время S(n) + O(1). Кроме того, во время каждого обновления выбирается еще один разделитель sr в порядке круговой очереди, и фрагмент 1/log n шага цикла sr выполняется за время O(1). Работа с sr гарантирует, что после каждых O((log n)2) обновлений выполняется некоторое перемещение каждого верхнего разделителя. | |||
Операция find-min возвращает минимальный элемент базового списка, доступный за время O(1). | |||
'''Редукция в теореме 2''' | |||
Данную редукцию можно получить из предыдущей редукции в результате замены всех атомарных куч системами буферов, разработанными для верхних разделителей. | |||
'''Последующие улучшения''' | |||
В работе [1] Алструп и др. представили редукцию общего вида, преобразующую очередь с приоритетами с поддержкой операции вставки за время O(1) с сохранением всех остальных границ. Эту редукцию можно использовать для снижения стоимости вставки до константной в теоремах 1 и 2. | |||
== Применение == | |||
Доказательства эквивалентности, приведенные в [ ], могут использоваться для перевода известных результатов сортировки в новые результаты для очередей с приоритетами для целых чисел и строк в различных вычислительных моделях (см. раздел. «Основные результаты»). Эти результате также можно рассматривать как новые способы доказательства нижних границ для сортировки посредством очередей с приоритетами. | |||
Новая очередь с приоритетами на RAM-машине, соответствующая приведенным в теореме 1 границам и поддерживающая операцию decrease-key за время O(1), представлена в работе [ ]. Это построение сочетает экспоненциальные деревья поиска Андерссона [ ] и очереди с приоритетами, упомянутые в теореме 1. Редукция в теореме 1 также использована в [12] для разработки адаптивного алгоритма сортировки целых чисел для пословной RAM-машины. Редукции из очередей с приоритетами, допускающих слияние, к сортировке, представленные в [11], используют редукции из очередей с приоритетами, не допускающих слияния, к сортировке, представленные в [15]. | |||
== Открытые вопросы == | |||
Как упоминалось выше, комбинаторная редукция для машин с указателями, приведенная в теореме 2, является более слабой, чем редукция для пословных RAM-машин. Например, для гипотетического алгоритма сортировки с линейным временем выполнения теорема 1 предлагает очередь с приоритетами с временем обновления O(1), а теорема Theorem – с временем обновления 2O(log "•'. Остается открытым вопрос о том, можно ли устранить или уменьшить этот разрыв. | |||
== См. также == | |||
* [[Сортировка без явного задания параметров кэша]] | |||
* [[Внешние сортировка и перестановка]] | |||
* [[Сортировка строк]] | |||
* [[Построение суффиксного дерева в 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 | |||
