О QuickSort не говори

← →
Друг (2014-08-11 20:44) [0]

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

// "стандартная реализация" из модуля 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), которого достаточно, и который существенно упрощает и сокращает время сравнения.
QuickSort(Integer) test: Generics QuickSort (standard)... 3838ms. Asm QuickSort... 1856ms. Smart QuickSort... 1451ms.
5) Вас ожидает сюрприз - если станете сортировать строки, варианты, интерфейсы, динамических массивы, замыкания или структуры их содержащие. Алгоритм быстрой сортировки минимум в двух местах предполагает чтение и запись структур. А при каждом копировании таких данных происходит невидимая рутина по инициализации и финализации данных. Не говоря уже о невидимом блоке try/finally, призванном подчищать данные по выходу из функции. Существует способ обойти внутреннюю рутину через копирование массива байт, но в рамках дженериков реализовать такой подход невозможно. В итоге при неумелой сортировке строк/массивов/структур/etc вас всегда ожидает просадка производительности. Что кстати легко заметить в тесте для строк. В обоих случаях используется стандартный RTL компаратор строк, но буферизируются элементы по разному.
QuickSort(String) test: Generics QuickSort (standard)... 18596ms. Smart QuickSort... 6911ms.
6) Одна из оптимизаций - сортировка вставками для малых (под)массивов. Реализацию брал и оптимизировал у Шарахова.
7) Ну и наконец оптимизации на низком уровне. Поскольку конечное время работы зависит от объёма исполненных тактов, а количество регистров крайне мало - путём титанических усилий, мне всё-таки удалось выжать из компилятора Delphi максимум :)

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

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

← →
Rouse_ © (2014-08-11 21:00) [1]

Не плохо (на первый взгляд :)
Правда... именно поэтому мы и не используем быструю сортировку на критических обьёмах :)

← →
jack128_ (2014-08-11 21:51) [2]

> Существует способ обойти внутреннюю рутину через копирование
> массива байт, но в рамках дженериков реализовать такой подход
> невозможно.

с чего бы это??

var Buffer: array[0..31] of byte; procedure TUtils.MemorySwap<T>(var A, B: T); begin if SizeOf(T) <= (High(Buffer) + 1) then begin Move(@A, @Buffer, SizeOf(A)); Move(@B, @A, SizeOf(A)); Move(@Buffer, @B, SizeOf(A)); end else Assert(False, "Тут имеет смысл выделять дин память"); end;

← →
Друг (2014-08-11 23:47) [3]

> jack128_ (11.08.14 21:51) [2]

если не вдаваться в разбор твоего кода, то sizeof(T) не работает :)

← →
Rouse__ (2014-08-12 00:06) [4]

Правда чтоль? :))) проверял?

← →
Sha © (2014-08-12 00:09) [5]

> Друг (11.08.14 20:44)

Было бы интересно сравнить время работы с сортировками,
приведенными у меня в статье.
Интересует, естественно, вариант с вызовом функции сравнения.

И ниже еще несколько замечаний, если уж ты всерьез этим занялся:

> В теории глубина рекурсии в QuickSort в худшем случае - равна N.

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

> Но в умных реализациях сортировки на С++ используется оператор < (LessThan), которого достаточно, и который существенно упрощает и сокращает время сравнения.

А тупые авторы сортировок на других языках этого не знают,
и совершенно случайно записывают свои алгоритмы так,
чтобы в них можно было обойтись исключительно функциями вида LessThan.
Ты, вероятно, не заметил, но у большинства нормальных авторов
все алгоритмы такие. Тем не менее, периодически всплывают юзеры,
открывающие всем глаза.

← →
Друг (2014-08-12 00:09) [6]

http://delphimaster.net/view/2-1404906872/

самое интересное, что и джек там был :)

← →
Друг (2014-08-12 00:24) [7]

> Sha © (12.08.14 00:09) [5]

Ты злой какой-то, ей богу :)
Во-первых, давай сравним. Я открыл исходники, забубень свой код, я добавлю реализацию с калбеком. Мне тоже интересно.

