懒惰评价与时间复杂性

我看了一下堆栈溢出 非平凡的懒惰评价，然后找到了 Keegan McAllister 的演示文稿: 为什么要学 Haskell。在幻灯片8中，他展示了最小函数，定义为:

minimum = head . sort

并指出它的复杂性是 O (n)。我不明白为什么说复杂度是线性的，如果按替换排序是 O (nlogn)。文章中提到的排序不能是线性的，因为它不假设任何关于数据的东西，因为它是线性排序方法(如计数排序)所需要的。

懒惰评价在这里扮演了一个神秘的角色吗? 如果是的话，它背后的原因是什么？

4793 次浏览
小开

没那么神秘。为了交付第一个元素，需要对列表进行多少排序？您需要找到最小元素，这很容易在线性时间内完成。碰巧，对于 sort的某些实现，惰性计算将为您做到这一点。

小开
最佳答案

在 minimum = 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]

上面显示的 增长的经验阶数增加长度的列表，n，这是迅速减少，通常是由 ~ n log n计算。参见 这篇博文。下面是一个快速的相关性检查:

*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]

懒惰评价可以隐喻为一种生产者/消费者习惯用法 1，以独立的制表存储为中介。我们所写的任何生产性定义，都定义了一个生产者，当消费者提出要求时，这个生产者会一点一点地生产出它的产品，但不会更快。生产的任何产品都是制表的，因此，如果另一个消费者以不同的速度消费相同的产品，它将访问以前填充的相同存储器。

当没有更多的消费者继续指向一个存储块时，它将被垃圾收集。有时编译器通过优化就能完全取消中间存储，省去中间人。

参见: 简单生成器与懒惰评估 by Oleg Kiselyov，Simon Peyton-Jones and Amr Sabry。

小开

假设 minimum' :: (Ord a) => [a] -> (a, [a])是一个函数，它返回列表中最小的元素以及删除了该元素的列表。显然，这可以在 O (n)时间内完成。如果然后将 sort定义为

sort :: (Ord a) => [a] -> [a]
sort xs = xmin:(sort xs')
where
(xmin, xs') = minimum' xs

那么延迟计算意味着在 (head . sort) xs中只计算第一个元素。如您所见，这个元素就是对 minimum' xs的第一个元素，它是在 O (n)时间内计算出来的。

当然，正如 delnan 所指出的，复杂性取决于 sort的实现。

小开

这种解释取决于 sort的实现，对于某些实现，这种解释是不正确的。例如，对于在列表末尾插入的插入排序，延迟计算没有帮助。因此，让我们选择一个要查看的实现，为了简单起见，让我们使用选择排序:

sort [] = []
sort (x:xs) = m : sort (delete m (x:xs))
where m = foldl (\x y -> if x < y then x else y) x xs

函数显然使用 O (n ^ 2)时间对列表进行排序，但是由于 head只需要列表的第一个元素，因此从不计算 sort (delete x xs)！

小开

在实践中看到这一点的一个有趣的方法是跟踪比较函数。

import Debug.Trace
import Data.List


myCmp x y = trace (" myCmp " ++ show x ++ " " ++ show y) $ compare x y


xs = [5,8,1,3,0,54,2,5,2,98,7]


main = do
print "Sorting entire list"
print $ sortBy myCmp xs


print "Head of sorted list"
print $ head $ sortBy myCmp xs

首先，请注意整个列表的输出与跟踪消息交织的方式。其次，注意在仅计算头部时跟踪消息是如何相似的。

我刚刚在 Ghci 运行了一下，它不完全是 O (n) : 它需要15个比较才能找到第一个元素，而不是应该需要的10个。但它仍然小于 O (n log n)。

编辑: 正如维特斯在下面指出的那样，用15个比较代替10个比较并不等于说它不是 O (n)。我的意思是，这需要比理论上的最小值更多的东西。

小开

您已经得到了许多解决 head . sort具体问题的答案。我再加几句一般性陈述。

随着热切评价，各种算法的计算复杂度以一种简单的方式组成。例如，f . g的最小上限(LUB)必须是 f和 g的 LUB 之和。因此，您可以将 f和 g视为黑盒，并且仅根据它们的 LUB 进行推理。

然而，使用延迟计算，f . g的 LUB 可以比 f和 g的 LUB 之和更好。不能使用黑盒推理来证明 LUB; 必须分析实现及其交互。

因此，经常被引用的事实是，懒惰评估的复杂性比急于评估的复杂性更难推断。想想下面这些。假设您试图改进一段形式为 f . g的代码的渐近性能。在渴望学习的语言中，您可以遵循一个明显的策略来做到这一点: 选择更复杂的 f和 g，并首先改进它们。如果你成功了，你就完成了 f . g任务。

另一方面，在一种懒惰的语言中，你可能会遇到以下情况:

  • 你改善了更复杂的 f和 g，但是 f . g没有改善(甚至得到 更糟)。
  • 你可以改善 f . g的方式不帮助(甚至 更糟了) f或 g。
小开

受 Paul Johnson 答案的启发，我绘制了这两个函数的增长率。首先，我修改了他的代码，每次比较打印一个字符:

import System.Random
import Debug.Trace
import Data.List
import System.Environment


rs n = do
gen <- newStdGen
let ns = randoms gen :: [Int]
return $ take n ns


cmp1 x y = trace "*" $ compare x y
cmp2 x y = trace "#" $ compare x y


main = do
n <- fmap (read . (!!0)) getArgs
xs <- rs n
print "Sorting entire list"
print $ sortBy cmp1 xs


print "Head of sorted list"
print $ head $ sortBy cmp2 xs

计算 *和 #字符数，我们可以在均匀间隔的点(请原谅我的 Python)采样比较计数:

import matplotlib.pyplot as plt
import numpy as np
import envoy


res = []
x = range(10,500000,10000)
for i in x:
r = envoy.run('./sortCount %i' % i)
res.append((r.std_err.count('*'), r.std_err.count('#')))


plt.plot(x, map(lambda x:x[0], res), label="sort")
plt.plot(x, map(lambda x:x[1], res), label="minimum")
plt.plot(x, x*np.log2(x), label="n*log(n)")
plt.plot(x, x, label="n")
plt.legend()
plt.show()

运行这个脚本可以得到如下图表:

growth rates

下面这条线的斜率是. 。

>>> import numpy as np
>>> np.polyfit(x, map(lambda x:x[1], res), deg=1)
array([  1.41324057, -17.7512292 ])

1.41324057(假设它是一个线性函数)


提交答案