UninitializedFastArray.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
# 2008-12-03 koyachi
# via http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html

class UninitializedFastArray
  def initialize
    @dense = []   # queue
    @sparse = []  # inverted_index ハッシュのキーにして
    @n = 0
  end

  def add(i)
    @dense[@n] = i
    @sparse[i] = @n
    @n += 1
  end

  # ハッシュキーにしてキャッシュの有無調べるのはよくやる
  def is(i)
    @sparse[i] < @n && @dense[@sparse[i]] == i
  end

  # clear操作内で配列長0にするだけ、実際の配列内容をクリアしなくても
  # is(i)で確認すれば前の値が残っていてもアクセスすることがない
  # -> ゼロクリアコスト削減
  #    ある程度の大きさの配列を一括で高速に初期化する必要がある場合
  def clear
    @n = 0
  end

  def iter
    @dense
  end
end