Burstsort и его варианты — это кэш-эффективные алгоритмы для сортировки строк . Они являются вариантами традиционной радиксной сортировки , но быстрее для больших наборов данных общих строк, впервые опубликованных в 2003 году, с некоторыми оптимизирующими версиями, опубликованными в более поздние годы. [1]
Алгоритмы пакетной сортировки используют trie для хранения префиксов строк с растущими массивами указателей в качестве конечных узлов, содержащих отсортированные уникальные суффиксы (называемые сегментами ). Некоторые варианты копируют хвосты строк в сегменты. По мере того, как сегменты превышают заданный порог, сегменты «разбиваются» на попытки, что и дало сортировке ее название. Более поздний вариант использует индекс сегмента с меньшими подсекционными сегментами для сокращения использования памяти. Большинство реализаций делегируют многоключевой быстрой сортировке, расширению трехсторонней радикальной быстрой сортировки, для сортировки содержимого сегментов. Разделив входные данные на сегменты с общими префиксами, сортировка может быть выполнена эффективным с точки зрения кэширования способом.
Burstsort была введена как сортировка , похожая на сортировку MSD radix [1], но она быстрее из-за того, что учитывает кэширование и связанные с ним основания, хранящиеся ближе друг к другу из-за специфики структуры trie. Она использует специфику строк, которые обычно встречаются в реальном мире. И хотя асимптотически она такая же, как сортировка radix, со сложностью O ( wn ) ( w – длина слова и n – количество строк для сортировки), но из-за лучшего распределения памяти она имеет тенденцию быть в два раза быстрее на больших наборах данных строк. Она была объявлена «самым быстрым известным алгоритмом для сортировки больших наборов строк». [2]
Ссылки
- ^ ab Sinha, R.; Zobel, J. (2005). "Кэш-ориентированная сортировка больших наборов строк с динамическими попытками" (PDF) . Журнал экспериментальной алгоритмики . 9 : 1.5. CiteSeerX 10.1.1.599.861 . doi :10.1145/1005813.1041517. S2CID 10807318.
- ^ «Burstsort: Самый быстрый известный алгоритм сортировки большого набора строк | Hacker News».
- Производная сортировки с помощью burstsort (C-burstsort), быстрее, чем burstsort: Sinha, Ranjan; Zobel, Justin; Ring, David (январь 2006 г.). "Cache-Efficient String Sorting Using Copying" (PDF) . Journal of Experimental Algorithmics . 11 (1.2): 1.2. CiteSeerX 10.1.1.85.3498 . doi :10.1145/1187436.1187439. S2CID 3184411. Архивировано из оригинала (PDF) 2007-10-01 . Получено 2007-05-31 .
- Тип данных, используемый в burstsort: Heinz, Steffen; Zobel, Justin; Williams, Hugh E. (апрель 2002 г.). "Burst Tries: A Fast, Efficient Data Structure for String Keys" (PDF) . ACM Transactions on Information Systems . 20 (2): 192–223. CiteSeerX 10.1.1.18.3499 . doi :10.1145/506309.506312. S2CID 14122377. Архивировано из оригинала (PDF) 2013-12-05 . Получено 2007-09-25 .
- Синха, Ранджан; Зобель, Джастин (2003). "Эффективная сортировка больших наборов строк на основе префиксных таблиц" (PDF) . Труды 26-й Австралазийской конференции по информатике . Том 16. С. 11–18. CiteSeerX 10.1.1.12.2757 . ISBN 978-0-909-92594-9. Архивировано из оригинала (PDF) 2012-02-08 . Получено 2007-09-25 .
- Синха, Ранджан; Вирт, Энтони (март 2010 г.). «Инженерная пакетная сортировка: на пути к быстрой сортировке строк на месте» (PDF) . ACM Journal of Experimental Algorithmics . 15 (2.5): 1–24. doi :10.1145/1671970.1671978. S2CID 16410080.
Внешние ссылки
- Реализация burstsort на Java: burstsort4j
- Массивы Джуди — это тип сортировки методом копирования с пакетной сортировкой: реализация на языке C
