Почему Haskell использует mergesort вместо quicksort?

В "Haskell" Wikibooks есть следующее утверждение:

Data.List предлагает функцию сортировки для сортировки списков. Он не использует quicksort; скорее, он использует эффективную реализацию алгоритма, называемого mergesort.

Какова основная причина в Haskell для использования mergesort по quicksort? Quicksort обычно имеет лучшую практическую производительность, но, возможно, не в этом случае. Я понимаю, что выгодные преимущества quicksort трудно (невозможно?) Делать с списками Haskell.

Был вопрос, связанный с программным обеспечением.SE, но это было не совсем о том, почему используется mergesort.

Я сам реализовал два типа для профилирования. Mergesort был превосходным (примерно в два раза быстрее для списка из 2 ^ 20 элементов), но я не уверен, что моя реализация quicksort была оптимальной.

Изменить: Вот мои реализации mergesort и quicksort:

mergesort :: Ord a => [a] -> [a]
mergesort [] = []
mergesort [x] = [x]
mergesort l = merge (mergesort left) (mergesort right)
    where size = div (length l) 2
          (left, right) = splitAt size l

merge :: Ord a => [a] -> [a] -> [a]
merge ls [] = ls
merge [] vs = vs
merge [email protected](l:ls) [email protected](v:vs)
    | l < v = l : merge ls second
    | otherwise = v : merge first vs

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort [x] = [x]
quicksort l = quicksort less ++ pivot:(quicksort greater)
    where pivotIndex = div (length l) 2
          pivot = l !! pivotIndex
          [less, greater] = foldl addElem [[], []] $ enumerate l
          addElem [less, greater] (index, elem)
            | index == pivotIndex = [less, greater]
            | elem < pivot = [elem:less, greater]
            | otherwise = [less, elem:greater]

enumerate :: [a] -> [(Int, a)]
enumerate = zip [0..]

Изменить 2 3: меня попросили предоставить тайминги для моих реализаций по сравнению со Data.List в Data.List. Следуя рекомендациям @Will Ness, я скомпилировал этот -O2 флагом -O2, каждый раз меняя отсортированный -O2 в main, и выполнил его с помощью +RTS -s. Сортированный список был дешево-созданным, псевдослучайным [Int] списком с 2 ^ 20 элементами. Результаты были следующими:

  • Data.List.sort: 0.171s
  • mergesort: 1.092s (~ 6x медленнее, чем Data.List.sort)
  • quicksort: 1.152s (~ 7x медленнее, чем Data.List.sort)

Ответы

Ответ 1

На императивных языках Quicksort выполняется на месте, изменяя массив. Как вы демонстрируете в своем примере кода, вы можете адаптировать Quicksort к чисто функциональному языку, например Haskell, создавая вместо него отдельные списки, но это не так быстро.

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

Давайте немного отступим: преимущество Quicksort - "знания" - репутация, созданная несколько десятилетий назад на машинах, значительно отличающихся от тех, которые мы используем сегодня. Даже если вы используете один и тот же язык, этот вид знаний требует перепроверки время от времени, поскольку факты на местах могут измениться. В последнем сравнительном документе, который я прочитал на эту тему, Quicksort все еще на вершине, но его лидерство над Mergesort было тонким, даже в C/C++.

У Mergesort есть и другие преимущества: его не нужно настраивать, чтобы избежать худшего случая Quicksort O (n ^ 2), и он естественно стабилен. Таким образом, если вы потеряете узкую разницу в производительности из-за других факторов, Mergesort является очевидным выбором.

Ответ 2

Я думаю, что ответ @comingstorm в значительной степени связан с носом, но здесь есть еще одна информация об истории функции сортировки GHC.

В исходном коде для Data.OldList вы можете найти реализацию sort и убедиться в том, что это сортировка слияния. Как раз под определением в этом файле есть следующий комментарий:

Quicksort replaced by mergesort, 14/5/2002.

From: Ian Lynagh <[email protected]>

I am curious as to why the List.sort implementation in GHC is a
quicksort algorithm rather than an algorithm that guarantees n log n
time in the worst case? I have attached a mergesort implementation along
with a few scripts to time it performance...

Итак, первоначально была использована функциональная quicksort (и функция qsort все еще существует, но прокомментирована). Показатели Ian показали, что его слияние было конкурентоспособным с quicksort в случае "случайного списка" и значительно превзошло его в случае уже отсортированных данных. Позже версия Ian была заменена другой реализацией, которая была примерно в два раза быстрее, согласно дополнительным комментариям в этом файле.

Основная проблема с оригинальным qsort заключалась в том, что он не использовал случайный стержень. Вместо этого он поворачивается по первому значению в списке. Это явно плохо, потому что это означает, что производительность будет наихудшим (или близким) для сортированного (или почти отсортированного) ввода. К сожалению, есть несколько проблем при переключении с "поворота на первый" на альтернативу (случайную или - как в вашей реализации - где-то в середине). На функциональном языке без побочных эффектов управление псевдослучайным входом является проблемой, но позвольте сказать, что вы разрешите это (возможно, построив генератор случайных чисел в вашу функцию сортировки). У вас все еще есть проблема, что при сортировке неизменяемого связанного списка размещение произвольного стержня и последующего разбиения на нем будет включать в себя несколько переходов списка и копии подписок.

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

Ответ 3

В односвязном списке объединение может быть выполнено на месте. Более того, наивные реализации просматривают более половины списка, чтобы получить начало второго подсписок, но начало второго подсети выпадает как побочный эффект сортировки первого подсписчика и не требует дополнительного сканирования. Единственное, что происходит в quicksort, - это объединение кеш-кодов. Quicksort работает с элементами, расположенными близко друг к другу в памяти. Как только элемент косвенности входит в него, например, когда вы сортируете массивы указателей вместо самих данных, это преимущество становится меньше.

У Mergesort есть твердые гарантии для наихудшего поведения, и это легко сделать стабильную сортировку с ним.

Ответ 4

Короткий ответ:

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

Quicksort медленный для списков, Mergesort не на месте для массивов.