Tại sao lại có một sự khác biệt hiệu suất 1000x giữa hai phiên bản của merge sort trong Haskell

Question

EDIT:

Nó chỉ ra các phiên bản chậm thực sự là một sắp xếp chèn O (n^2) chứ không phải là một merge sort O (n log n) giải thích vấn đề hiệu suất. Tôi nghĩ rằng tôi sẽ tiết kiệm cho độc giả tương lai nỗi đau của lội qua mã để khám phá câu trả lời này.

---

BẮT ĐẦU BẮT ĐẦU TẠI ĐÂY ---------------------------------------- ---

Tôi đã viết hai phiên bản sắp xếp hợp nhất trong haskell và tôi không thể mò mẫm tại sao phiên bản nhanh hơn 1000 lần so với phiên bản khác. Trong cả hai trường hợp, chúng tôi bắt đầu bằng cách tạo mục trong danh sách để sắp xếp danh sách tạo danh sách danh sách. Sau đó, chúng tôi ghép nối các danh sách và hợp nhất chúng cho đến khi chỉ còn một danh sách. Vấn đề có vẻ là tôi đang gọi "doMerge (x1: x2: xs) = doMerge $ hợp nhất x1 x2: doMerge xs" trong phiên bản chậm nhưng gọi doMerge (mergePairs xs) trong phiên bản nhanh. Tôi ngạc nhiên bởi sự khác biệt tốc độ 1000x!

-- 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 

Nhìn vào kết quả hồ sơ, rõ ràng là phiên bản chậm được phân bổ cách bộ nhớ hơn. Tôi không chắc chắn tại sao mặc dù. Cả hai phiên bản có vẻ tương tự trong đầu của tôi. Ai đó có thể giải thích lý do tại sao phân bổ quá khác nhau?

slowMergeSort Profiling kết quả:

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 Profiling

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

Thứ hai trong số này là O(n^2) và không nên được sử dụng vì nó là thuật toán sai (không nên được gọi là mergesort).

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

hoàn thành sắp xếp xs chỉ ngắn hơn so với danh sách gốc. Việc hợp nhất một danh sách rất ngắn với một danh sách rất dài tương đương với việc chèn, vì vậy chúng ta thấy rằng đây thực sự là sắp xếp chèn. Toàn bộ điểm sáp nhập là phân chia và chinh phục, đây không phải là phân chia và chinh phục. Khi độ dài của danh sách tăng lên thì tỷ lệ tốc độ sẽ tiếp tục tồi tệ hơn.

Đầu tiên là loại hợp nhất phù hợp vì nó hợp nhất các danh sách có độ dài bằng nhau.