Haskell이 quicksort 대신 mergesort를 사용하는 이유는 무엇입니까?

Haskell이 quicksort 대신 mergesort를 사용하는 이유는 무엇입니까?

---

에서 위키 책 ' 하스켈 ,이 다음과 같은 주장은 :

Data.List는 목록 정렬을위한 정렬 기능을 제공합니다. 빠른 정렬을 사용하지 않습니다. 오히려 mergesort라는 알고리즘의 효율적인 구현을 사용합니다.

Haskell에서 quicksort보다 mergesort를 사용하는 근본적인 이유는 무엇입니까? Quicksort는 일반적으로 실제 성능이 더 좋지만이 경우에는 그렇지 않을 수 있습니다. Quicksort의 제자리 이점은 Haskell 목록과 관련하여 어렵습니다 (불가능합니까?).

softwareengineering.SE 에 대한 관련 질문이 있었지만 실제로 mergesort가 사용되는 이유 는 아닙니다 .

프로파일 링을 위해 두 가지 종류를 직접 구현했습니다. Mergesort는 우수했지만 (2 ^ 20 요소 목록의 경우 약 두 배 빠름), 퀵 정렬 구현이 최적이라고 확신 할 수 없습니다.

편집 : 다음은 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..]

편집 2 3 : 내 구현과 .NET의 정렬에 대한 타이밍을 제공하라는 요청을 받았습니다 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)

---

명령형 언어에서 Quicksort는 배열을 변경하여 제자리에서 수행됩니다. 코드 샘플에서 보여 주듯이, 대신 단일 링크 목록을 작성하여 Quicksort를 Haskell과 같은 순수한 기능적 언어로 조정할 수 있지만 그렇게 빠르지는 않습니다.

반면에 Mergesort는 인플레 이스 알고리즘이 아닙니다. 간단한 명령형 구현은 병합 된 데이터를 다른 할당으로 복사합니다. 이는 본질적으로 데이터를 복사해야하는 Haskell에 더 적합합니다.

잠시 뒤로 물러나 자. Quicksort의 성능 우위는 "전설"입니다. 수십 년 전에 오늘날 우리가 사용하는 기계와는 매우 다른 기계에서 축적 된 명성입니다. 같은 언어를 사용하더라도 지상의 사실이 바뀔 수 있으므로 이러한 종류의 지식은 수시로 재확인해야합니다. 이 주제에 대해 읽은 마지막 벤치마킹 문서에는 Quicksort가 여전히 최상위에 있었지만 Mergesort에 대한 리드는 C / C ++에서도 미미했습니다.

Mergesort에는 다른 장점이 있습니다. Quicksort의 O (n ^ 2) 최악의 경우를 피하기 위해 조정할 필요가 없으며 자연스럽게 안정적입니다. 따라서 다른 요인으로 인해 좁은 성능 차이를 잃는 경우 Mergesort는 확실한 선택입니다.

---

@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이 여전히 존재하지만 주석 처리됨). Ian의 벤치 마크에 따르면 그의 병합 정렬은 "무작위 목록"사례에서 퀵 정렬과 경쟁력이 있으며 이미 정렬 된 데이터의 경우 훨씬 더 나은 성능을 보입니다. 나중에 Ian의 버전은 해당 파일의 추가 주석에 따라 약 두 배 빠른 다른 구현으로 대체되었습니다.

The main issue with the original qsort was that it didn't use a random pivot. Instead it pivoted on the first value in the list. This is obviously pretty bad because it implies performance will be worst case (or close) for sorted (or nearly sorted) input. Unfortunately, there are a couple of challenges in switching from "pivot on first" to an alternative (either random, or -- as in your implementation -- somewhere in "the middle"). In a functional language without side effects, managing a pseudorandom input is a bit of a problem, but let's say you solve that (maybe by building a random number generator into your sort function). You still have the problem that, when sorting an immutable linked list, locating an arbitrary pivot and then partitioning based on it will involve multiple list traversals and sublist copies.

I think the only way to realize the supposed benefits of quicksort would be to write the list out to a vector, sort it in place (and sacrifice sort stability), and write it back out to a list. I don't see that that could ever be an overall win. On the other hand, if you already have data in a vector, then an in-place quicksort would definitely be a reasonable option.

---

On a singly-linked list, mergesort can be done in place. What's more, naive implementations scan over half the list in order to get the start of the second sublist, but the start of the second sublist falls out as a side effect of sorting the first sublist and does not need extra scanning. The one thing quicksort has going over mergesort is cache coherency. Quicksort works with elements close to each other in memory. As soon as an element of indirection enters into it, like when you are sorting pointer arrays instead of the data itself, that advantage becomes less.

Mergesort has hard guarantees for worst-case behavior, and it's easy to do stable sorting with it.

---

Short answer:

Quicksort is advantageous for arrays (in-place, fast, but not worst-case optimal). Mergesort for linked lists (fast, worst-case optimal, stable, simple).

Quicksort is slow for lists, Mergesort is not in-place for arrays.

---

Many arguments on why Quicksort is not used in Haskell seem plausible. However, at least Quicksort is not slower than Mergesort for the random case. Based on the implementation given in Richard Bird's book, Thinking Functionally in Haskell, I made a 3-way Quicksort:

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

I benchmarked a few cases, e.g., lists of size 10^4 containing Int between 0 and 10^3 or 10^4, and so on. The result is the 3-way Quicksort or even Bird's version are better than GHC's Mergesort, something like 1.x~3.x faster than ghc's Mergesort, depending on the type of data (many repetitions? very sparse?). The following stats is generated by criterion:

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)

However, there is another requirement of sort stated in Haskell 98/2010: it needs to be stable. The typical Quicksort implementation using Data.List.partition is stable, but the above one isn't.

---

Later addition: A stable 3-way Quicksort mentioned in the comment seems as fast as tqsort here.

---

I am not sure, but looking at the code i don't think Data.List.sort is Mergesort as we know it. It just makes a single pass starting with the sequences function in a beautiful triangular mutual recursive fashion with ascending and descending functions to result in a list of already ascending or descending ordered chunks in the required order. Only then it starts merging.

It's a manifestation of poetry in coding. Unlike Quicksort, its worst case (total random input) has O(nlogn) time complexity, and best case (already sorted ascending or descending) is O(n).

I don't think any other sorting algorithm can beat it.

참고URL : https://stackoverflow.com/questions/52237695/why-does-haskell-use-mergesort-instead-of-quicksort