performance - 为什么haskell中两个版本的归并排序有1000倍的性能差异

Question

编辑:

事实证明，慢版本实际上是插入排序 O(n^2) 而不是合并排序 O(n log n) 来解释性能问题。我想我可以让 future 的读者免于费力通过代码来发现这个答案的痛苦。

原创从这里开始-------------------------------------------

我在 haskell 中编写了两个版本的合并排序，但我无法理解为什么一个版本比另一个版本快 1000 倍。在这两种情况下，我们首先将列表中的项目排序为一个列表，创建一个列表列表。然后我们将列表配对并合并它们，直到只剩下一个列表。问题似乎是我在慢版本中调用“doMerge(x1:x2:xs)= doMerge $ merge x1 x2:doMerge xs”，但在快速版本中调用doMerge(mergePairs xs)。 1000倍的速度差异让我感到惊讶!

-- Better version: takes 0.34 seconds to sort a 100,000 integer list.
betMergeSort :: [Int] -> [Int]
betMergeSort list = doMerge $ map (\x -> [x]) list
  where
    doMerge :: [[Int]] -> [Int]
    doMerge [] = []
    doMerge [xs] = xs
    doMerge xs = doMerge (mergePairs xs)

    mergePairs :: [[Int]] -> [[Int]]
    mergePairs (x1:x2:xs) = merge x1 x2 : mergePairs xs
    mergePairs xs = xs

    -- expects two sorted lists and returns one sorted list.
    merge :: [Int] -> [Int] -> [Int]
    merge [] ys = ys
    merge xs [] = xs
    merge (x:xs) (y:ys) = if x <= y
                            then x : merge xs (y:ys)
                            else y : merge (x:xs) ys


-- Slow version: takes 350 seconds to sort a 100,000 integer list.
slowMergeSort :: [Int] -> [Int]
slowMergeSort list = head $ doMerge $ map (\x -> [x]) list
  where
    doMerge :: [[Int]] -> [[Int]]
    doMerge [] = []
    doMerge (oneList:[]) = [oneList]
    doMerge (x1:x2:xs) = doMerge $ merge x1 x2 : doMerge xs

    -- expects two sorted list and returns one sorted list.
    merge :: [Int] -> [Int] -> [Int]
    merge [] ys = ys
    merge xs [] = xs
    merge (x:xs) (y:ys) = if x <= y then x : merge xs (y:ys) else y : merge (x:xs) ys

查看分析器输出，很明显慢版本正在分配更多内存。我不确定为什么。这两个版本在我的脑海中似乎很相似。有人可以解释为什么分配如此不同吗？

slowMergeSort 分析结果:

    Wed Aug 21 12:24 2013 Time and Allocation Profiling Report  (Final)

       mergeSort +RTS -sstderr -p -RTS s

    total time  =       12.02 secs   (12017 ticks @ 1000 us, 1 processor)
    total alloc = 17,222,571,672 bytes  (excludes profiling overheads)

COST CENTRE         MODULE  %time %alloc

slowMergeSort.merge Main     99.2   99.4


                                                                               individual     inherited
COST CENTRE               MODULE                             no.     entries  %time %alloc   %time %alloc

MAIN                      MAIN                                74           0    0.0    0.0   100.0  100.0
 main                     Main                               149           0    0.0    0.0   100.0  100.0
  main.sortedL            Main                               165           1    0.0    0.0    99.3   99.5
   slowMergeSort          Main                               167           1    0.0    0.0    99.3   99.5
    slowMergeSort.\       Main                               170       40000    0.0    0.0     0.0    0.0
    slowMergeSort.doMerge Main                               168       79999    0.0    0.0    99.2   99.5
     slowMergeSort.merge  Main                               169   267588870   99.2   99.4    99.2   99.4
  main.sortVersion        Main                               161           1    0.0    0.0     0.0    0.0
  randomInts              Main                               151           1    0.0    0.0     0.7    0.5
   force                  Main                               155           1    0.0    0.0     0.0    0.0
    force.go              Main                               156       40001    0.0    0.0     0.0    0.0
   randomInts.result      Main                               152           1    0.7    0.5     0.7    0.5

libMergeSort 分析

    Wed Aug 21 12:23 2013 Time and Allocation Profiling Report  (Final)

       mergeSort +RTS -sstderr -p -RTS l

    total time  =        0.12 secs   (124 ticks @ 1000 us, 1 processor)
    total alloc = 139,965,768 bytes  (excludes profiling overheads)

COST CENTRE              MODULE  %time %alloc

randomInts.result        Main     66.9   64.0
libMergeSort.merge       Main     24.2   30.4
main                     Main      4.0    0.0
libMergeSort             Main      2.4    3.2
libMergeSort.merge_pairs Main      1.6    2.3


                                                                                    individual     inherited
COST CENTRE                    MODULE                             no.     entries  %time %alloc   %time %alloc

MAIN                           MAIN                                74           0    0.0    0.0   100.0  100.0
 main                          Main                               149           0    4.0    0.0   100.0  100.0
  main.sortedL                 Main                               165           1    0.0    0.0    28.2   35.9
   libMergeSort                Main                               167           1    2.4    3.2    28.2   35.9
    libMergeSort.\             Main                               171       40000    0.0    0.0     0.0    0.0
    libMergeSort.libMergeSort' Main                               168          17    0.0    0.0    25.8   32.7
     libMergeSort.merge_pairs  Main                               169       40015    1.6    2.3    25.8   32.7
      libMergeSort.merge       Main                               170      614711   24.2   30.4    24.2   30.4
  main.sortVersion             Main                               161           1    0.0    0.0     0.0    0.0
  randomInts                   Main                               151           1    0.0    0.0    67.7   64.0
   force                       Main                               155           1    0.0    0.0     0.8    0.0
    force.go                   Main                               156       40001    0.8    0.0     0.8    0.0
   randomInts.result           Main                               152           1   66.9   64.0    66.9   64.0

Answer 1

其中第二个是 O(n^2)并且不应使用，因为它是错误的算法(不应称为合并排序)。

doMerge (x1:x2:xs) = doMerge $ merge x1 x2 : doMerge xs

完全排序 xs这仅比原始列表短一个常数。将一个很短的列表与一个很长的列表合并就相当于插入，所以我们看到这实际上只是插入排序。合并排序的全部意义在于分而治之，这不是分而治之。随着列表的长度越来越大，速度比将继续变差。

第一个是适当的合并排序，因为它合并大约偶数长度的列表。