Почему Haskell использует сортировку слиянием вместо быстрой сортировки?

Question

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

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

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

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

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

Edit: Вот мои реализацииof 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 first@(l:ls) second@(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..]

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

• Data.List.sort: 0,171 с
• mergesort: 1,092 с (~ в 6 раз медленнее, чем Data.List.sort)
• quicksort: 1,152 с (примерно в 7 раз медленнее, чем Data.List.sort)

Answer 1

Многие аргументы о том, почему Quicksort не используется в Haskell, кажутся правдоподобными. Однако, по крайней мере, быстрая сортировка не медленнее, чем Mergesort для случайного случая. Основываясь на реализации, приведенной в книге Ричарда Берда, Функциональное мышление в Haskell , я сделал трехстороннюю быструю сортировку:

tqsort [] = []
tqsort (x:xs) = sortp xs [] [x] [] 
  where
    sortp [] us ws vs     = tqsort us ++ ws ++ tqsort vs
    sortp (y:ys) us ws vs =
      case compare y x of 
        LT -> sortp ys (y:us) ws vs 
        GT -> sortp ys us ws (y:vs)
        _  -> sortp ys us (y:ws) vs

Я протестировал несколько случаев, например, списки размером 10 ^ 4, содержащие Int от 0 до 10 ^ 3 или 10 ^ 4, и так далее. В результате 3-сторонняя версия Quicksort или даже Bird лучше, чем Mergesort GHC, что примерно в 1.x ~ 3.x быстрее, чем Mergesort ghc, в зависимости от типа данных (много повторений? Очень мало?). Следующая статистика генерируется критерием :

benchmarking Data.List.sort/Diverse/10^5
time                 223.0 ms   (217.0 ms .. 228.8 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 226.4 ms   (224.5 ms .. 228.3 ms)
std dev              2.591 ms   (1.824 ms .. 3.354 ms)
variance introduced by outliers: 14% (moderately inflated)

benchmarking 3-way Quicksort/Diverse/10^5
time                 91.45 ms   (86.13 ms .. 98.14 ms)
                     0.996 R²   (0.993 R² .. 0.999 R²)
mean                 96.65 ms   (94.48 ms .. 98.91 ms)
std dev              3.665 ms   (2.775 ms .. 4.554 ms)

Однако есть еще одно требование sort, заявленное в Haskell 98 / 2010 : оно должно быть стабильным . Типичная реализация Quicksort, использующая Data.List.partition, является stable , но вышеприведенная - нет.

---

Позднее добавление : Стабильная трехсторонняя быстрая сортировка, упомянутая в комментарии, кажется здесь такой же быстрой, как и tqsort.

Answer 2

Я не уверен, но, глядя на код, я не думаю, что Data.List.sort - это Mergesort, как мы его знаем. Он просто делает один проход, начиная с функции sequences красивым треугольным взаимно-рекурсивным способом с функциями ascending и descending, чтобы получить список уже восходящих или нисходящих упорядоченных фрагментов в требуемом порядке. Только тогда начинается слияние.

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

Я не думаю, что какой-либо другой алгоритм сортировки может победить его.

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

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

Quicksort replaced by mergesort, 14/5/2002.

From: Ian Lynagh <igloo@earth.li>

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's performance...

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

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

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

Answer 6

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

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

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

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