Dlaczego istnieje różnica wydajności 1000x pomiędzy dwiema wersjami seryjnej sortowania w Haskell

Question

EDIT:

Okazuje się powolny wersja jest rzeczywiście Sortowanie przez wstawianie O (n^2) zamiast seryjnej sortowania O (n log n) wyjaśnienie problemu z wydajnością. Pomyślałem, że zaoszczędzę przyszłym czytelnikom bólu brodzenia w kodzie, aby odkryć tę odpowiedź.

---

ORIGINAL BEGINS TUTAJ ---------------------------------------- ---

Napisałem dwie wersje sortowania scalania w haskell i nie mogę zrozumieć, dlaczego ten jest 1000 razy szybszy od drugiego. W obu przypadkach zaczynamy od uczynienia pozycji na liście, aby została posortowana lista tworząca listę list. Następnie tworzymy listy i łączymy je, dopóki nie pozostanie tylko jedna lista. Problem wydaje mi się, że nazywam "doMerge (x1: x2: xs) = doMerge $ merge x1 x2: doMerge xs" w powolnej wersji, ale wywołując doMerge (mergePairs xs) w szybkiej wersji. Jestem zaskoczony różnicą prędkości 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 

Patrząc na wyjściu profiler, oczywiste jest, że powolny wersja przeznacza sposób więcej pamięci. Nie jestem pewien, dlaczego. Obie wersje wyglądają podobnie w mojej głowie. Czy ktoś może wyjaśnić, dlaczego alokacja jest tak różna?

slowMergeSort Profilowanie wynik:

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 Profilowanie

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

Drugim z nich jest O(n^2) i nie powinny być stosowane, ponieważ jest to zły algorytm (nie powinien być nazywany mergesort).

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

zupełnie sortuje xs który jest tylko stały krócej niż na pierwotnej liście. Łączenie bardzo krótkiej listy z bardzo długą jest równoznaczne z wstawieniem, więc widzimy, że jest to po prostu sortowanie wstawek. Cały punkt mergesort to dziel i rządź, to nie jest dziel i rządź. Wraz ze wzrostem długości list, wskaźnik szybkości będzie się pogarszał.

Pierwszym z nich jest właściwy sortowanie scalające, ponieważ łączy on listy o równej długości.