Прав был Шарахов, когда 4 года назад в своём блоге сказал "быстрая сортировка обладает какой-то мистической силой, заставляя снова возвращаться к ней". В битве за удобством и скоростью мне удалось достичь определённых успехов и сегодня я поделюсь результатами своего труда, но сперва объясню, чем вообще вызвана необходимость доработать сортировку.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
// "стандартная реализация" из модуля Classes
procedure QuickSort(SortList: PPointerList; L, R: Integer; SCompare: TListSortCompare);
var
I, J: Integer;
P, T: Pointer;
begin
repeat
I := L;
J := R;
P := SortList^[(L + R) shr 1];
repeat
while SCompare(SortList^[I], P) < 0 do Inc(I);
while SCompare(SortList^[J], P) > 0 do Dec(J);
if I <= J then
begin
T := SortList^[I];
SortList^[I] := SortList^[J];
SortList^[J] := T;
Inc(I);
Dec(J);
end;
until I > J;
if L < J then QuickSort(SortList, L, J, SCompare);
L := I;
until I >= R;
end;
1) По долгу службы мне периодически приходится обрабатывать внушительные объёмы данных и совсем не редкая операция - сортировка. В модуле Classes в своё время я нашёл реализацию и достаточно долго использовал её (листинг выше). Но в реальных условиях нужно сортировать не указатели, а структуры. Периодически приходилось создавать вспомогательный массив указателей, инициализировать и позже вызывать QuickSort. В конечном счёте потребовалось простое решение, при помощи которого можно оперативно "создать" требуемую сортировку.
2) Конечно напрашивается решение - использовать шаблоны. Но в Delphi7 шаблонов нет, а современные дженерики обладают существенным рядом недостатков, о которых поговорим позже.
3) В теории глубина рекурсии в QuickSort в худшем случае - равна N. В Delphi реализации ситуация оптимизируется, но не решается кардинально. А значит в зависимости от набора данных вполне существует вероятность, что скажем при сортировке миллиона элементов произойдёт переполнение стека. Ситуация усугубляется тем, что на платформе x64 стек в рекурсиях расходуется значительно быстрее, чем на x86 и ARM. Мне же удалось реализовать решение, которое не только не приведёт к переполнению стека, но и затратит в худшем случае 1кб на платформе x64.
4) Я обнаружил, что львиную долю времени сортировки занимает вызов калбека сравнения. Необходимость в нём на практике возникает не всегда. Мы часто сравниваем 1-2 поля, причём числовых, а значит реализовав сравнение вручную или вызвав inline оператор (надеюсь такие есть) - мы существенно повысим производительность сортировки. К сожалению дженерики не позволяют использовать операторы сравнения, а функции-компараторы гарантированно дают просадку производительности (что отлично видно на тесте с Integer). К слову привычные компараторы тоже используются неэффективно. В своё время Sha посвятил небольшой раздел правильному сравнению Integer с громким названием "Самая быстрая на Земле". Но в умных реализациях сортировки на С++ используется оператор < (LessThan), которого достаточно, и который существенно упрощает и сокращает время сравнения.
1.
2.
3.
4.
QuickSort(Integer) test:
Generics QuickSort (standard)... 3838ms.
Asm QuickSort... 1856ms.
Smart QuickSort... 1451ms.
5) Вас ожидает сюрприз - если станете сортировать строки, варианты, интерфейсы, динамических массивы, замыкания или структуры их содержащие. Алгоритм быстрой сортировки минимум в двух местах предполагает чтение и запись структур. А при каждом копировании таких данных происходит невидимая рутина по инициализации и финализации данных. Не говоря уже о невидимом блоке try/finally, призванном подчищать данные по выходу из функции. Существует способ обойти внутреннюю рутину через копирование массива байт, но в рамках дженериков реализовать такой подход невозможно. В итоге при неумелой сортировке строк/массивов/структур/etc вас всегда ожидает просадка производительности. Что кстати легко заметить в тесте для строк. В обоих случаях используется стандартный RTL компаратор строк, но буферизируются элементы по разному.
1.
2.
3.
QuickSort(String) test:
Generics QuickSort (standard)... 18596ms.
Smart QuickSort... 6911ms.
6) Одна из оптимизаций - сортировка вставками для малых (под)массивов. Реализацию брал и оптимизировал у Шарахова.
7) Ну и наконец оптимизации на низком уровне. Поскольку конечное время работы зависит от объёма исполненных тактов, а количество регистров крайне мало - путём титанических усилий, мне всё-таки удалось выжать из компилятора Delphi максимум :)
Собственно всё. Используйте кому нужно. Скопируйте функцию и замените <T> на ваш тип.
Несмотря на страшный вид функций, бинарный размер у них примерно равен дженерик-реализациям. Для сортировки Integer порядка 288 байт если не ошибаюсь.
Ссылка:
http://webfile.ru/8ea97d85dff9b007d66aef7b251f7e1d
