Почему не является более гладким?

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

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

Но я никогда не слышал о smoothsort. Никто никогда не упоминает об этом, и большинство обсуждений, похоже, вращаются вокруг других алгоритмов сортировки.

Почему это?

Ответ 1

Производительность Big-O отлично подходит для публикации статей, но в реальном мире мы также должны смотреть на константы. Quicksort был алгоритмом выбора для неустойчивой, на месте, в-памяти сортировки так долго, потому что мы можем реализовать свой внутренний цикл очень эффективно, и он очень удобен для кеширования. Даже если вы можете реализовать внутренний цикл smoothsort так же эффективно или почти так же эффективно, как и quicksort, вы, вероятно, обнаружите, что его пропускная способность кеша делает его медленнее.

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

Ответ 2

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

Например, существует 0 (n) наихудший по времени алгоритм для нахождения статистики k-го порядка, но он настолько сложный, что O ( n log n) наихудшая версия превосходит его в большинстве случаев.

Кроме того, есть интересное сравнение:

... Как вы можете видеть, оба Timsort и Smoothsort не разрезали горчицу. Smoothsort хуже, чем сортировки STL во всех случаях (даже при замене std: bitset на сырые операции с битами)...

Ответ 3

Ну сначала я бы сказал, что это не похоже на то, что Smoothsort не знаменит. Это зависит от потребности пользователя, а также зависит от пользователя, использовать его или нет.

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

Из Документация: -

Алгоритм smoothsort должен иметь возможность хранить в памяти размеры всех кучек в строке. Поскольку все эти значения Это обычно делается с использованием битового вектора. Более того, поскольку в последовательности есть не более O (log n) чисел, эти биты могут быть закодированных в O (1) машинных словах, предполагая, что трансдихотомическая машина модель.