Почему быстрая сортировка лучше, чем другие алгоритмы сортировки на практике?

31

Это репост вопроса о cs.SE от Janoma . Полный кредит и портит ему или cs.SE.

В курсе стандартных алгоритмов нас учат, что быстрая сортировка в среднем составляет O (n log n), а в худшем случае O (n²). В то же время изучаются другие алгоритмы сортировки, в которых O (n log n) в худшем случае (например, mergesort и heapsort ) и даже линейное время в лучшем случае (например, сортировка пузырьков ), но с некоторыми дополнительными потребностями в памяти.

После быстрого взгляда на еще несколько времен выполнения, естественно сказать, что быстрая сортировка не должна быть такой же эффективной, как другие.

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

Почему же тогда быстрая сортировка превосходит другие алгоритмы сортировки на практике? Связано ли это со структурой реальных данных ? Это связано с тем, как работает память в компьютерах? Я знаю, что некоторые воспоминания намного быстрее, чем другие, но я не знаю, является ли это реальной причиной этой нелогичной работы (по сравнению с теоретическими оценками).

Рафаэль
источник
3
Репутация Quicksort датируется временем, когда кеша не существовало.
AProgrammer
9
"Почему быстрая сортировка превосходит другие алгоритмы сортировки на практике?" Конечно, это правда? Покажите нам реальную реализацию, на которую вы ссылаетесь в этом заявлении, и сообщество расскажет вам, почему эта конкретная реализация ведет себя так, как она. Все остальное приведет к диким догадкам о несуществующих программах.
Док Браун
1
@DocBrown: Многие реализации Quicksort (или их варианты) выбраны во многих библиотеках, возможно потому, что они работают лучше всего (я надеюсь, что так). Так что может быть что-то в алгоритме, который делает быструю сортировку быстрой, независимо от реализации .
Рафаэль
1
Кто-то должен сказать это для полноты, поэтому я буду: Quicksort не является (обычно) стабильным. По этой причине вы можете не захотеть использовать его. Кроме того, по этой причине сортировка по умолчанию может не быть быстрой сортировкой, даже если это то, что вам нужно.
Ральф Чапин
1
@Raphael: Часто то, что называется быстрой сортировкой, на самом деле представляет собой разновидность, например, intro sort (используется afaik в стандартной библиотеке C ++), а не чисто быструю сортировку.
Джорджио

Ответы:

21

Я бы не согласился, что быстрая сортировка лучше, чем другие алгоритмы сортировки на практике.

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

Простейшая быстрая сортировка (без случайного поворота) рассматривает этот потенциально распространенный случай как O (N ^ 2) (сводится к O (N lg N) со случайными поворотами), тогда как TimSort может обрабатывать эти случаи в O (N).

Согласно этим тестам в C #, сравнивающим встроенную быструю сортировку с TimSort, Timsort значительно быстрее в большинстве отсортированных случаев и немного быстрее в случае случайных данных, а TimSort становится лучше, если функция сравнения особенно медленная. Я не повторял эти тесты и не удивлюсь, если бы быстрая сортировка немного превысила TimSort для некоторой комбинации случайных данных или если во встроенной сортировке C # (основанной на быстрой сортировке) есть что-то странное, что замедляет ее. Тем не менее, TimSort имеет явные преимущества, когда данные могут быть частично отсортированы, и примерно равна быстрой сортировке по скорости, когда данные не сортируются частично.

TimSort также имеет дополнительный бонус за стабильность, в отличие от быстрой сортировки. Единственный недостаток TimSort - использование O (N) по сравнению с O (lg N) в обычной (быстрой) реализации.

доктор джимбоб
источник
18

Быстрая сортировка считается более быстрой, потому что коэффициент меньше, чем у любого другого известного алгоритма. Для этого нет причины или доказательства, просто не было найдено алгоритма с меньшим коэффициентом. Это правда, что другие алгоритмы также имеют O ( n log n ) времени, но в реальном мире коэффициент также важен.

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

Рамзи Кахил
источник
7
+ Верно. Учителя должны быть более осведомлены (а я был учителем) о том, что постоянные факторы могут меняться на порядки. Таким образом, навык настройки производительности действительно имеет значение, независимо от Big-O. Проблема в том, что они продолжают преподавать gprof только потому, что им нужно преодолеть ту точку пули в учебной программе, которая на 180 градусов неверна.
Майк Данлавей,
2
«Для этого нет причины или причины»: конечно, есть. Если вы будете копать достаточно глубоко, вы найдете причину.
Жиль "ТАК - перестать быть злым"
2
@ B Seven: чтобы упростить многое ... для алгоритма сортировки O (n log n), существует (n log n) итераций цикла сортировки, чтобы отсортировать n элементов. Коэффициент - это время, которое занимает каждый цикл цикла. Когда n действительно велико (по крайней мере, тысячи), коэффициент не так важен, как O (), даже если коэффициент огромен. Но когда n мало, коэффициент имеет значение - и может быть самым важным, если вы сортируете только 10 элементов.
Мэтт Галлахер
4
@MikeDunlavey - хороший пример того, что построение пирамид - это O (n), а сортировка фотографий - O (n ln n), но это быстрее!
Мартин Беккет
2
Существуют гарантированные алгоритмы O (n log n), такие как heapsort и mergesort, поэтому в асимптотическом наихудшем случае Quicksort даже не так быстр, как лучший. Но в реальной производительности некоторые варианты быстрой сортировки работают очень хорошо. Однако говорить «коэффициент меньше» - все равно, что говорить «это быстрее, потому что быстрее». Почему постоянные факторы так малы? Основная причина в том, что быстрая сортировка очень хороша с точки зрения локальности - она ​​очень хорошо использует кэши. У Mergesort тоже хорошая местность, но это очень сложно сделать на месте.
Steve314
16

