Burstsort - Burstsort

Burstsort
Учебный классАлгоритм сортировки
Структура данныхTrie
Худший случай спектакльО(wn)
Худший случай космическая сложностьО(wn)

Burstsort и его варианты являются эффективными кеш-алгоритмами для сортировки струны. Это варианты традиционного радиальная сортировка но быстрее для больших наборы данных общих строк, впервые опубликованных в 2003 году, а некоторые версии оптимизации были опубликованы позже.[1]

Алгоритмы пакетной сортировки используют три для хранения префиксов строк, с растущие массивы указателей как конечных узлов, содержащих отсортированные уникальные суффиксы (называемые ведра). Некоторые варианты копируют хвосты строк в корзины. Когда сегменты превышают заданный порог, сегменты "разбиваются" на попытки, давая сорту свое имя. Более поздний вариант использует индекс сегмента с меньшими вложенными сегментами, чтобы уменьшить использование памяти. Большинство реализаций делегируют функцию быстрой сортировки по нескольким клавишам, расширению трехсторонней быстрой сортировки по основанию счисления, для сортировки содержимого сегментов. Разделив входные данные на сегменты с общими префиксами, сортировку можно производить с эффективным использованием кеша.

Burstsort был представлен как вид, похожий на Сортировка по основанию MSD,[1] но работает быстрее из-за того, что кэширование и связанные с ним системы счисления хранятся ближе друг к другу из-за особенностей структуры trie. Он использует особенности строк, которые обычно встречаются в реальном мире. И хотя асимптотически это то же самое, что и радииксная сортировка, с временной сложностью О(wn) (ш - длина слова и п - количество сортируемых строк), но из-за лучшего распределения памяти он имеет тенденцию быть вдвое быстрее для больших наборов данных строк. Он был объявлен «самым быстрым из известных алгоритмов для сортировки больших наборов строк».[2]

Рекомендации

  1. ^ а б Sinha, R .; Зобель, Дж. (2005). «Сортировка больших наборов строк с учетом кеширования с динамическими попытками» (PDF). Журнал экспериментальной алгоритмики. 9: 1.5. CiteSeerX  10.1.1.599.861. Дои:10.1145/1005813.1041517.
  2. ^ https://news.ycombinator.com/item?id=445221

внешняя ссылка