Пакетная сортировка
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( Июль 2017 г. ) |
| Сорт | Алгоритм сортировки |
|---|---|
| Структура данных | Три |
| Худшая производительность | Собственный ) |
| Наихудшая пространственная сложность | Собственный ) |
| Оптимальный | ? |
Пакетная сортировка и ее варианты — это эффективные кеш-алгоритмы сортировки строк . Это варианты традиционной поразрядной сортировки , но более быстрые для больших наборов данных общих строк. Впервые они были опубликованы в 2003 году, а в последующие годы были опубликованы некоторые оптимизирующие версии. [1]
Алгоритмы пакетной сортировки используют дерево для хранения префиксов строк с растущими массивами указателей в качестве конечных узлов, содержащих отсортированные уникальные суффиксы (называемые сегментами ). Некоторые варианты копируют хвосты строк в ведра. Когда сегменты выходят за пределы заранее определенного порога, они «разбиваются» на попытки, что и дает сорту свое название. В более позднем варианте используется индекс сегмента с меньшими подсегментами для уменьшения использования памяти. В большинстве реализаций для сортировки содержимого сегментов используется быстрая многоключевая сортировка, расширение трехсторонней поразрядной быстрой сортировки. Разделив входные данные на сегменты с общими префиксами, сортировку можно выполнить эффективно с точки зрения кэширования.
Пакетная сортировка была представлена как сортировка, похожая на поразрядную сортировку MSD . [1] но быстрее из-за того, что известно о кэшировании и связанных с ним системах счисления, которые хранятся ближе друг к другу из-за особенностей структуры дерева. Он использует особенности строк, которые обычно встречаются в реальном мире. И хотя асимптотически это то же самое, что поразрядная сортировка, с временной сложностью O ( wn ) ( w — длина слова и n — количество сортируемых строк), но из-за лучшего распределения памяти она имеет тенденцию быть в два раза быстрее на больших объемах. наборы данных строк. Он был объявлен «самым быстрым из известных алгоритмов сортировки больших наборов строк». [2]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б Синха, Р.; Зобель, Дж. (2005). «Сортировка больших наборов строк с учетом кэша с динамическими попытками» (PDF) . Журнал экспериментальной алгоритмики . 9 :1,5. CiteSeerX 10.1.1.599.861 . дои : 10.1145/1005813.1041517 . S2CID 10807318 .
- ^ «Пакетная сортировка: самый быстрый из известных алгоритмов для сортировки большого набора строк | Hacker News» .
- Производная пакетной сортировки (C-burstsort), более быстрая, чем пакетная сортировка: Синха, Ранджан; Зобель, Джастин; Ринг, Дэвид (январь 2006 г.). «Эффективная сортировка строк с использованием копирования» (PDF) . Журнал экспериментальной алгоритмики . 11 (1.2): 1.2. CiteSeerX 10.1.1.85.3498 . дои : 10.1145/1187436.1187439 . S2CID 3184411 . Архивировано из оригинала (PDF) 1 октября 2007 г. Проверено 31 мая 2007 г.
- Тип данных, используемый при пакетной сортировке: Хайнц, Штеффен; Зобель, Джастин; Уильямс, Хью Э. (апрель 2002 г.). «Пакетные попытки: быстрая и эффективная структура данных для строковых ключей» (PDF) . Транзакции ACM в информационных системах . 20 (2): 192–223. CiteSeerX 10.1.1.18.3499 . дои : 10.1145/506309.506312 . S2CID 14122377 . Архивировано из оригинала (PDF) 5 декабря 2013 г. Проверено 25 сентября 2007 г.
- Синха, Ранджан; Зобель, Джастин (2003). «Эффективная сортировка больших наборов строк на основе Trie» (PDF) . Материалы 26-й Австралазийской конференции по информатике . Том. 16. С. 11–18. CiteSeerX 10.1.1.12.2757 . ISBN 978-0-909-92594-9 . Архивировано из оригинала (PDF) 8 февраля 2012 г. Проверено 25 сентября 2007 г.
- Синха, Ранджан; Вирт, Энтони (март 2010 г.). «Инженерная пакетная сортировка: на пути к быстрой сортировке строк на месте» (PDF) . Журнал экспериментальной алгоритмики ACM . 15 (2,5): 1–24. дои : 10.1145/1671970.1671978 . S2CID 16410080 .
Внешние ссылки
[ редактировать ]- Реализация пакетной сортировки на Java: взрывная сортировка4j.
- Массивы Джуди — это тип пакетной сортировки копирования: реализация на языке C.