В "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)
