マージソートよりも速く挿入ソートパズル私より

Question

ちょうど私の足がハスケルとソートアルゴリズムで濡れた。

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

それらの両方は、短い遅延の後に結果をプリントアウトして起動しますが、マージソートを印刷する多くの：私はここで私は彼らの効率を比較してみましょう挿入ソートを実装し、マージソート

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 

をしましたもっと早く。わかっているように、merge-sortは大きなデータセットの挿入ソートよりもはるかに高速です。私は、結果がどのように結果を出力するかではなく、短い結果と短い結果のような結果をどのように与えるかによって表示されると考えました。私はfoldrを挿入ソートに使っているのですか？シーンの背後には何がありますか？

EDIT：Thx人。私はハスケルを学び始めてから怠惰な評価を聞いたことがあるが、それでもハスケルを抱えている。誰かが小さなデータセットでもう少し詳しく説明しますか？[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:[])と一致するか、一致しません。しかし、私はまだ分かりません。だから私はそのサンクを少し評価するでしょう。私はそのサンクを最初の2つの乱数（100000のうち）を生成させる。今私は最初の定義と一致しないので、私はmerge_sortの2番目の定義を知っている知っている。

merge_sort keys = merge THUNK1 THUNK2 -- keys = THUNK0 

これは簡単です。それは、単なるマージの呼び出しです。私はその定義を拡張します。ああ、これは一致するかもしれない異なるパターン3つのがあります。私は再び(x:xs)

merge_sort (take THUNK3 THUNK0) 

戻るmerge_sortに、私はTHUNK1は少し評価し、それが最初の定義のパターンに一致するかどうかを見る必要がありますね、私たちはありますか？つまり、と一致するかどうかを知るのに十分なだけ(take THUNK3 THUNK0)を評価する必要があることを意味します。やばい。 takeはで、最初の議論ではです...つまり、私はを完全に評価する必要があります。 THUNK3。 OK ...深呼吸...

len = length THUNK0 `div` 2 

ここでは刺激的なケースです。 THUNK0（リスト）のlengthを計算するには、全スパインを展開する必要があります。私は実際に値を内部で計算する必要はありませんが、リスト全体の構造を明らかにする必要があります。これはもちろん、一度に1つのパターンマッチが行われ、[]か(x:xs)かを判断します。しかし、全体として、lengthは "背骨厳格"です。

短い休止私は100000要素のリスト

ふうの背骨を肉付けしながら、それが行われました。今私は長さを知っています。つまり、私はlen = 500000を知っています。 THUNK0は、最終的にはです！ピー！私はどこにいたのだろう？

merge_sort (take 500000 THUNK3) 

---

などがあります。 merge_sortは可能な限り怠惰にしようとし続けます。 merge_sortへの再帰呼び出しはできるだけ怠惰になります。最終的には、最も外側のmerge_sortの最初の要素を決定するために、両方の再帰呼び出しの最初の要素をmerge_sortに知る必要があります。そして、それらの最初の要素を知るためには、後続の再帰呼び出しの最初の要素などが必要です。したがって、すべての要素を評価する必要があるため、O（n）の作業が行われますそれぞれの番号生成）。

次に、トーナメントのように考える。各要素は別の要素とペアになっています。 「勝ち」（最も低い）要素は、次のラウンドに移動します（最小のmerge_sortへの再帰呼び出しの最初の要素になります）。戦闘員の半分が他の競争相手であり、のうちの1/2は、（合計の1/4）が次のラウンドに移動するなどである。これはまた、O（n）であることが判明した（n/2）比較は第1ラウンド中に実行され、後続ラウンドはあまりにも急速に小さくなって有意ではないからである。 （1/2 + 1/4 + 1/8の合計は1に収束し、合計n回の比較が行われることを意味する）。

すべてにおいて、O（n）作業が実行される必要がある最終的に第1の要素を生成する。次の要素について追加の作業を実行する必要がありますが、作業の総量はO（n log（n））になります。

---

これはinsert_sortとは対照的です。どのように動作するか考えてみましょう：リストをたどり、各要素をソートされたリストに「挿入」します。それはあなたがあなたが仕事の最後のビットを行い、ソートされたリストの中に（最低であったかもしれない）最後の要素を挿入するまで、ソートの最初の要素はが何であるかを確認してくださいに知ることができないことを意味します。

私は、これは明らかにmerge_sortがinsert_sortが行う一方で、結果の生産を開始するために、すべての作業を実行する必要がない方法を示します願っています。