Journal InTime

_ real-time deque

Purely Functional Data Structuresのreal-time dequeをRubyで実装してみた。 dequeは両端から要素を追加したり削除できるキューで、real-time dequeは両端への追加・削除が最悪でもO(1)というもので、以下のような使い方ができる。

>> deque = Immutable::Deque.empty.push(1).push(2).push(3)
=> #<Immutable::Deque:0x20f21b18 @front=Stream[?, ...], @front_len=1, @front_schedule=Stream[...], @rear=Stream[?, ...], @rear_len=2, @rear_schedule=Stream[...], @c=3>
>> deque.to_a
=> [1, 2, 3]
>> deque.first
=> 1
>> deque.shift.to_a
=> [2, 3]
>> deque.last
=> 3
>> deque.pop.to_a
=> [1, 2]

短命データなら例えば双方向リストを使って簡単に実装できると思うが、永続データだと後でリンクを付け変えることができないので結構複雑になる。このreal-time dequeでは、2本のリストを使って前半と後半に要素を分けて管理し、一回の操作がO(1)に収まるように一方のリストから他方に逐次的に要素を移している。

当初、queueの実装をFigure 5.3どおりに以下のように実装していたが、@c == 2*1の時に(1..5).inject(Immutable::Deque.empty, :&cons).to_aのようなコードでエラーになってしまった。

def queue(f, f_len, f_schedule, r, r_len, r_schedule)
  # ...
  elsif r_len > @c * f_len + 1
    i = (f_len + r_len) / 2
    j = (f_len + r_len) - i
    f2 = rotate_drop(f, j, r)
    r2 = r.take(j)
    self.class.new(f2, i, f2, r2, j, r2)
  else
    self.class.new(f, f_len, f_schedule, r, r_len, r_schedule)
  end
end

どうも

i = (f_len + r_len) / 2
j = (f_len + r_len) - i

の部分を

j = (f_len + r_len) / 2
i = (f_len + r_len) - j

のようにiとjを入れ替えないと上手く行かないようだ。 この部分はリア側の要素をフロント側に移す処理をしていて、elsifの前にはフロント側の要素をリア側に移すコードがあるのだが、それと対称的なコードにするには上記のようにiとjを入れ替えないといけない気がする。

また、Figure 5.3のコードはrotateDropの引数の順番も間違っているような気がするのだが、MLのコードなのでよくわからない。