Neden Haskell birleştirme tür iki sürümü arasındaki bir 1000x performans fark yoktur

Question

DÜZENLEME:

Yavaş versiyonu aslında bir ekleme sıralama O (n^2) yerine bir birleştirme sıralaması O daha (n log çıkıyor n) performans konusunu açıklamak. Bu cevabı bulmak için gelecekteki okuyucuları kodun içinden geçmenin acısını saklayacağımı düşündüm.

---

ORİJİNAL ---------------------------------------- BURADA BAŞLIYOR ---

Haskell'de birleştirme sıralamalarının iki sürümünü yazdım ve neden birinin diğerinden 1000 kat daha hızlı olduğunu anlayamıyorum. Her iki durumda da listede bir liste oluşturarak liste halinde bir liste oluşturarak başlıyoruz. Sonra listeleri bir araya getirip sadece bir liste kalmayıncaya kadar birleştiririz. Sorun şu ki, yavaş sürümde "doMerge (x1: x2: xs) = doMerge $ merge x1 x2: doMerge xs" yi çağırıyorum ama doMerge'i (mergePairs xs) hızlı sürümde çağırıyorum. 1000x hız farkıyla şaşırdım!

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

profilci çıkışında bakıldığında yavaş versiyonu yol fazla bellek tahsis edilir olduğu açıktır. Neden olduğundan emin değilim. Her iki versiyon da kafamda benzer görünüyor. Birisi, tahsisin neden bu kadar farklı olduğunu açıklayabilir mi?

slowMergeSort profil sonuçları:

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 profil

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

bu ikinci O(n^2) olup, (mergesort denilen olmamalıdır) yanlış algoritması olarak kullanılmamalıdır.

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

tamamen sadece orijinal listeden daha sabit kısadır xs sıralar. Çok kısa bir listeyi çok uzun bir listeyle birleştirmek, ekleme işlemine eşdeğerdir, dolayısıyla bunun gerçekten yalnızca ekleme sıralama olduğunu görüyoruz. Mergesortun bütün noktası böl ve fethet, bu bölme ve fethetme değil. Listelerin uzunluğu büyüdükçe hız oranı daha da kötüye gitmeye devam edecektir.

Birincisi, yaklaşık uzunluktaki listeleri birleştirdiği için uygun bir birleştirme sıralamadır.