inits和tails的空间复杂度是什么？

Question

简短概述

在阅读Okasaki的Purely Functional Data Structures中关于persistence的内容以及他关于单向链表（这是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大致分配相同的内存？这与列表融合有关吗？
• 还是我的基准测试存在缺陷？

- jub0bs

---

我的唯一猜测是：中间的 Int 没有被优化掉，所以 fTails 也会为它们进行 O(n^2) 的分配。必须查看核心代码才能确定（我手头没有 ghc）。 - user395760

@delnan 谢谢。我还不习惯检查核心，但我会研究一下的。 - jub0bs

@AndrásKovács (ಠ_ರ) ? 你是在使用和我相同的基准测试吗？你使用的 GHC 版本是哪个？我正在使用 GHC 7.10.1。 - jub0bs

请忽略我的 GHC 7.8.3 的结果（以及其他人的结果）。 GHC 7.8.3 存在一个 bug，inits 函数运行非常缓慢。该问题已经在 7.8.4 版本中得到了修复。 - Cirdec

@Jubobs 当我使用 +RTS -s 时，我只是将其中一个注释掉。使用 RTS -p 时，我的结果与你的类似。 - András Kovács

Answer 1

Haskell报告中的inits实现与base 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 的 Banker's 队列的版本，它既是渐进最优的，又几乎和原来的实现一样快。Joachim Breitner 进一步优化了它，主要是通过使用严格的 scanl' 而不是通常的 scanl，这个实现被纳入了 GHC 7.8.4 中。现在，inits 可以在 O(n) 时间内生成结果的脊柱；强制整个结果需要 O(n^2) 时间，因为不同的初始段之间不能共享任何 cons。如果你想要真正荒谬地快速的 inits 和 tails，最好的选择是使用 Data.Sequence；Louis Wasserman 的实现神奇。另一种可能性是使用 Data.Vector——它可能会使用切片来处理这些东西。

- dfeuer

---

非常全面的回答。谢谢。 - jub0bs