Life Goes On

まあまあだけど楽しんでる方です

Haskell で RealTimeQueue

@autotaker1984 さんの以下の記事について考えました。

永続リアルタイムキューのHaskell実装と計算量解析 - autotaker's blog

head / tail するときに、reverse さえ完了していれば問題ない、だから snoc で停止計算を進行させる必要はない、というのはなんとなく説得力があります。
けれども PFDS では、 rotate が始まるときに停止計算がすべて完了していること(負債を完済していること)にこだわっていました。
それは、停止計算が重なると再帰的な呼び出しで計算量が増えるからです。

たとえば空のキューに 1 から 15 まで snoc すると、frontList は以下のような状態で、go 関数の呼び出しが再帰的になります。

go [] (go [] (go [] (go [] [] [1]) [3, 2]) [7, 6, 5, 4]) [15, 14 .. 8]

ここから tail すると以下のように 4 ステップかかります。

go [] (go [] (go [] (go [] [] [1]) [3, 2]) [7, 6, 5, 4]) [15, 14 .. 8]
=> go [] (go [] (go [] (1 : []) [3, 2]) [7, 6, 5, 4]) [15, 14 .. 8]
=> go [] (go [] (1 : go [3] [] [2]) [7, 6, 5, 4]) [15, 14 .. 8]
=> go [] (1 : go [7] (go [3] [] [2]) [6, 5, 4]) [15, 14 .. 8]
=> 1 : go [15] (go [7] (go [3] [] [2]) [6, 5, 4]) [14, 13 .. 8]

さらに tail する場合も以下のように 3 ステップかかります。

go [15] (go [7] (go [3] [] [2]) [6, 5, 4]) [14, 13 .. 8]
=> go [15] (go [7] (2 : [3]) [6, 5, 4]) [14, 13 .. 8]
=> go [15] (2 : go [6, 7] [3] [5, 4]) [14, 13 .. 8]
=> 2 : go [14, 15] (go [6, 7] [3] [5, 4]) [13, 12 .. 8]

ざっくり言うと O(1) ではなく O(log(n)) かかってしまうように思います。