72

我正在查看 stackoverflow Non-Trivial Lazy Evaluation，这让我看到了 Keegan McAllister 的演讲：为什么要学习 Haskell。在幻灯片 8 中，他展示了最小函数，定义为：

minimum = head . sort

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

懒惰的评估在这里起到了神秘的作用吗？如果是这样，背后的解释是什么？

4

7 回答 7

60

在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，以独立的记忆存储作为中介。我们编写的任何生产性定义都定义了一个生产者，该生产者将在其消费者要求时，一点一点地生产其输出 - 但不会更快。无论生产什么都被记忆，因此如果另一个消费者以不同的速度消费相同的输出，它会访问相同的存储空间，之前已填充。

当没有更多的消费者引用一个存储时，它会被垃圾收集。有时，通过优化编译器能够完全取消中间存储，从而将中间人排除在外。

1另见：Oleg Kiselyov、Simon Peyton-Jones 和 Amr Sabry 的Simple Generators v. Lazy Evaluation 。

于 2012-08-21T15:08:50.090 回答
21

假设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只计算第一个元素。如您所见，此元素只是 pair 的（第一个元素）minimum' xs，它是在 O(n) 时间内计算的。

当然，正如 delnan 指出的那样，复杂性取决于sort.

于 2012-08-21T15:14:38.917 回答
14

您已经获得了大量解决head . sort. 我将添加一些更一般的陈述。

通过热切评估，各种算法的计算复杂性以一种简单的方式构成。例如， 的最小上界 (LUB)f . g必须是 和 的LUB 之f和g。因此，您可以将f和g视为黑盒并仅根据其 LUB 进行推理。

然而，通过惰性求值，f . gLUB 可以比 和 的 LUB 之f和更好g。您不能使用黑盒推理来证明 LUB；您必须分析实现及其交互。

因此，经常被引用的事实是惰性求值的复杂性比急切求值更难推理。想想以下。假设您正在尝试提高一段代码的渐近性能，其形式为f . g. 在急切的语言中，您可以遵循明显的策略来执行此操作：选择更复杂的fand g，然后先改进它。如果你成功了，你就成功了f . g。

另一方面，在惰性语言中，您可能会遇到以下情况：

  • 您改进了更复杂的fand g，但f . g没有改进（甚至变得更糟）。
  • 您可以f . g以无济于事（甚至恶化）f或g.
于 2012-08-21T19:15:01.473 回答
12

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

于 2012-08-21T15:17:53.143 回答
8

它没有那么神秘。您需要对列表的多少进行排序才能提供第一个元素？您需要找到最小元素，这可以在线性时间内轻松完成。sort碰巧的是，惰性求值的某些实现会为您执行此操作。

于 2012-08-21T15:08:25.217 回答
7

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

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) 不同。我的意思是它需要超过理论最小值。

于 2012-08-21T16:43:06.877 回答
6

受保罗约翰逊回答的启发，我绘制了这两个函数的增长率。首先，我修改了他的代码，每次比较打印一个字符：

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（假设它是一个线性函数）

于 2012-08-24T06:05:48.460 回答