algorithm - 惰性求值和时间复杂度

Question

我正在查看 stackoverflow Non-Trivial Lazy Evaluation ，这让我看到了 Keegan McAllister 的演讲:Why learn Haskell .在幻灯片 8 中，他展示了最小函数，定义为:

minimum = head . sort

并声明其复杂度为 O(n)。我不明白为什么如果按替换排序是 O(nlog n)，那么复杂度是线性的。帖子中提到的排序不能是线性的，因为它不对数据做任何假设，而线性排序方法(例如计数排序)需要它。

懒惰评估在这里扮演着神秘的角色吗？如果是，背后的解释是什么？

Answer 1

在 最小 = head 中。 sort，sort 不会完全完成，因为它不会预先完成。 sort 只会在生成第一个元素所需的时候完成，这是 head 所要求的。

例如归并排序，首先将列表中的 n 个数字进行两两比较，然后将获胜者配对并比较(n/2 个数字)，然后是新的获胜者(n/4) 等。总的来说，O(n) 比较以产生最小元素。

mergesortBy less [] = []
mergesortBy less xs = head $ until (null.tail) pairs [[x] | x <- xs]
  where
    pairs (x:y:t) = merge x y : pairs t
    pairs xs      = xs
    merge (x:xs) (y:ys) | less y x  = y : merge (x:xs) ys
                        | otherwise = x : merge  xs (y:ys)
    merge  xs     []                = xs
    merge  []     ys                = ys

---

可以扩充上面的代码来标记它生成的每个数字，并在其生成中进行一些比较:

mgsort xs = go $ map ((,) 0) xs  where
  go [] = []
  go xs = head $ until (null.tail) pairs [[x] | x <- xs]   where
    ....
    merge ((a,b):xs) ((c,d):ys) 
            | (d < b)   = (a+c+1,d) : merge ((a+1,b):xs) ys    -- cumulative
            | otherwise = (a+c+1,b) : merge  xs ((c+1,d):ys)   --   cost
    ....

g n = concat [[a,b] | (a,b) <- zip [1,3..n] [n,n-2..1]]   -- a little scrambler

运行几个列表长度，我们看到 它确实是 ~ n:

*Main> map (fst . head . mgsort . g) [10, 20, 40, 80, 160, 1600]
[9,19,39,79,159,1599]

---

为了查看排序代码本身是否为 ~ n log n，我们将其更改为每个生成的数字仅携带其自己的成本，然后通过对整体求和得出总成本排序列表:

    merge ((a,b):xs) ((c,d):ys) 
            | (d < b)   = (c+1,d) : merge ((a+1,b):xs) ys      -- individual
            | otherwise = (a+1,b) : merge  xs ((c+1,d):ys)     --   cost

这里是各种长度列表的结果，

*Main> let xs = map (sum . map fst . mgsort . g) [20, 40, 80, 160, 320, 640]
[138,342,810,1866,4218,9402]

*Main> map (logBase 2) $ zipWith (/) (tail xs) xs
[1.309328,1.2439256,1.2039552,1.1766101,1.1564085]

以上显示empirical orders of growth对于增加的列表长度，n，它正在迅速减少，这通常由 ~ n log n 计算表现出来。另见 this blog post .这是一个快速的相关性检查:

*Main> let xs = [n*log n | n<- [20, 40, 80, 160, 320, 640]] in 
                                    map (logBase 2) $ zipWith (/) (tail xs) xs
[1.3002739,1.2484156,1.211859,1.1846942,1.1637106]

---

编辑:惰性求值可以隐喻地看作是一种生产者/消费者习语¹，以独立的内存存储作为中介。我们编写的任何生产性定义都定义了一个生产者，它将根据消费者的要求一点一点地生产其输出——但不会更早。无论产生什么都会被内存，这样如果另一个消费者以不同的速度消费相同的输出，它会访问相同的存储，之前已经填充。

当不再有消费者引用一 block 存储时，它就会被垃圾收集。有时，通过优化，编译器能够完全消除中间存储，将中间人排除在外。

¹ 另见:Simple Generators v. Lazy Evaluation作者:Oleg Kiselyov、Simon Peyton-Jones 和 Amr Sabry。