合并的方式 - 排序比插入排序更快困惑我

Question

刚刚在Haskell的排序算法中弄湿了我的脚.我已经实现了insert-sort和merge-sort

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]

它们都会在短暂的延迟后开始打印出结果,但合并排序的打印速度要快得多.众所周知,merge-sort比大数据集的插入排序快得多.我认为这将通过它们如何给出结果(如长时间延迟而非短时间)而不是它们如何打印结果来显示.是因为我foldr在插入排序中使用了吗？幕后背后是什么？

编辑:大家好.自从我开始学习Haskell之后,我就听说过懒惰的评估,但却得到了它的支持.任何人都会用一个小数据集说明一点,比如说[5,2,6,3,1,4]？foldr由于第一个元素最后出现,如何在完成排序之前输出结果？

Answer 1

现场背后是懒惰的评价.排序列表的开始在排序完成之前确定,因此可以在完成工作之前输出.由于mergesort更快,因此合并排序列表打印得更快.

根据要求:排序如何[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

现在这是一个令人恼火的案例.要计算lengthTHUNK0(这是一个列表),我必须扩展整个旋转.我不必实际计算内部的值,但我确实需要充实整个列表的结构.当然,这是一次完成一个模式匹配,确定它是否[],或(x:xs).但总的来说,length是"脊柱严格".

短暂的停顿,同时我充实了100000元素列表的脊柱

Phew,完成了.现在我知道长度,这意味着我知道len = 500000.THUNK0 终于全面评估了!唷!我在哪儿？

merge_sort (take 500000 THUNK3)

等等.merge_sort将继续努力尽可能地懒惰.递归调用merge_sort将尽可能地懒惰.最后,为了确定最外层的第一个元素merge_sort,我们需要知道两个递归调用的第一个元素merge_sort.并且要知道那些的第一个元素......我们将需要后续递归调用的第一个元素,等等.因此将完成O(n)工作,因为需要对每个元素进行求值(执行随机数生成)每一个人).

然后,把它想象成锦标赛.每个元素与另一个元素配对."获胜"(最低)元素移动到下一轮(成为递归调用最低merge_sorts 的第一个元素).还有另外一场比赛,战斗员数量的1/2,其中 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.