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

Question

TL；博士

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

在我看来

• 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(二次)空间复杂度的结论正确吗？
• 如果是这样，为什么 GHC 为 fInits 和 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 能够使用私有(private)的、非融合版本的 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 的实现 is magical 。另一种可能性是使用 Data.Vector - 它可能使用切片来实现此类操作。