合併排序的方式比插入排序更快謎題

Question

剛剛在排序算法與Haskell溼了我的腳。我實現了插入排序和合並排序

insert_sort :: (Ord a, Show a) => [a] -> [a] 
insert_sort keys = foldr f [] keys 
      where f key []  = [key] 
       f key acc  = insert key acc 
       insert y []  = [y] 
       insert y (x:xs) 
        | x < y  = x : insert y xs 
        | otherwise = y : x : xs 

merge_sort :: (Ord a, Show a) => [a] -> [a] 
merge_sort (x:[]) = [x] 
merge_sort keys = merge (merge_sort (take len keys)) (merge_sort (drop len keys)) 
     where len   = length keys `div` 2 
      merge :: [a] -> [a] -> [a] 
      merge (x:xs) []  = (x:xs) 
      merge []  (y:ys) = (y:ys) 
      merge (x:xs) (y:ys) = if x <= y 
            then x : merge (xs) (y:ys) 
            else y : merge (x:xs) ys 

以下是我比較了它們的效率：

insert_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int] 
merge_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int] 

他們都開始多在短暫的延遲後，打印出結果，但合併排序打印更快。我們知道，合併排序比大數據集的插入排序快得多。我認爲這將表現在他們如何給出結果（如長時間延遲與短時延遲），而不是他們如何輸出結果。是因爲我使用foldr進行插入排序嗎？現場背後是什麼？

編輯：Thx guys。自從我開始學習Haskell以來，我聽說過懶惰的評估，但還沒有掌握它。有人會用一個小數據集說明一點，比如[5,2,6,3,1,4]？自從第一個元素終於出現以後，如何在使用foldr完成排序之前輸出結果？

Answer 1

幕後的是懶惰的評價。在排序完成之前確定排序列表的開始，因此可以在工作完成之前輸出。由於合併速度更快，因此合併排序列表的打印速度更快。

按要求：如何排序[5,2,6,3,1,4]收益。爲簡潔起見，我使用insert_sort = foldr ins []。

insert_sort [5,2,6,3,1,4] 
    = foldr ins [] [5,2,6,3,1,4] 
    = 5 `ins` foldr ins [] [2,6,3,1,4] 
    = 5 `ins` 2 `ins` [6,3,1,4] ... 
    = 5 `ins` 2 `ins` 6 `ins` 3 `ins` 1 `ins` 4 `ins` [] 
    = 5 `ins` 2 `ins` 6 `ins` 3 `ins` 1 `ins` (4:[]) 
    = 5 `ins` 2 `ins` 6 `ins` 3 `ins` (1:4:[]) 
    = 5 `ins` 2 `ins` 6 `ins` (1 : (3 `ins` (4:[]))) 
    = 5 `ins` 2 `ins` (1 : (6 `ins` (3 `ins` (4:[])))) 
    = 5 `ins` (1 : (2 `ins` (6 `ins` (3 `ins` (4:[]))))) 
    = 1 : (5 `ins` (2 `ins` (6 `ins` (3 `ins` (4:[]))))) -- now 1 can be output 
    = 1 : (5 `ins` (2 `ins` (6 `ins` (3:4:[])))) 
    = 1 : (5 `ins` (2 `ins` (3 : (6 `ins` (4:[]))))) 
    = 1 : (5 `ins` (2 : (3 : (6 `ins` (4:[]))))) 
    = 1 : 2 : (5 `ins` (3 : (6 `ins` (4:[]))))   -- now 2 can be output 
    = 1 : 2 : 3 : (5 `ins` (6 `ins` (4:[])))    -- now 3 
    = 1 : 2 : 3 : (5 `ins` (4:6:[])) 
    = 1 : 2 : 3 : 4 : (5 `ins` (6:[]))     -- now 4 
    = 1 : 2 : 3 : 4 : 5 : 6 : []       -- done 

和排序合併（縮寫：merge = mg，merge_sort = ms）：