Во-вторых о < ты и сам пишешь в статье:
Недавно John Herbster пошел чуть дальше и предложил использовать в QuickSort функции сравнения, возвращающие результат типа boolean.

Ну и наконец о глубине. В изначальной реализации - N. В Classes реализации кстати тоже N. Есть реализация с логарифмом - никто не спорит.

← →
Sha © (2014-08-12 00:45) [8]

> Друг (12.08.14 00:24) [7]
> Во-первых, давай сравним. Я открыл исходники, забубень свой код,
> я добавлю реализацию с калбеком. Мне тоже интересно.

Я примерно догадываюсь, каким будет результат )
У меня в экспериментах ассемблерный код без рекурсии едва заметно выиграл у обычного хорошо сбалансированного паскаля.
А забубенить ща некогда.

> Во-вторых о < ты и сам пишешь в статье:
> Недавно John Herbster пошел чуть дальше и предложил использовать
> в QuickSort функции сравнения, возвращающие результат типа boolean.

Году так в 76 у Синглтона на это обратил внимание, если не ошибаюсь. А Хебстер на форуме Ембы по дельфи об этом много говорил,
потому и написал. Ты же сейчас уже не вспомнишь изобретателя колеса.

> Ну и наконец о глубине. В изначальной реализации - N.
> В Classes реализации кстати тоже N.
> Есть реализация с логарифмом - никто не спорит.

Ну так и надо говорить, что логарифм. Это и есть глубина рекурсии.
Более того, можно было бы сказать, что есть нерекурсивные реализации
с доп. массивом на 64 целых, которых тебе за глаза хватит в реальной жизни, чтобы не создавать впечатление, что предлагается
нечто радикально новое. Все это уже кем-то это открыто.

← →
Друг (2014-08-12 00:51) [9]

Удалено модератором

← →
Sha © (2014-08-12 00:53) [10]

Удалено модератором

← →
Друг (2014-08-12 10:53) [11]

> jack128_ (11.08.14 21:51) [2]
> Rouse__ (12.08.14 00:06) [4]

Хех, в приведённом виде действительно работает
Тока сие даже близко по производительности не стоит с использованным подходом

А запись type TData = array[0..sizeof(T)] в дженериках не поддерживается :(

← →
jack128_ (2014-08-12 12:08) [12]

> А запись type TData = array[0..sizeof(T)] в дженериках не
> поддерживается :(

нужно просто хитрее быть ;-)

class procedure TUtils<T>.Test; const SizeOfT = SizeOf(T); type TData = array[0..SizeOfT] of byte; var A: TData; begin A[0] := 1; end;

к слову TData = array[0..SizeOfT - 1] of byte; - уже не работает.

ЗЫ Проверялось в Delphi XE4

← →
Друг (2014-08-12 12:39) [13]

> jack128_ (12.08.14 12:08) [12]

в XE5 не компилит

← →
Друг (2014-08-12 12:39) [14]

> jack128_ (12.08.14 12:08) [12]

в XE5 не компилит

← →
jack128_ (2014-08-12 12:58) [15]

ну чё, поломали значит.

← →
Друг (2014-08-12 13:50) [16]

> jack128_ (12.08.14 12:58) [15]

Доломали окончательно :))

← →
Mystic © (2014-08-12 15:26) [17]

Все как-бы тривиально... Еще несколько банальностей:

1. В случае больших структур увеличивается и время на их перемещение внутри массива. Поэтому массив указателей таки предпочтительнее.

2. Вероятность наступления худшего случая с глубиной N чуть менее чем никогда. Если это критично, то надо просто выбирать другой алгоритм.

3. Потребность в оптимизации в случае сортировки возникает достаточно редко. Тогда нет большой проблемы в том, чтобы сделать Copy + Paste и тюнить конкретный случай. Более того, даже на уровне представления данных.

← →
Друг (2014-08-12 16:12) [18]

