1

在Data.List模块中，使用了以下数据结构

{- We store a front list, a rear list, and the length of the queue.  Because we
only snoc onto the queue and never uncons, we know it's time to rotate when the
length of the queue plus 1 is a power of 2. Note that we rely on the value of
the length field only for performance.  In the unlikely event of overflow, the
performance will suffer but the semantics will remain correct.  -}

data SnocBuilder a = SnocBuilder {-# UNPACK #-} !Word [a] [a]

{- Smart constructor that rotates the builder when lp is one minus a power of
2. Does not rotate very small builders because doing so is not worth the
trouble. The lp < 255 test goes first because the power-of-2 test gives awful
branch prediction for very small n (there are 5 powers of 2 between 1 and
16). Putting the well-predicted lp < 255 test first avoids branching on the
power-of-2 test until powers of 2 have become sufficiently rare to be predicted
well. -}

{-# INLINE sb #-}
sb :: Word -> [a] -> [a] -> SnocBuilder a
sb lp f r
  | lp < 255 || (lp .&. (lp + 1)) /= 0 = SnocBuilder lp f r
  | otherwise                          = SnocBuilder lp (f ++ reverse r) []

-- The empty builder

emptySB :: SnocBuilder a
emptySB = SnocBuilder 0 [] []

-- Add an element to the end of a queue.

snocSB :: SnocBuilder a -> a -> SnocBuilder a
snocSB (SnocBuilder lp f r) x = sb (lp + 1) f (x:r)

-- Convert a builder to a list

toListSB :: SnocBuilder a -> [a]
toListSB (SnocBuilder _ f r) = f ++ reverse r

片段上方的评论提到如下：

队列保证（摊销） O(1)snoc和 O(1) uncons，这意味着我们可以toListSB将 O(1) 转换为类似列表的结构比普通列表慢的常数因子——我们支付 O(n ）随着我们使用列表而增加成本。

我不明白为什么toListSB在 O(1) 中工作是摊销的。右列表的长度不是在 2 的连续幂之间越来越大吗？

4

1 回答 1

1

如果当前列表长度为N=2^M，则有 M 次加倍操作。第一次加倍需要 1 个时间单位，第二次 0 需要 2 个时间单位，第三次 - 4 以此类推。但众所周知（几何级数和公式）

1 + 2 + 4 + 8 + ...+2^M = 2^(M+1) - 1 = O(N)

所以每次操作的摊销成本是O(N)/N = O(1)

于 2016-09-16T09:51:12.157 回答