init 和 tail 的空间复杂度是多少？

Question

TL; DR

在阅读了冈崎纯函数数据结构中关于持久性的文章并浏览了他关于单链表（这就是 Haskell 列表的实现方式）的说明性示例后，我对 和 的空间复杂性感到好奇。Data.Listinitstails

在我看来，这

• 的空间复杂度与其参数的长度成tails线性关系，并且
• 的空间复杂度inits是其参数长度的二次方，

但一个简单的基准表明情况并非如此。

基本原理

通过tails，可以共享原始列表。计算tails xs简单地包括沿着列表遍历xs并创建指向该列表的每个元素的新指针；无需xs在内存中重新创建部分内容。

相比之下，由于 的每个元素inits xs“以不同的方式结束”，因此不可能存在这种共享，并且 的所有可能的前缀xs必须在内存中从头开始重新创建。

基准

下面的简单基准测试显示两个函数之间的内存分配没有太大差异：

-- Main.hs

import Data.List (inits, tails)

main = do
    let intRange = [1 .. 10 ^ 4] :: [Int]
    print $ sum intRange
    print $ fInits intRange
    print $ fTails intRange

fInits :: [Int] -> Int
fInits = sum . map sum . inits

fTails :: [Int] -> Int
fTails = sum . map sum . tails

编译我的Main.hs文件后

ghc -prof -fprof-auto -O2 -rtsopts Main.hs

和跑步

./Main +RTS -p

该Main.prof文件报告如下：

COST CENTRE MODULE  %time %alloc

fInits      Main     60.1   64.9
fTails      Main     39.9   35.0

分配给的内存fInits和分配给的内存fTails是同一个数量级的……嗯……

到底是怎么回事？

• tails我关于（线性）和inits（二次）空间复杂度的结论是否正确？
• fInits如果是这样，为什么 GHC 为和分配大致相同的内存fTails？列表融合与此有关系吗？
• 或者我的基准有缺陷吗？

Answer 1

Haskell 报告中的实现inits与 4.7.0.1 (GHC 7.8.3) 之前使用的实现相同或几乎相同，但速度非常慢。特别是，fmap应用程序递归地堆叠，因此强制结果的连续元素变得越来越慢。

inits [1,2,3,4] = [] : fmap (1:) (inits [2,3,4])
 = [] : fmap (1:) ([] : fmap (2:) (inits [3,4]))
 = [] : [1] : fmap (1:) (fmap (2:) ([] : fmap (3:) (inits [4])))
....

Bertram Felgenhauer 探索的最简单的渐近最优实现基于应用take连续更大的参数：

inits xs = [] : go (1 :: Int) xs where
  go !l (_:ls) = take l xs : go (l+1) ls
  go _  []     = []

Felgenhauer 能够使用私有的非熔断版本来获得一些额外的性能take，但它仍然没有达到应有的速度。

在大多数情况下，以下非常简单的实现速度明显更快：

inits = map reverse . scanl (flip (:)) []

在一些奇怪的极端情况下（例如map head . inits），这个简单的实现渐近非最优。因此，我使用相同的技术编写了一个版本，但基于 Chris Okasaki 的银行家队列，它既是渐近最优的，又几乎一样快。Joachim Breitner 进一步优化了它，主要是使用严格的scanl'而不是通常的scanl，并且这个实现进入了 GHC 7.8.4。inits现在可以在 O(n) 时间内生成结果的主干；强制整个结果需要 O(n^2) 时间，因为没有任何 conses 可以在不同的初始段之间共享。如果你想要真正快得离谱inits，tails你最好的选择是使用Data.Sequence; Louis Wasserman 的实现非常神奇。另一种可能性是使用Data.Vector——它可能使用切片来完成这样的事情。