> 1. В случае больших структур увеличивается и время на их
> перемещение внутри массива. Поэтому массив указателей таки
> предпочтительнее.

А если 12-16 байт?

> 2. Вероятность наступления худшего случая с глубиной N чуть
> менее чем никогда. Если это критично, то надо просто выбирать
> другой алгоритм.

Зачем испытывать судьбу и ждать неожиданного переполнения стека?

> 3. Потребность в оптимизации в случае сортировки возникает
> достаточно редко. Тогда нет большой проблемы в том, чтобы
> сделать Copy + Paste и тюнить конкретный случай. Более того,
> даже на уровне представления данных.

Зачем копипастить неэффективные сортировки, когда можно копипастить эффективную сортировку, специально для того заточенную? Берёшь, копируешь, заменяешь <T> на тип, используешь.

Да, не хватает реализации с калбеком и сортировки указателей с калбеком. Но это вопрос лени - когда я (или кто-то другой) на основе "шаблона сортировки" вставит реализацию с калбеком.

← →
Mystic © (2014-08-13 23:02) [19]

> Зачем испытывать судьбу и ждать неожиданного переполнения
> стека

Тогда не имеет смысла вообще использовать этот алгоритм, бери пирамидальную. Или переключайся на пирамидальную, если все плохо. Быстрая сортировка нестабильна. Точка.

Но если один фрейм это 64 байта, то на миллион элементов будет израсходовано 64M стека. Большинство приложений сдохнут при обработке такого объема. Вероятность этого на случайном наборе 1/1000000! ~= 1.21e-5565709.

> Kогда можно копипастить эффективную сортировку, специально
> для того заточенную?

Опять же будет оверхед, если надо будет миллион раз отсортировать 100 чисел.

← →
Mystic © (2014-08-13 23:21) [20]

Опять же, в самом неблагоприятном случае с миллионом элементов у нас будет примерно 5 * 10^-11 сравнений, не говоря о других операциях. На моем ноуте это около двух часов работы, так что Stack Overflow увидят только очень терпеливые.

← →
Омлет © (2014-08-14 21:34) [21]

> 5 * 10^-11 сравнений

Маловаааато ))

← →
Друг (2014-08-15 09:16) [22]

> Mystic ©

В архиве реализация, которая работает быстро и не кушает стек.
Этого достаточно, чтобы использовать её, а не другие реализации или алгоритмы

← →
KSergey © (2014-08-15 10:46) [23]

> 1) По долгу службы мне периодически приходится обрабатывать внушительные объёмы данных и совсем не редкая операция -
> сортировка. В модуле Classes в своё время я нашёл реализацию и достаточно долго использовал её (листинг выше).
> Но в реальных условиях нужно сортировать не указатели, а структуры.

Мне видится подозрительным это.
Сортируем огромные массивы данных, боремся за скорость - но гоняем в памяти не указатели - а целые структуры.
Это точно имеет смысл?

Единственный вариант, когда это имеет смысл - если размер данных в структуре не на много больше указателя, возможно у автора именно такой случай, не знаю.

← →
Друг (2014-08-15 10:52) [24]

> KSergey © (15.08.14 10:46) [23]

так а я по большому счёту не против сортировки указателей
я говорю, что это не всегда удобно
особенно когда структуры 8-16 байт
выделить массив указателей, заполнить его, удалить его - это тоже время

ну и не забывай, что порой нужно хранить сортированный массив. манипуляции с массивом указателей в данном случае слишком накладны

← →
Mystic © (2014-08-15 11:13) [25]

> В архиве реализация, которая работает быстро и не кушает стек.

Тогда тебе надо будет создавать стек руками. Или это не быстрая сортировка. Как что речь идет об экономии памяти.

← →
KSergey © (2014-08-15 11:44) [26]

> Друг (15.08.14 10:52) [24]
> так а я по большому счёту не против сортировки указателей
> я говорю, что это не всегда удобно особенно когда структуры 8-16 байт
> выделить массив указателей, заполнить его, удалить его - это тоже время

