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

на Wikibooks'Хаскелл, есть по иску:

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

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

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

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

Edit: вот моя реализация сортировка слиянием и быстрая сортировка:

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 s
  • mergesort: 1.092 s (~6x медленнее, чем Data.List.sort)
  • quicksort: 1.152 s (~7x медленнее, чем Data.List.sort)
4 60
performance haskell sorting

4 ответа:

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

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

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

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

65

Я думаю, что ответ @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...

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

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

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

26

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

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

4

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

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

быстрая сортировка является медленным для списков, сортировка слиянием не в месте для массивов.

3