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

<p>в <a href="https://en.wikibooks.org/wiki/haskell">wikibooks '<em>haskell</em></a> , есть <a href="https://en.wikibooks.org/wiki/haskell/higher-order\_functions">следующая претензия</a> :</p><blockquote> <p>data.list предлагает функцию сортировки списков. это не использует быструю сортировку; скорее, он использует эффективную реализацию алгоритма под названием mergesort.</p> </blockquote><p><strong>какова основная причина в haskell использовать сортировку слиянием вместо быстрой сортировки?</strong> быстрая сортировка обычно имеет лучшую практическую производительность, но, возможно, не в этом случае. я понял, что преимущества быстрой сортировки на месте трудно (невозможно?) сделать со списками на haskell.</p><p>был <a href="https://softwareengineering.stackexchange.com/questions/180417/fastest-haskell-library-sort-implementation">связанный вопрос о softwareengineering.se</a> , но на самом деле он не был посвящен <em>почему</em> использованию mergesort.</p><p>я реализовал эти два вида для профилирования. mergesort был лучше (примерно в два раза быстрее для списка из 2 ^ 20 элементов), но я не уверен, что моя реализация быстрой сортировки была оптимальной.</p><p><strong>edit:</strong> вот мои реализации mergesort и quicksort:</p><pre class="lang-hs prettyprint-override"><code>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..] </code></pre><p><strong>правка 
2
 3:</strong> меня попросили предоставить сроки для моих реализаций по сравнению с сортировкой в <code>data.list</code>. следуя советам @will ness, я скомпилировал <a href="https://gist.github.com/rwbogl/a7e4fb66c4b606da2f084242111ebe55">этот gist</a> с флагом <code>-o2</code>, каждый раз изменяя предоставляемую сортировку в <code>main</code>, и выполнял ее с помощью <code>+rts -s</code>. сортированный список представлял собой дешевый, псевдослучайный список <code>[int]</code> с 2 ^ 20 элементами. результаты были следующими:</p><ul> <li><code>data.list.sort</code>: 0,171 с</li> <li><code>mergesort</code>: 1.092s (~ в 6 раз медленнее, чем <code>data.list.sort</code>)</li> <li><code>quicksort</code>: 1.152s (~ в 7 раз медленнее, чем <code>data.list.sort</code>)</li> </ul>

<p>в императивных языках быстрая сортировка выполняется на месте путем изменения массива. как вы продемонстрировали в своем примере кода, вы можете адаптировать quicksort к чисто функциональному языку, такому как haskell, создавая односвязные списки, но это не так быстро.</p><p>с другой стороны, mergesort не является алгоритмом на месте: простая императивная реализация копирует объединенные данные в другое распределение. это лучше подходит для haskell, который по своей природе должен в любом случае копировать данные.</p><p>давайте сделаем небольшой шаг назад: производительность quicksort edge - это «знания» - репутация, созданная десятилетиями назад на машинах, которые сильно отличаются от тех, которые мы используем сегодня. даже если вы используете один и тот же язык, такие знания время от времени нуждаются в перепроверке, поскольку факты на местах могут измениться. в последнем тестовом документе, который я читал по этой теме, quicksort все еще был на вершине, но его преимущество над mergesort было небольшим, даже в c/c++.</p><p>mergesort имеет и другие преимущества: его не нужно настраивать, чтобы избежать наихудшего случая quicksort o (n ^ 2), и он, естественно, стабилен. таким образом, если вы потеряете узкую разницу в производительности из-за других факторов, mergesort станет очевидным выбором.</p>

