避免多个列表遍历的好处

Question

我已经在函数式语言中看到很多关于处理列表和构造函数的函数,这些函数在接收到一些额外的值(通常在生成函数时不存在)时对其元素执行某些操作,例如:

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

  ("懒惰评估"下的最后两个例子)

• 暂存列表以严格的函数语言(如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中尝试过它,更具体地说是"追加"的阶段版本,它遍历第一个列表并返回一个函数,在尾部插入第二个列表,而不会多次遍历第一个列表.令我惊讶的是,即使考虑到它仍然必须复制列表结构,因为最后一个指针在每种情况下都不同,所以它要快得多.

以下是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
-- ...

我知道在Haskell中使用comb x rest f = ...vs 并没有什么区别(请纠正我,如果我错了)comb x rest = \f -> ...,但我选择这个版本来强调这个想法.

更新:在一些简单的测试之后,我在Haskell中找不到执行时间的任何差异.那么问题只是关于严格的语言,例如Scheme(至少是我测试它的Racket实现)和ML.

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就是这样一个编译器.

Answer 2

还有另一个非常重要的原因.如果只遍历列表一次,并且没有其它引用,则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)

Answer 3

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

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

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

写出部分方程可能会阻止编译器优化并强制实际创建函数 - 从而导致生成的代码急剧减慢。我尝试了你的cachedList代码，发现 0.01 秒的执行时间变成了 0.20 秒（现在不记得我所做的具体测试）。