merge_sort [5,2,6,3,1,4] 
    = mg (ms [5,2,6]) (ms [3,1,4]) 
    = mg (mg (ms [5]) (ms [2,6])) (mg (ms [3]) (ms [1,4])) 
    = mg (mg [5] (mg [2] [6])) (mg [3] (mg [1] [4])) 
    = mg (mg [5] [2,6]) (mg [3] [1,4]) 
    = mg (2 : mg [5] [6]) (1 : mg [3] [4]) 
    = 1 : mg (2 : mg [5] [6]) (mg [3] [4])    -- now 1 can be output 
    = 1 : mg (2 : mg [5] [6]) [3,4] 
    = 1 : 2 : mg (mg [5] [6]) [3,4]      -- now 2 can be output 
    = 1 : 2 : mg [5,6] [3,4] 
    = 1 : 2 : 3 : mg [5,6] [4]       -- now 3 
    = 1 : 2 : 3 : 4 : mg [5,6] []       -- now 4 
    = 1 : 2 : 3 : 4 : 5 : 6 : []       -- now 5 and 6 

誠然，我已經採取了一些捷徑，但Haskell是不是隻有懶之一。

Answer 2

確定這裏是分解。你要我打印出來：

merge_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int] 

我碰巧知道這是一個列表。所以，首先我會打印出一個開放的括號

[ 

然後我會尋找列表的第一個元素，即打印出來，然後一個逗號。這意味着我必須開始評估該表達式，直到我能夠確定列表的第一個元素是什麼。

merge_sort THUNK0 

那麼現在我需要模式匹配。 THUNK匹配(x:[])或者它不。但我還不知道。所以我會評估一下這個thunk。我讓這個thunk產生前兩個隨機數（100000）。現在我知道它不符合第一個定義，所以我拿第二個定義merge_sort。

merge_sort keys = merge THUNK1 THUNK2 -- keys = THUNK0 

那麼這很容易......這只是一個調用合併。我會擴展這個定義。哦，廢話，有三個這可能匹配不同的模式。我想我應該評估THUNK1一點，看看它是否第一個定義的模式相匹配，(x:xs)

merge_sort (take THUNK3 THUNK0) 

回到merge_sort再次，我們是什麼？這意味着我需要評估(take THUNK3 THUNK0)就足以說明它是否與(x:[])匹配。哦，CRAP。 take是嚴格在其第一個參數...這意味着我必須完全評估 THUNK3。好吧......深呼吸......

len = length THUNK0 `div` 2 

現在，這裏是一個令人煩惱的案例。要計算THUNK0（這是一個列表）上的length，我必須展開整個SPOLE。我不必實際計算裏面的值，但是我需要充實整個列表的結構。當然，這是一次完成一個模式匹配，確定它是否是[]或(x:xs)。但總體來說，length是「脊椎嚴格」。

短暫的停頓，而我割肉出局100000元素列表

唷脊柱，得到了實現。現在我知道長度，這意味着我知道len = 500000。 THUNK0是終於充分評估！唷！我在哪裏？

merge_sort (take 500000 THUNK3) 

---

等等。 merge_sort將繼續儘可能地變得懶惰。對merge_sort的遞歸調用將盡可能慢。最終，爲了確定最外面的第一個元素merge_sort，我們需要知道遞歸調用merge_sort的第一個元素。並且要知道這些元素的第一個元素...我們需要後續遞歸調用的第一個元素等。因此，將會有大約O（n）工作完成，因爲每個元素都需要進行評估（執行隨機爲每一個號碼生成）。

然後，把它想象成一個比賽。每個元素都與另一個元素配對。 「獲勝」（最低）元素移動到下一輪（成爲遞歸調用的最低元素，即merge_sort s）。還有另外一場比賽的戰鬥人員數量是1/2，而那些人的（總數的1/4）移動到下一輪，等等。這也證明是O（n）工作，因爲（n/2）比較是在第一輪中進行的，隨後的回合變得太快而太快而不重要。 （總和1/2 + 1/4 + 1/8 ...收斂於1，這意味着執行總共n次比較。）

總而言之，O（n）工作需要執行以便最終產生第一個元素。需要爲後續元素執行額外工作，但總工作量爲O（n log（n））。

---

現在將其與insert_sort對比。試想一下它是如何工作的：它遍歷列表，並將每個元素「插入」到一個排序列表中。這意味着你不能確定知道排序的第一個元素是，直到你執行了最後一項工作，並且將最後一個元素（可能是最低的）插入到排序列表中。

我希望這清楚地說明了merge_sort如何並不需要執行所有的工作，以便開始生產結果，而insert_sort一樣。