<p>я думаю, что ответ @comingstorm в значительной степени на носу, но вот еще немного информации об истории функции сортировки ghc.</p><p>в исходном коде для <code>data.oldlist</code> вы можете найти <a href="http://hackage.haskell.org/package/base-4.11.1.0/docs/src/data.oldlist.html#sort">реализацию</a> of <code>sort</code> и убедиться, что это сортировка слиянием. чуть ниже определения в этом файле следующий комментарий:</p><pre><code>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... </code></pre><p>итак, первоначально была использована функциональная быстрая сортировка (и функция <code>qsort</code> все еще существует, но закомментирована). тесты яна показали, что его сортировка слиянием была конкурентоспособной с быстрой сортировкой в случае «случайного списка» и значительно превзошла его в случае уже отсортированных данных. позднее, согласно дополнительным комментариям в этом файле, версия яна была заменена другой реализацией, которая была примерно в два раза быстрее.</p><p>основная проблема с оригинальной переменной <code>qsort</code> заключалась в том, что она не использовала случайный пивот. вместо этого он поворачивается на первое значение в списке. это, очевидно, довольно плохо, поскольку подразумевает, что производительность будет наихудшим (или близким) для отсортированного (или почти отсортированного) ввода. к сожалению, есть пара сложностей при переключении с «поворот на первый» на альтернативу (случайным образом или - как в вашей реализации - где-то в «середине»). на функциональном языке без побочных эффектов управление псевдослучайным вводом представляет собой небольшую проблему, но, допустим, вы решили это (возможно, встроив генератор случайных чисел в функцию сортировки). у вас все еще есть проблема, заключающаяся в том, что при сортировке неизменяемого связанного списка, нахождении произвольного центра и последующем разбиении на его основе потребуется несколько обходов списка и копий подсписка.</p><p>я думаю, что единственный способ реализовать предполагаемые преимущества быстрой сортировки - это записать список в вектор, отсортировать его на месте (и пожертвовать стабильностью сортировки) и записать его обратно в список. я не понимаю, что это может быть общей победой. с другой стороны, если у вас уже есть данные в векторе, то быстрая сортировка на месте определенно была бы разумным вариантом.</p>

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

<p><strong> короткий ответ: </strong></p><p>быстрая сортировка выгодна для массивов (на месте, быстрая, но не оптимальная в худшем случае). слияние для связанных списков (быстрый, оптимальный в худшем случае, стабильный, простой).</p><p>быстрая сортировка медленная для списков, mergesort не для массивов.</p>

<p>многие аргументы о том, почему quicksort не используется в haskell, кажутся правдоподобными. однако, по крайней мере, быстрая сортировка не медленнее, чем mergesort для случайного случая. основываясь на реализации, приведенной в книге ричарда берда, <em>мышление функционально в хаскеле</em>, я сделал трехстороннюю быструю сортировку:</p><pre><code>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 </code></pre><p>я протестировал несколько случаев, например, списки размером 10 ^ 4, содержащие int от 0 до 10 ^ 3 или 10 ^ 4, и так далее. в результате 3-сторонняя версия quicksort или даже bird лучше, чем mergesort ghc, что примерно в 1.x ~ 3.x быстрее, чем mergesort ghc, в зависимости от типа данных (много повторений? очень мало?). следующая статистика генерируется <a href="http://hackage.haskell.org/package/criterion-1.5.3.0">критерием</a> :</p><pre><code>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) </code></pre><p>однако есть еще одно требование <code>sort</code>, изложенное в haskell <a href="https://www.haskell.org/onlinereport/list.html">98</a> / <a href="https://www.haskell.org/onlinereport/haskell2010/haskellch20.html#x28-22800020">2010</a> : оно должно быть <em>стабильным</em>. типичная реализация quicksort с использованием <code>data.list.partition</code> - это <em>stable</em>, но вышеприведенная - нет. </p><hr><p><strong>позднее добавление</strong>: стабильная трехсторонняя быстрая сортировка, упомянутая в комментарии, кажется такой же быстрой, как и <code>tqsort</code> здесь. </p>

<p>я не уверен, но, глядя на код, я не думаю, что <code>data.list.sort</code> - это mergesort, как мы его знаем. он просто делает один проход, начиная с функции <code>sequences</code> в красивой треугольной взаимно-рекурсивной манере с функциями <code>ascending</code> и <code>descending</code>, чтобы получить список уже восходящих или нисходящих упорядоченных фрагментов в требуемом порядке. только тогда начинается слияние.</p><p>это проявление поэзии в кодировании. в отличие от быстрой сортировки, ее наихудший случай (суммарный случайный ввод) имеет o(nlogn) временную сложность, а лучший случай (уже отсортированный по возрастанию или убыванию) равен o (n).</p><p>я не думаю, что любой другой алгоритм сортировки может победить.</p>