"inits"的高效版本

Question

那是, inits "abc" == ["","a","ab","abc"]

有一个标准版本的initsin Data.List,但下面我自己写了一个版本:

myInits = f id
 where
  f start (l:ls) = (start []):(f (start . (l:)) ls)
  f start [] = [(start [])]

虽然我的版本比标准版本简单得多,但我怀疑它因效率原因而不太好.我怀疑,当myInits l完全评估时,它需要O(n^2)空间.举例来说myTails,实现tails:

myTails a@(_:ls) = a:(myTails ls)
myTails [] = [[]]

这几乎与标准版本完全相同,我怀疑O(n)通过重用列表的尾部来实现空间.

有人能解释一下:

1. 为什么我的版本inits不好.
2. 为什么另一种方法更好(无论是标准方法Data.List还是您自己方法).

Answer 1

您myInits使用称为差异列表的技术来生成在线性时间内构建列表的函数.我相信,但还没有检查,将运行时间完全评估myInits是O(n^2)需要O(n^2)空间.全面评估inits还需要O(n^2)运行时间和空间.任何版本inits都需要O(n^2)空间; 列表构建,:并且[]只能共享它们的尾部,并且结果之间没有共同的尾巴inits.initsin 的版本Data.List使用一个分摊的时间O(1)队列,就像在相关答案的后半部分中描述的更简单的队列.将Snoc在源代码中引用Data.List的文字游戏上Cons(另一个名称:)向后 - 能够将项目附加到列表的末尾.

简单地试验这些函数表明,myInits当在大型列表上稀疏地使用时,表现令人满意.在我的计算机上,在ghci中,myInits [1..] !! 8000000几秒钟就会产生结果.不幸的是,我有horrifyingly低效执行与GHC 7.8.3出货,所以我不能比较myInits来inits.

严格

之间存在一个很大的区别myInits与inits和之间myTails和tails.当应用于undefined或_|_(发音为"bottom",我们使用的另一个符号undefined)时,它们具有不同的含义.

inits具有严格性属性inits (xs ++ _|_) = inits xs ++ _|_,当xs空列表[]表示inits在应用时仍会产生至少一个结果undefined

inits (xs ++ _|_) = inits xs ++ _|_
inits ([] ++ _|_) = inits [] ++ _|_
inits        _|_  = [[]]     ++ _|_
inits        _|_  =  []      :  _|_

我们可以通过实验看到这一点

> head . inits $ undefined
[]

myInits 对于空列表或更长的列表,没有此属性.

> head $ myInits undefined
*** Exception: Prelude.undefined

> take 3 $ myInits ([1,2] ++ undefined)
[[],[1]*** Exception: Prelude.undefined

如果我们意识到在任何一个分支f中myInits都会产生start [],我们可以解决这个问题 因此,我们可以延迟模式匹配,直到需要决定下一步做什么.

myInits' = f id
 where
  f start list = (start []):
                 case list of
                     (l:ls) -> f (start . (l:)) ls
                     []     -> []

懒惰的增加使得myInits'工作就像inits.

> head $ myInits' undefined
[]

> take 3 $ myInits' ([1,2] ++ undefined)
[[],[1],[1,2]]

同样,你myTails和tailsinData.List之间的区别在于,在tails决定是否有剩余的列表之前,将整个列表作为第一个结果.文档表示它遵守tails _|_ = _|_ : _|_,但它实际上遵循一个更难以轻易描述的更强大的规则.

Answer 2

前缀函数构建可以作为实际列表与它们的具体化分开:

diffInits = map ($ []) . scanl (\a x -> a . (x:)) id

这明显更快(在GHCi内部测试),并且比您的版本更懒惰(参见Cirdec的讨论答案):

diffInits        _|_  == []           :  _|_
diffInits (xs ++ _|_) == diffInits xs ++ _|_