功能阵列倍增堆栈的摊销

Question

我正在研究紧凑堆栈的想法——随着其大小的增加，其空间需求接近数组的空间需求。候选结构：

data Stack a
  = Empty
  | Zero (Stack a)
  | One !(SmallArray a) (Stack a)
  | Two !(SmallArray a) !(SmallArray a) (Stack a)
-- Invariant: the array size at depth `n` is `2^n`.

push :: a -> Stack a -> Stack a
push = pushA . pure

pushA :: SmallArray a -> Stack a -> Stack a
pushA sa Empty = One sa Empty
pushA sa (Zero more) = One sa more
pushA sa1 (One sa2 more) = Two sa1 sa2 more
pushA sa1 (Two sa2 sa3 more) = One sa1 (pushA (sa2 <> sa3) more)

pop :: Stack a -> Maybe (a, Stack a)
pop stk = do
  (sa, stk') <- popA stk
  hd <- indexSmallArrayM sa 0
  Just (hd, stk')

popA :: Stack a -> Maybe (SmallArray a, Stack a)
popA Empty = Nothing
popA (Zero more) = do
  (sa, more') <- popA more
  let !(sa1, sa2) = -- split sa in two
  Just (sa1, One sa2 more')
popA (One sa more) = Just (sa, Zero more)
popA (Two sa1 sa2 more) = Just (sa1, One sa2 more)

一些数值实验表明，O(log n)对于一系列n 推送，我可以获得每个操作的平均成本。但是是否可以将这种结构分析为具有O(log n)每次推送或弹出的成本？或者如果没有，可以为类似的结构做到这一点吗？我一直无法找到合适的借方不变量。棘手的情况似乎是一系列Two节点后跟一个One节点，但我可能只是在接近这一切都是错误的。

Answer 1

我相信我已经找到办法了。我在问题中建议的数字系统结果证明不是正确的；它不支持O(log n) pop（或者至少不简单地这样做）。我们可以通过从 0/1/2 冗余二进制切换到 1/2/3 冗余二进制来修补这个问题。

-- Note the lazy field in the Two constructor.
data Stack a
  = Empty
  | One !(SmallArray a) !(Stack a)
  | Two !(SmallArray a) !(SmallArray a) (Stack a)
  | Three !(SmallArray a) !(SmallArray a) !(SmallArray a) !(Stack a)

push :: a -> Stack a -> Stack a
push = pushA . pure

pushA :: SmallArray a -> Stack a -> Stack a
pushA sa Empty = One sa Empty
pushA sa1 (One sa2 more) = Two sa1 sa2 more
pushA sa1 (Two sa2 sa3 more) = Three sa1 sa2 sa3 more
pushA sa1 (Three sa2 sa3 sa4 more) = Two sa1 sa2 (pushA (sa3 <> sa4) more)

pop :: Stack a -> Maybe (a, Stack a)
pop stk = do
  ConsA sa stk' <- pure $ popA stk
  hd <- indexSmallArrayM sa 0
  Just (hd, stk')

data ViewA a = EmptyA | ConsA !(SmallArray a) (Stack a)

popA :: Stack a -> ViewA a
popA Empty = EmptyA
popA (Three sa1 sa2 sa3 more) = ConsA sa1 (Two sa2 sa3 more)
popA (Two sa1 sa2 more) = ConsA sa1 (One sa2 more)
popA (One sa more) = ConsA sa $
  case popA more of
    EmptyA -> Empty
    ConsA sa1 more' -> Two sa2 sa3 more'
      where
        len' = sizeofSmallArray sa1 `quot` 2
        sa2 = cloneSmallArray sa1 0 len'
        sa3 = cloneSmallArray sa1 len' len'

证明其具有所需的摊销范围的第一个重要步骤是选择借方不变式[*]。这让我困惑了很长一段时间，但我想我已经明白了。

借方不变性Stack：我们允许节点中的惰性节点Two与该节点和所有早期节点中存储的元素一样多的借方Two。

定理

push并按摊销时间pop运行O(log n)。

校样草图

推

我们依次考虑每种情况。

• Empty总是微不足道的。

• One：我们增加了以下借记限额。

• Two：我们将以下节点的借方限额减少 1 个单位。我们O(log n)支付费用以清偿超额借方。

• Three：这是 的棘手情况push。我们有一些节点，Three后面还有其他节点。对于每个Three节点，我们暂停s数组加倍工作。我们使用从新节点中的元素获得的额外借记限额来支付费用Two。当我们到达链条的末端时Three，我们需要做一些有趣的事情。我们可能需要下面的全部借方限额，因此我们使用借方传递将最终数组附加的借方分散到所有早期节点。

  最后，我们有Empty、One、 或Two。如果我们有Empty或One，我们就完成了。如果我们有Two，则更改它以Three减少以下借记限额。但我们还从所有已更改为 s 的 s中获得以下借方津贴！我们的净损失借方准备金仅为 1，所以我们是黄金。ThreeTwo

流行音乐

我们再次通过案例进行。

• Empty是微不足道的。
• Three：我们增加以下借记限额。
• Two：我们将某些节点的借方限额减少 1 个单位；支付 O(log n) 来清偿多余的借方。
• One: 这个是硬案例。我们有一些节点，One后面还有其他节点。对于每个One，我们执行一次分割。我们通过借记来支付这些费用，并从根本上免除这些费用。最后，我们遇到了与 类似的情况push：棘手的情况以 结束，我们使用所有新的s 来支付最终 的损失这一Two事实。TwoTwo

紧凑

人们可能会担心结构中会累积足够多的重击，从而否定基于数组的表示的紧凑性。幸运的是，事实并非如此。thunk 只能出现在Stack节点中Two。但对该节点的任何操作都会将其变成 aOne或 a Three，从而强制Stack. 因此，thunk 永远不会在链中累积，并且每个节点的 thunk 永远不会超过一个。

[*] 冈崎，C. (1998)。纯函数式数据结构。剑桥：剑桥大学出版社。doi:10.1017/CBO9780511530104 ，或在线阅读其论文的相关部分。