28

我在函数式语言中看到了许多关于处理列表和构造函数以在接收到一些附加值（通常在生成函数时不存在）后对其元素执行某些操作的示例，例如：

  • 计算每个元素与平均值之间的差异

    （“懒惰评估”下的最后两个例子）

  • 使用严格的函数式语言（例如 ML/OCaml）暂存列表追加，以避免多次遍历第一个列表

    （标题为“分期”的部分）

  • 使用 foldr 将列表与另一个列表进行比较（即生成一个函数以将另一个列表与第一个列表进行比较）

    listEq a b = foldr comb null a b
  where comb x frec [] = False
        comb x frec (e:es) = x == e && frec es
cmp1To10 = listEq [1..10]

在所有这些示例中，作者通常都提到只遍历原始列表一次的好处。但是我不能不让自己思考“当然，不是遍历 N 个元素的列表，而是遍历 N 个评估链，那又怎样？”。我知道它一定有一些好处，有人可以解释一下吗？

编辑：感谢两位的回答。不幸的是，这不是我想知道的。我将尝试澄清我的问题，因此它不会与（更常见的）关于创建中间列表的问题（我已经在各个地方读到过）混淆。也感谢您更正我的帖子格式。

我对您构造要应用于列表的函数的情况感兴趣，在这种情况下您还没有评估结果的必要值（无论是否是列表）。那么你就无法避免生成对每个列表元素的引用（即使不再引用列表结构）。而且您拥有与以前相同的内存访问权限，但您不必解构列表（模式匹配）。

例如，请参阅上述 ML 书中的“暂存”章节。我已经在 ML 和 Racket 中尝试过，更具体地说是“append”的分段版本，它遍历第一个列表并返回一个在尾部插入第二个列表的函数，而无需多次遍历第一个列表。令我惊讶的是，即使考虑到它仍然必须复制列表结构，因为最后一个指针在每种情况下都不同，它也快得多。

以下是 map 的一种变体，它应用于列表后，更改功能时应该更快。由于 Haskell 并不严格，我将不得不强制对listMap [1..100000]in进行评估cachedList（或者可能不强制，因为在第一个应用程序之后它仍然应该在内存中）。

listMap = foldr comb (const [])
  where comb x rest = \f -> f x : rest f

cachedList = listMap [1..100000]
doubles = cachedList (2*)
squares = cachedList (\x -> x*x)

-- print doubles and squares
-- ...

comb x rest f = ...我知道在 Haskell 中使用vs并没有什么不同（如果我错了，请纠正我）comb x rest = \f -> ...，但我选择了这个版本来强调这个想法。

更新：经过一些简单的测试，我在 Haskell 中找不到任何执行时间的差异。那么问题只是关于严格的语言，例如 Scheme（至少是我测试过的 Racket 实现）和 ML。

4

4 回答 4

27

基本上，在循环体中执行一些额外的算术指令比执行一些额外的内存获取便宜。

遍历意味着做大量的内存访问，所以你做的越少越好。遍历的融合减少了内存流量，并增加了直线计算负载，因此您可以获得更好的性能。

具体来说，考虑这个程序来计算列表上的一些数学：

go :: [Int] -> [Int]
go = map (+2) . map (^3)

显然，我们用列表的两次遍历来设计它。在第一次和第二次遍历之间，将结果存储在中间数据结构中。但是，它是一个惰性结构，因此只消耗O(1)内存。

现在，Haskell 编译器立即将两个循环融合为：

go = map ((+2) . (^3))

这是为什么？毕竟，两者都很O(n)复杂，对吧？区别在于常数因子。

考虑到这种抽象：对于第一个管道的每个步骤，我们执行以下操作：

  i <- read memory          -- cost M
  j = i ^ 3                 -- cost A
  write memory j            -- cost M
  k <- read memory          -- cost M
  l = k + 2                 -- cost A
  write memory l            -- cost M

所以我们支付 4 次内存访问和 2 次算术运算。

对于融合结果，我们有：

  i <- read memory          -- cost M
  j = (i ^ 3) + 2           -- cost 2A
  write memory j            -- cost M

其中A和M是在 ALU 和内存访问上进行数学运算的常数因子。

还有其他常数因子（两个循环分支）而不是一个。

因此，除非内存访问是免费的（远非如此），否则第二个版本总是更快。

请注意，对不可变序列进行操作的编译器可以实现数组融合，即为您执行此操作的转换。GHC就是这样一个编译器。

于 2012-12-03T17:28:59.067 回答
16

还有一个非常重要的原因。如果你只遍历一个列表一次，并且没有其他引用，那么 GC 可以在你遍历列表元素时释放它们所占用的内存。此外，如果列表是延迟生成的，那么您总是只有恒定的内存消耗。例如 

import Data.List

main = do
    let xs = [1..10000000]
        sum = foldl' (+) 0 xs
        len = foldl' (\_ -> (+ 1)) 0 xs
    print (sum / len)

计算sum，但需要保留对的引用xs并且它所占用的内存不能被释放，因为它需要len稍后计算。（或反之亦然。）所以程序消耗相当多的内存，越大xs它需要的内存就越多。

但是，如果我们只遍历一次列表，它是惰性创建的，并且元素可以立即被GC，所以无论列表有多大，程序都只O(1)占用内存。

{-# LANGUAGE BangPatterns #-}
import Data.List

main = do
    let xs = [1..10000000]
        (sum, len) = foldl' (\(!s,!l) x -> (s + x, l + 1)) (0, 0) xs
    print (sum / len)
于 2012-12-03T20:37:33.093 回答
3

提前为一个健谈风格的答案道歉。

这可能很明显，但如果我们谈论的是性能，您应该始终通过测量来验证假设。

几年前，我在思考 GHC（STG 机器）的操作语义。我也问过自己同样的问题——著名的“单次遍历”算法肯定不是很好吗？它只是表面上看起来像一次遍历，但在引擎盖下你也有这个通常与原始列表非常相似的链式结构。

我为著名的 RepMin 问题写了几个版本（严格程度不同）——给定一棵充满数字的树，生成相同形状的树，但用所有数字中的最小值替换每个数字。如果我没记错的话（记住——总是自己验证东西！），朴素的两次遍历算法比各种聪明的一次遍历算法执行得快得多。

我还与 Simon Marlow 分享了我的观察结果（那段时间我们都在 FP 暑期学校），他说他们在 GHC 中使用了这种方法。但不是像您想象的那样提高性能。相反，他说，对于一个大的 AST（比如 Haskell 的那个），写下所有的构造函数会占用很多空间（就代码行而言），所以他们只是通过写下一个（句法）遍历来减少代码量.

我个人避免这个技巧，因为如果你犯了一个错误，你会得到一个循环，这是一个非常不愉快的调试事情。

于 2012-12-09T17:36:02.053 回答
2

所以你的问题的答案是，部分编译。提前完成，这样就无需遍历列表来获取各个元素 - 所有引用都提前找到并存储在预编译函数中。

至于您对也需要遍历该函数的担忧，这在解释语言中是正确的。但是编译消除了这个问题。

在存在懒惰的情况下，这种编码技巧可能会导致相反的结果。拥有完整的方程，例如 Haskell GHC 编译器能够执行各种优化，这基本上完全消除了列表并将代码转换为等效的循环。当我们使用例如-O2switch 编译代码时会发生这种情况。

写出部分方程可能会阻止这种编译器优化并强制实际创建函数——结果代码会大大减慢。我尝试了您的cachedList代码，看到 0.01 秒的执行时间变成了 0.20 秒（现在不记得我所做的确切测试）。

于 2012-12-14T18:59:53.867 回答