Если не рассматривать аспекты другой реализации, стека и прочего - то в случае "не указателей" достаточно скопипастить исходный приведенный код и заменить в заголовке функции PPointerList на указатель на нужный тип массива )

Про всё остальное не спорю, не вникал.

← →
Друг (2014-08-15 13:43) [27]

> KSergey © (15.08.14 11:44) [26]

В принципе да
Но:
1) "инлайн" оператор
2) перемещение сложных структур (строки, динамические массивы, интерфейсы, ...)
3) стек
4) модификация алгоритма - вставки
5) низкоуровневая оптимизация
Банальный пример - если структура имеет размер например 17 байт, то каждое обращение List[I] займёт несколько тактов

> Mystic © (15.08.14 11:13) [25]
посмотри реализацию

← →
Mystic © (2014-08-15 14:54) [28]

> посмотри реализацию

Вот твой стек, созданный руками. Только фиксированного размера.

var STACK: array[0..63] of TStackItem;

В принципе, трюк, когда в первую очередь смотрится наименьший интервал, а потом более длинный вполне можно реализовать и в рекурсивном варианте. Глубина рекурсии в 64 это ничто. Вот только смысла в этом все равно нет, потому что на современных конфигурациях скорее закончится терпение пользователя, чем произойдет Stack overflow. А вот дополнительные проверки могут скушать время в случае over 9000+ мелких массивов. Спасет OPД только переключение на пирамидальную сортировку. Еще может помочь в плане скорости сортировка вставками для маленьких кусков (размер меньше либо равен 16). Впрочем все это давным давно всем известно.

Кстати, когда ты выкладываешь исходники, то не у всех может быть установлен rar (планшеты и просто чужой комп). Плюс cp1251 у меня в notepad видится как

label proc_loop, proc_loop_current, swap_loop, insertion_loop; const // ðåæèì èíîãäà íåîáõîäèìî óêàçûâàòü, ÷òîáû áîëåå îïòèìàëüíî ïðîèçâîäèòü ñðàâíåíèÿ // 0 - ñòðóêòóðà êåøèðóåòñÿ íà ñòåêå (ïî óìîë÷àíèþ) // â ýòîì ñëó÷àå TCmpData = ìàññèâ áàéò.

← →
имя (2014-08-15 16:14) [29]

Удалено модератором

← →
имя (2014-08-15 16:42) [30]

Удалено модератором

← →
имя (2014-08-15 16:47) [31]

Удалено модератором

← →
Друг (2014-08-15 17:33) [32]

> Mystic © (15.08.14 14:54) [28]

Хоть убей, не понял, что ты хотел до меня донести

← →
Mystic © (2014-08-15 17:35) [33]

Удалено модератором

← →
Друг (2014-08-15 18:33) [34]

> Mystic © (15.08.14 17:35) [33]

Ну это тогда получается, что все, кто организует библиотеки и функции - фигнёй страдают :)

> Ну это тогда получается, что все, кто организует библиотеки
> и функции - фигнёй страдают :)

Не все. У кого-то есть проблема. Есть люди, которые пишут библиотеки, которые решают эту проблему. Это полезно.

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

← →
Друг (2014-08-15 19:59) [36]

Ясно :)
TArray.QuickSort<T> писали те, на кого не нужно показывать пальцем :)

← →
Друг (2014-08-15 20:00) [37]

Причём писали далеко не самым лучшим образом :)

Они написали код, который удовлетворяет 99% всех потребностей. Простая и надежная реализация, может быть не очень оптимальная. Последние годы я не слежу за Delphi, но что-то мне подсказывает, что вопросов про повышение эффективности сортировки не очень много.

Ты выбираешь 1% пользователей, но упускаешь из виду тот факт, что у этого одного процента потребности как раз зачастую очень экзотические. И написать что-то универсальное, подходящее всем тут крайне тяжело, возможно невозможно. Не говоря про то, что если сортировка и будет узким местом, то очень вероятно, что такое узкое место будет только одно. И не будет большой проблемы специально для этого случая сделать Copy + Paste с некоторой оптимизацией.

