Сравнение тимсорта и быстрой сортировки

Question

Почему я чаще всего слышу о быстрой сортировке, как самом быстром общем алгоритме сортировки, когда timsort (согласно википедии), кажется, работает намного лучше?Похоже, Google не дал никакого сравнения.

Answer 1

TimSort - это оптимизация слияния, она стабильна и быстрее, чем старая сортировка.

при сравнении с быстрой сортировкой имеет два преимущества:

1. Невероятно быстро для почти отсортированнойпоследовательность данных (включая данные, отсортированные в обратном порядке);
2. Наихудший случай по-прежнему O (N * LOG (N)).

Если честно, я не думаю, что # 1это преимущество, но оно меня впечатлило.

Вот преимущества QuickSort

1. QuickSort очень очень прост, даже очень хорошо настроенная реализация, мы можем записать его псевдо-коды в пределах 20 строк;
2. QuickSort - этосамый быстрый в большинстве случаев;
3. Потребление памяти составляет LOG (N).

В настоящее время в Java 7 SDK реализован Timsort и новый вариант быстрой сортировки: т.е. Dual Pivot QuickSort.

Если вам нужна стабильная сортировка, попробуйте timsort, иначе начните с быстрой сортировки.

Answer 2

Более или менее это связано с тем, что Timsort является гибридным алгоритмом сортировки.Это означает, что в то время как два основных вида, которые он использует (сортировка Mergesort и Insertion), хуже, чем Quicksort для многих типов данных, Timsort использует их только тогда, когда это выгодно.

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

Подробнее о Timsort см. этот ответ и связанный пост в блоге.В основном это предполагает, что большинство данных уже частично отсортированы, и создает «прогоны» отсортированных данных, которые обеспечивают эффективное объединение с использованием сортировки слиянием.

Answer 3

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

JDK7 использует TimSort для массива объектов. Массив объектов содержит только ссылку на объект. Сам объект хранится в куче. Чтобы сравнить объект, нам нужно прочитать объект из кучи. Это похоже на чтение из одной части кучи для одного объекта, затем случайное чтение объекта из другой части кучи. Будет много пропущенного кеша. Я думаю, по этой причине локальность памяти уже не важна. Это может быть причиной того, что JDK использует только TimSort для массива объектов вместо примитивного массива.

Это только мое предположение.

Answer 4

Вот номера тестов с моей машины (процессор i7-6700, 3,4 ГГц, Ubuntu 16.04, gcc 5.4.0, параметры: SIZE = 100000 и RUNS = 3):

$ ./demo 
Running tests
stdlib qsort time:                 12246.33 us per iteration
##quick sort time:                  5822.00 us per iteration
merge sort time:                    8244.33 us per iteration
...    
##tim sort time:                    7695.33 us per iteration
in-place merge sort time:           6788.00 us per iteration    
sqrt sort time:                     7289.33 us per iteration    
...
grail sort dyn buffer sort time:    7856.67 us per iteration

Тест проводитсяиз проекта sort Свенсона, в котором он реализовал несколько алгоритмов сортировки в C. Предположительно , его реализации достаточно хороши, чтобы быть репрезентативными, но я их не исследовал.

Так что вы действительно не можете сказать.Контрольные цифры сохраняют свою актуальность не более двух лет, а затем вы должны повторить их.Возможно, timsort победил qsort waaay еще в 2011 году, когда был задан вопрос, но времена изменились.Или qsort всегда был самым быстрым, но timsort превзошел его по неслучайным данным.Или код Свенсона не так хорош, и лучший программист переломил ситуацию в пользу Тимсорта.Или, возможно, я отстой и не использовал правильный CFLAGS при компиляции кода.Или ... Вы поняли.