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 ) を保証します。つまり、リストのような構造への O(1) 変換は、通常のリストよりも一定の係数だけ遅いunconsと考えることができます。つまり、O(n toListSB) コストは、リストを消費するにつれて段階的に増加します。

toListSBO(1) での作業が償却される理由がわかりません。右側のリストの長さは、連続する 2 のべき乗の間でどんどん大きくなっていきませんか?

4

1 に答える 1

1

リストの現在の長さが である場合N=2^M、2 倍にする操作が M 回ありました。最初の 2 倍には 1 時間単位、2 回目は 0 2 時間単位、3 回目は 4 というようにかかります。しかし、それは知られています（幾何学的累進和の公式）

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

したがって、1 回の操作あたりの償却コストはO(N)/N = O(1)

于 2016-09-16T09:51:12.157 に答える