Быстрая сортировка не превосходит все другие алгоритмы сортировки. Например, сортировка по куче снизу вверх ( Wegener 2002 ) превосходит быструю сортировку для разумных объемов данных, а также является алгоритмом на месте. Это также легко реализовать (по крайней мере, не сложнее, чем какой-то оптимизированный вариант быстрой сортировки).

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

Док Браун
источник
+1: я провел несколько тестов, и сортировка слиянием определенно была лучше, чем быстрая сортировка для больших массивов (> 100000 элементов). Сортировка кучи была немного хуже сортировки слиянием (но сортировке слиянием требуется больше памяти). Я думаю, что то, что люди называют быстрой сортировкой, часто является вариацией, называемой интро-сортировкой: быстрая сортировка, которая возвращается к кучной сортировке, когда глубина рекурсии выходит за определенные пределы.
Джорджио
@Giorgio: быстрая сортировка может быть изменена некоторыми способами, чтобы улучшить ее, см., Например, здесь: algs4.cs.princeton.edu/23quicksort Пробовали ли вы эти улучшения?
Док Браун
Интересно, вы можете оставить ссылку на книгу \ сайт, чтобы узнать больше об этом? (желательно книга)
Рамзи Кахил
@Martin: ты имеешь в виду геймпорт Bottom-Up? Ну, я дал ссылку выше. Если вам нужен бесплатный ресурс, в немецкой википедии есть статья об этом ( de.wikipedia.org/wiki/BottomUp-Heapsort ). Даже если вы не говорите по-немецки, я думаю, вы все равно можете прочитать пример C99.
Док Браун
7

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

Quicksort:

  • имеет среднюю сложность по времени Θ ( n log n );
  • может быть реализовано с пространственной сложностью Θ (log n );

Также имейте в виду, что нотация большого О не учитывает никаких констант, но на практике это имеет значение, если алгоритм работает в несколько раз быстрее. Θ ( n log n ) означает, что алгоритм выполняется в K  n  log ( n ), где K является константой. Quicksort является алгоритм сравнения сортировки с наименьшим K .

Vartec
источник
1
@ Жиль: у него низкий К, потому что это простой алгоритм.
Vartec
5
WTF? Это не имеет никакого смысла. Простота алгоритма не имеет отношения к скорости его работы. Сортировка выбора проще, чем быстрая сортировка, это не делает ее быстрее.
Жиль "ТАК - перестань быть злым"
1
@ Жиль: сортировка выбора O (n ^ 2) для любого случая (худший, средний и лучший). Так что не важно, насколько это просто. Быстрая сортировка - это O (n log n) для среднего случая, и среди всех алгоритмов с O (n log n) avg это самый простой.
vartec
1
@ Жиль: при прочих равных, простота помогает производительности. Допустим, вы сравниваете два алгоритма, каждый из которых принимает (K n log n) итераций своих соответствующих внутренних циклов: алгоритм, который должен выполнять меньше операций за цикл, имеет преимущество в производительности.
наступающий шторм
1
@comingstorm: Выражение так сформулировано, что ваше высказывание является тавтологией, но оно не относится к "простоте". Существуют, например, более сложные варианты быстрой сортировки (различия по регистру!), Которые приводят к меньшему времени выполнения (как в теории, так и на практике).
Рафаэль
5

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

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

Джеймс Андерсон
источник
1

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

Тем не менее, я считаю, что быстрая сортировка работает хорошо (для случайного ввода), потому что она проста, и потому что ее рекурсивная структура относительно дружественна кешу. С другой стороны, поскольку его наихудший случай легко вызвать, любое практическое использование быстрой сортировки должно быть более сложным, чем указывалось бы в описании учебника: таким образом, измененные версии, такие как интросорт.

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

comingstorm
источник
Я предполагаю, что «меньшая константа», с которой другие связывают это, - это формальная форма анализа, то есть количество сравнений или свопов. Это очень хорошо определено, но неясно, как это переводится во время выполнения. Коллега в настоящее время проводит некоторые исследования по этому вопросу.
Рафаэль
У меня сложилось впечатление, что речь идет об общей производительности, но я не буду рассчитывать ни на что. Однако вы правы: если ваше сравнение особенно дорого, вы можете посмотреть количество ожидаемых сравнений ...
Гроза
1
По той причине, что вы заявляете, что говорить об общей производительности (с точки зрения времени) в общем случае не имеет смысла, поскольку учитывается слишком много деталей. Причина для подсчета только операций выбора не в том, что они дорогостоящие, а в том, что они происходят "чаще всего". "в смысле обозначений Ландау (Big-Oh), поэтому их подсчет дает грубую асимптотику. Как только вы учитываете константы и / или время выполнения, эта стратегия становится гораздо менее интересной.
Рафаэль
Хорошая реализация QuickSort скомпилирует так, чтобы ваши сводные значения оставались в регистре процессора столько, сколько они необходимы. Этого часто достаточно, чтобы превзойти теоретически более быструю сортировку с сопоставимыми временами Big-O.
Дэн Лайонс
Разные алгоритмы сортировки имеют разные характеристики в отношении количества сравнений и количества обменов, которые они выполняют. И @DanLyons заметили, что типичная сортировка в библиотеке выполняет свои сравнения с помощью пользовательских функций, и хранение значений в регистрах при большом количестве вызовов функций довольно сложно.
Заостренный