懒惰的评估和时间复杂性

Question

我正在寻找stackoverflow Non-Trivial Lazy Evaluation,这让我想到了Keegan McAllister的演讲:为什么要学习Haskell.在幻灯片8中,他显示了最小功能,定义为:

minimum = head . sort

并指出其复杂性为O(n).我不明白为什么如果通过替换排序是O(nlog n),复杂性被认为是线性的.帖子中引用的排序不能是线性的,因为它不假设数据的任何内容,因为线性排序方法需要它,例如计数排序.

懒惰的评价在这里发挥着神秘的作用吗？如果是这样,背后的解释是什么？

Answer 1

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

编辑:懒惰评估可以隐喻地被视为生产者/消费者习语¹,具有独立的记忆存储作为中介.我们编写的任何有效的定义都定义了一个生产者,它会在消费者要求的时候一点一点地产生它的输出 - 但不是更快.无论生成什么都是备忘的,因此如果另一个消费者以不同的速度消耗相同的输出,它将访问先前填充的相同存储.

当没有更多的消费者继续参考存储时,它会被垃圾收集.有时通过优化,编译器可以完全取消中间存储,从而削减中间人.

¹另见:Simple Generators诉 Oleg Kiselyov,Simon Peyton-Jones和Amr Sabry的懒惰评价.

Answer 2

假设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.

Answer 3

你已经得到了很多解决方案的答案head . sort.我只想添加一些更一般的声明.

通过热切的评估,各种算法的计算复杂性以简单的方式构成.例如,最小上限(LUB)f . g必须是和的LUB 之f和g.因此,您可以仅根据其LUB 来对待f和g作为黑匣子和理由.

懒惰的评价,但f . g可以有一个比LUB的总和更好的f和g的鲁布斯.你不能用黑盒推理来证明LUB; 您必须分析实现及其交互.

因此,经常提到的事实是,懒惰评估的复杂性比急切评估更难以推理.试想以下几点.假设您正在尝试改进其形式为的代码的渐近性能f . g.用一种急切的语言,你可以遵循明显的策略来做到这一点:选择更复杂的f和g,并首先改进它.如果你成功了,你就能成功f . g完成任务.

另一方面,在懒惰的语言中,您可以遇到以下情况:

• 你提高的更加复杂f和g,但f . g不会提高(甚至变得更坏).
• 你可以通过f . g无助于(或甚至恶化)f或g.

Answer 4

解释取决于实现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)因此永远不会被评估!

Answer 5

它并不那么神秘.您需要多少列表来排序以提供第一个元素？您需要找到最小元素,这可以在线性时间内轻松完成.碰巧,对于sort懒惰评估的一些实现,将为您执行此操作.

Answer 6

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

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).

编辑:正如Vitus在下面指出的那样,进行15次比较而不是10次与说不是O(n)不同.我只是意味着需要超过理论上的最小值.

Answer 7

在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()

运行脚本会给我们提供以下图表:

下线的斜率是..

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

..1.41324057(假设它是线性函数)