Прав был Шарахов, когда 4 года назад в своём блоге сказал "быстрая сортировка обладает какой-то мистической силой, заставляя снова возвращаться к ней". В битве за удобством и скоростью мне удалось достичь определённых успехов и сегодня я поделюсь результатами своего труда, но сперва объясню, чем вообще вызвана необходимость доработать сортировку.


1) По долгу службы мне периодически приходится обрабатывать внушительные объёмы данных и совсем не редкая операция - сортировка. В модуле Classes в своё время я нашёл реализацию и достаточно долго использовал её (листинг выше). Но в реальных условиях нужно сортировать не указатели, а структуры. Периодически приходилось создавать вспомогательный массив указателей, инициализировать и позже вызывать QuickSort. В конечном счёте потребовалось простое решение, при помощи которого можно оперативно "создать" требуемую сортировку.
2) Конечно напрашивается решение - использовать шаблоны. Но в Delphi7 шаблонов нет, а современные дженерики обладают существенным рядом недостатков, о которых поговорим позже.
3) В теории глубина рекурсии в QuickSort в худшем случае - равна N. В Delphi реализации ситуация оптимизируется, но не решается кардинально. А значит в зависимости от набора данных вполне существует вероятность, что скажем при сортировке миллиона элементов произойдёт переполнение стека. Ситуация усугубляется тем, что на платформе x64 стек в рекурсиях расходуется значительно быстрее, чем на x86 и ARM. Мне же удалось реализовать решение, которое не только не приведёт к переполнению стека, но и затратит в худшем случае 1кб на платформе x64.
4) Я обнаружил, что львиную долю времени сортировки занимает вызов калбека сравнения. Необходимость в нём на практике возникает не всегда. Мы часто сравниваем 1-2 поля, причём числовых, а значит реализовав сравнение вручную или вызвав inline оператор (надеюсь такие есть) - мы существенно повысим производительность сортировки. К сожалению дженерики не позволяют использовать операторы сравнения, а функции-компараторы гарантированно дают просадку производительности (что отлично видно на тесте с Integer). К слову привычные компараторы тоже используются неэффективно. В своё время Sha посвятил небольшой раздел правильному сравнению Integer с громким названием "Самая быстрая на Земле". Но в умных реализациях сортировки на С++ используется оператор < (LessThan), которого достаточно, и который существенно упрощает и сокращает время сравнения.


5) Вас ожидает сюрприз - если станете сортировать строки, варианты, интерфейсы, динамических массивы, замыкания или структуры их содержащие. Алгоритм быстрой сортировки минимум в двух местах предполагает чтение и запись структур. А при каждом копировании таких данных происходит невидимая рутина по инициализации и финализации данных. Не говоря уже о невидимом блоке try/finally, призванном подчищать данные по выходу из функции. Существует способ обойти внутреннюю рутину через копирование массива байт, но в рамках дженериков реализовать такой подход невозможно. В итоге при неумелой сортировке строк/массивов/структур/etc вас всегда ожидает просадка производительности. Что кстати легко заметить в тесте для строк. В обоих случаях используется стандартный RTL компаратор строк, но буферизируются элементы по разному.


6) Одна из оптимизаций - сортировка вставками для малых (под)массивов. Реализацию брал и оптимизировал у Шарахова.
7) Ну и наконец оптимизации на низком уровне. Поскольку конечное время работы зависит от объёма исполненных тактов, а количество регистров крайне мало - путём титанических усилий, мне всё-таки удалось выжать из компилятора Delphi максимум :)

Собственно всё. Используйте кому нужно. Скопируйте функцию и замените <T> на ваш тип.
Несмотря на страшный вид функций, бинарный размер у них примерно равен дженерик-реализациям. Для сортировки Integer порядка 288 байт если не ошибаюсь.

Ссылка:
http://webfile.ru/8ea97d85dff9b007d66aef7b251f7e1d

white_nigger

красавчик!
тока у меня не настолько большие объёмы. тысяч 10 максимум. но часто.
распараллеливание думаю мало поможет. но скинь сорсы посмотреть.

p.s.
у меня тоже ассемблера нет

asviridenkovКакие условия использования кода?
любые :))

asviridenkov

быстрее хешей ничего нет
у меня есть наработки, которых мне хватает, но они под x86

asviridenkov

напишу за 10 тыщ если нужно :)

white_nigger

а почему кстати зависимость нелинейная?
а поразрядная сортировка да, рулит :)

Kazantsev Alexey

По моему люди сильно переоценивают значение хеш-функции. Во-первых, даже самая крутая хеш-функция не обезопасит тебя от хеш-промахов. А во-вторых, люди мутят такие функции, что себестоимость её вызова значительно выше обрабатываемых промахов.

Значительно важнее организация хеш-таблицы и менеджмент памяти. В теории размер таблицы должен быть простым числом (для лучшего распределения), на практике размер должен быть степенью двойки, ибо операция вычисления индекса через остаток от деления убивает к чертям весь профит. Ну и стандартному менеджеру памяти можно предпочесть альтернативный, потому что структуры имеют одинаковый размер и заточка на многопоточность не нужна (если конечно контейнер не с многопоточным доступом).