懒惰的评价和时间的复杂性
我正在四处寻找stackoverflow 非平凡的懒惰评估 ，这导致了我Keegan McAllister的介绍： 为什么学习Haskell 。 在幻灯片8中，他显示了最小函数，定义如下：
minimum = head . sort 并指出它的复杂性是O（n）。 我不明白为什么复杂性被说成是线性的，如果通过replacesorting是O（nlog n）。 文章中提到的sorting不能是线性的，因为它不会假设数据，因为线性sorting方法（比如计数sorting）会要求sorting。
懒惰的评价在这里扮演着一个神秘的angular色吗？ 如果是的话，背后的解释是什么？
在minimum = head . sort minimum = head . sort sort不会完全完成，因为它不会提前完成。 这种sort只能根据需要进行，以产生head要求的第一个元素。
在例如mergesort中，首先将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 xy : pairs t pairs xs = xs merge (x:xs) (y:ys) | less yx = 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 .... gn = 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]
为了查看sorting代码本身是否为〜n ~ n log n ，我们对其进行修改，使得每个生成的数字只携带自己的成本，然后通过总和在整个sorting列表上find总成本：
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 ~ n log n计算所performance的那样。 另见这个博客文章 。 这是一个快速的相关检查：
*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 ，以独立的存储为媒介。 我们所写的任何有生产力的定义都定义了一个生产者，它会按照消费者的要求一点一点地产出产出 – 但不会早。 无论生产什么都被logging下来，这样，如果另一个消费者以不同的速度消耗相同的产出，则它访问先前填充的相同的存储。
当没有更多的消费者指的是一个存储，它会被垃圾收集。 有的时候，优化编译器能够完全消除中间存储，把中间人剪掉。
1另见： 简单生成器诉 Oleg Kiselyov，Simon Peyton-Jones和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）时间计算的。
当然，正如德尔南指出的那样，复杂性取决于sort的实施。
你已经得到了很多解决head . sort的答案head . sort head . sort 。 我只是添加一些更一般的说法。
通过热切的评估，各种algorithm的计算复杂度以一种简单的方式组成。 例如， f . g的最小上界（LUB） f . g f . g必须是f和g的LUB之和。 因此，你可以把f和g当作黑盒子，并根据他们的LUB进行独占。
然而，懒惰的评估， f . g f . g的LUB可以比f和g的LUB的总和更好。 你不能用黑箱推理来certificateLUB; 你必须分析实现和他们的交互。
因此，经常引用的事实是，懒惰评价的复杂性比渴望评价要困难得多。 想想以下几点。 假设你正在尝试改进一个forms为f . g的代码段的渐进性能f . g f . g 。 用一种热切的语言，有一个明显的策略可以做到这一点：select更复杂的f和g ，并首先改进。 如果你成功了，你就成功了f . g f . g任务。
另一方面，在一种懒惰的语言，你可以有这些情况：
- 你提高了
f和g复杂度，但f . gf . g没有改善（甚至变坏 ）。 - 你可以改进
f . gf . g以某种不利于（甚至恶化 ）f或g。
解释取决于sort的实现，对于某些实现它不是真的。 例如，在列表末尾插入插入sorting，惰性评估不起作用。 因此，让我们select一个实现来查看，为了简单起见，我们使用selectsorting：
sort [] = [] sort (x:xs) = m : sort (delete m (x:xs)) where m = foldl (\xy -> if x < y then x else y) x xs
该函数清楚地使用O（n ^ 2）时间对列表进行sorting，但是由于head只需要列表的第一个元素，所以sort (delete x xs)就不会被评估！
这并不神秘。 你需要sorting多less清单来提供第一个元素？ 你需要find最小的元素，这可以很容易地在线性时间完成。 碰巧，对于一些懒惰评估的实现将为你做这个。
在实践中看到这一点的一个有趣的方式是跟踪比较function。
import Debug.Trace import Data.List myCmp xy = trace (" myCmp " ++ show x ++ " " ++ show y) $ compare xy 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比较find第一个元素，而不是应该被要求的10。 但是它还不到O（n log n）。
编辑：正如Vitus下面指出的，取15个比较而不是10个不同于O（n）。 我的意思是这比理论上的最低要多。
受保罗·约翰逊的回答的启发，我绘制了两个函数的增长率。 首先，我修改了他的代码，每个比较打印一个字符：
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 xy = trace "*" $ compare xy cmp2 xy = trace "#" $ compare xy 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()
运行脚本会给我们下面的图表：
下线的斜率是..
>>> import numpy as np >>> np.polyfit(x, map(lambda x:x[1], res), deg=1) array([ 1.41324057, -17.7512292 ])
.1.41324057（假设它是一个线性函数）