← →
Друг (2014-08-15 21:46) [39]

> Mystic © (15.08.14 20:28) [38]

Есть круг задач - я его описал в [0]
Embarcadero написали бы так же, или сравнимо, если бы дженерики не были такими ущербными
Профит в 2 и 3 раза соответственно, листинг выше. А кого не интересует производительность сортировки - тот сортирует пузырьком

Но у тебя другая логика. Так что всё ok

← →
имя (2014-08-15 23:54) [40]

Удалено модератором

> Друг (15.08.14 21:46) [39]
> Профит в 2 и 3 раза соответственно, листинг выше.

Мне любопытно: это 2..3 раза вас лично спасли? я серьёзно.
Просто сейчас сталкиваюсь если с проблемами скорости - то, как правило, надо ускорение на порядок минимум, тогда есть смысл. А в 2 раза - это не спасает, если говорить о реальных потребностях ускорения. Потому как ускорение в 2..3 раза - это больше формальность: тесты, конечно, её показывают, но пользователю от этого не легче. Да и хватит на пол-года максимум, потом снова упрёшься.

← →
2... 3... профит! (2014-08-18 18:30) [42]

> Мне любопытно: это 2..3 раза вас лично спасли?

если речь о клиентских машинах/приложениях, то трудно понять, кого нужно или можно "спасти", но ускорение узких мест в 2-3 раза однозначно стоит труда по всего лишь замене одной библиотеки на другую

а на сервере это может спасти от увеличения парка железа в 2-3 раза (теоретически, конечно - ясно, что работу с БД какая-то сортировка не ускорит)

кстати, 2 - это бинарный порядок

← →
Друг (2014-08-18 21:52) [43]

> KSergey © (18.08.14 16:38) [41]

Скорость - это маркетинг, время, user-friendly, радость, спокойствие, экономия. 2-3 раза это на примерах выше. А сортируй ты сложные структуры с вариантами, несколькими строками, динамическими массивами - разница будет больше. И самое главное - разница в производительности ничего не стоит. Ну а использовать или нет - это, как говорится, дело хозяйское :)

← →
Дмитрий Белькевич (2014-08-19 02:00) [44]

Думаю, что в Delphi сделали "надежную" и "прозрачную" версию сортировки. Можно, конечно, квиксорт полировать до блеска. Но на реально больших объемах имхо лучше использовать какую-то базу.
Случаи всякие бывают, конечно...

← →
Друг (2014-08-19 10:21) [45]

> Дмитрий Белькевич (19.08.14 02:00) [44]

Неа, на Delphi сделали тупую версию сортировки, которой пользовались ещё N лет назад. Выражаясь на сленге - сделали копипасту.

А то, что надо инструмент подбирать в зависимости от задачи - я полностью согласен. Фокус в данном случае в том, что n-кратный профит ничего не стоит.

> Друг (18.08.14 21:52) [43]
> Скорость - это маркетинг, время, user-friendly, радость,

Мой вопрос разве был про смысл ускорения?
Вы непосредственно на поставленный вопрос прямо ответить можете?

> спокойствие, экономия. 2-3 раза это на примерах выше. А
> сортируй ты сложные структуры с вариантами, несколькими
> строками, динамическими массивами - разница будет больше.

Это почему? поясните, плиз: в каком месте будет ускорение (вы ведь про него говорите) при увеличении размера сортируемых структур?

← →
Друг (2014-08-20 13:26) [47]

> Мой вопрос разве был про смысл ускорения?Вы непосредственно
> на поставленный вопрос прямо ответить можете?

Да, недавно оптимизировал софтину, которая выдавала результат за 34 секунды. Сейчас выдаёт за 10,6 секунд. Как раз получается x3. Очень приятно.

> Это почему? поясните, плиз: в каком месте будет ускорение
> (вы ведь про него говорите) при увеличении размера сортируемых
> структур?

Об этом я написал в [0] посте

О QuickSort не говори Найти похожие ветки