避免多次列表遍历的好处

Question

我在函数式语言中看到过很多处理列表并构建一个函数来处理其元素的示例，以便在接收到某些额外值（通常不在生成函数时出现）后执行某些操作，例如：

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

  (“惰性求值”下的最后两个示例)

• 在严格的函数式语言中（如ML / OCaml）分阶段进行列表附加，以避免多次遍历第一个列表

  （标题为“Staging”的部分）

• 使用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中的它，更具体地说是“附加”的暂停版本，它遍历第一个列表并返回一个函数，以将第二个列表插入到尾部，而无需多次遍历第一个列表。令我惊讶的是，即使考虑到它仍然必须复制列表结构（因为每种情况下最后一个指针都不同），它仍然要快得多。

以下是map的变体，当更改函数时，应用于列表后速度应更快。由于Haskell不是严格的，我需要在cachedList中评估listMap [1..100000]的结果（或者也许不需要，在第一次应用之后，它仍应该在内存中）。

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

我知道在 Haskell 中，使用 comb x rest f = ... 和 comb x rest = \f -> ... 好像没有区别（如果我错了，请纠正我），但我选择这个版本来强调这个想法。

更新：经过一些简单的测试，我没有发现在 Haskell 中执行时间上的差异。那么问题仅适用于严格语言，比如 Scheme（至少是我测试过的 Racket 实现）和 ML。

- Alejandro Pulver

---

你确定是 listEq a b = foldr comb null b a 而不是 listEq a b = foldr comb null a b？这段代码来自哪里？ - Will Ness

关于分阶段编译 - 我认为它允许部分预编译。这样预编译的函数就包含了一些工作的部分提前完成。特别是，列表的遍历只进行一次，所有对单个元素的引用都从中提取并存储在一个已编译的函数中，随时可以使用。已编译的函数不会被遍历，只有解释函数才会被遍历。 - Will Ness

关于"a b"与"b a"，你是正确的，应该反过来。实际上，它们两边都可以删除，我保留它们的原因是因为在使用"let listEQ = ..."时，ghci会产生一个错误。如果它们顺序颠倒，我想要的部分求值就不会发生。 - Alejandro Pulver

“…不会发生”-这正是我建议的原因。但你在上次编辑中忘记改了 :) - Will Ness

一个相关的Haskell链接：http://www.haskell.org/haskellwiki/Runtime_compilation，在这里提到（https://dev59.com/10fRa4cB1Zd3GeqP_LHB#898763）。虽然在Haskell中我们无法明确区分柯里化声明和实际分期（编译），通常，如果声明了一个*命名*实体，它将被编译为一个单独的内存驻留实体；但这是一个*编译器*的事情（也称为实现细节）。 - Will Ness

Answer 1

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

遍历操作意味着进行大量的内存访问，因此您做得越少，效果就越好。合并遍历可以减少内存流量，并增加直线计算负载，从而提高性能。

具体来说，考虑以下计算列表上某些数学运算的程序：

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就是这样的编译器。

- Don Stewart

---

我很乐意再给一个+1，以便更清晰地扩展已经明确且有效的答案。 - ljedrz

Answer 2

还有一个非常重要的原因。如果您只遍历了一次列表，并且没有其他引用指向它，垃圾回收器可以在遍历时释放列表元素占用的内存。此外，如果列表是按需生成的，您始终只会有恒定的内存消耗。例如：

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 越大，所需内存越多。

然而，如果我们仅遍历列表一次，它将被惰性地创建，元素可以立即进行垃圾回收，因此无论列表有多大，程序只使用 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)

- Petr

---

有趣的是，你可以使用Spark并行计算sum和len，同时避免O(n)的空间复杂度。 - Don Stewart

@DonStewart 很好的观点。我想问一下，你能依赖它吗？我的意思是，你能确定一个火花不会因为某些原因落后于另一个火花（或者不会很快被启动），最终导致间隙占用 O(n) 的空间吗？ - Petr

我认为操作行为是非确定性的，因此您无法保证并行进展。 - Don Stewart

Answer 3

提前抱歉，我的回答可能会比较啰嗦。

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

几年前，我在思考GHC的操作语义，即STG机器。我问自己同样的问题——著名的“一次遍历”算法真的那么好吗？表面上看起来只是一次遍历，但在底层，你还有这个thunk链结构，它通常与原始列表非常相似。

我写了几个版本（严格程度不同）的著名RepMin问题——给定一个填满数字的树，生成相同形状的树，但将每个数字替换为所有数字的最小值。如果我没记错的话（记住——总是要自己验证！），天真的两次遍历算法比各种聪明的一次遍历算法表现得更快。

我还和西蒙·马洛（我们都在FP暑期学校期间）分享了我的观察结果，他说他们在GHC中使用这种方法。但并不是为了提高性能，正如你可能想的那样。相反，他说，对于一个大的AST（例如Haskell的AST），写下所有构造函数需要很多空间（以代码行计），因此他们通过只写下一个（语法）遍历来减少代码量。

个人建议避免使用这个技巧，因为如果你犯了一个错误，会得到一个非常不愉快的循环，很难调试。

- Roman Cheplyaka

Answer 4

因此，你问题的答案是“部分编译”。提前完成编译后，就不需要遍历列表来获取单个元素——所有引用都会提前找到并存储在预编译函数中。

至于你对该函数需要遍历的担忧，在解释型语言中确实存在。但编译可以消除这个问题。

在惰性存在的情况下，这种编码技巧可能会导致相反的结果。例如，Haskell GHC编译器具有完整的方程式，能够执行各种优化，从而完全消除列表，并将代码转换为等效的循环形式。当我们使用例如-O2开关编译代码时，就会发生这种情况。

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

- Will Ness

---

当你说“部分编译”时，我认为这不是在运行时完成的（与某些动态语言具有JIT相反）。 所以你的意思是它只在编译时已知列表时才能工作，或者甚至可以优化重用列表以在运行时已知吗？ - Alejandro Pulver

@user1871626，有一些系统可以进行运行时编译，例如Common LISP。在那里，它是显式完成的，例如有一个函数fun，您可以调用(compile 'fun)（在REPL提示符下）进行编译，编译后的代码将链接到运行时。分阶段技术非常适合这种情况。一旦被编译，该函数就包含了列表的预处理知识，并且多次应用已编译的函数更加高效，正如您提供的书籍所解释的那样。 - Will Ness