スタックとキューの速度

RubyではスタックもキューもだいたいArrayを使って実装する。Arrayの一番後ろに追加、取り出しをするのはpush/popメソッドで、一番前にするのはunshift/shiftである。これらをどういう組み合わせで使うかでスタックとキューのどっちかになるわけだが、組み合わせは4通りあって、つまりスタックもキューも2通りずつの実装方法が存在することになる。

require 'benchmark'

puts Benchmark.measure {
  ary = []
  1000.times do |i|
    ary.push i
  end
  1000000.times do |i|
    ary.push i
    ary.pop
  end
}
puts Benchmark.measure {
  ary = []
  1000.times do |i|
    ary.unshift i
  end
  1000000.times do |i|
    ary.unshift i
    ary.shift
  end
}
puts Benchmark.measure {
  ary = []
  1000.times do |i|
    ary.push i
  end
  1000000.times do |i|
    ary.push i
    ary.shift
  end
}
puts Benchmark.measure {
  ary = []
  1000.times do |i|
    ary.unshift i
  end
  1000000.times do |i|
    ary.unshift i
    ary.pop
  end
}
=>0.203000   0.000000   0.203000 (  0.203122)
  5.328000   0.000000   5.328000 (  5.390556)
  3.485000   0.047000   3.532000 (  3.578079)
  0.593000   0.000000   0.593000 (  0.593743)

これはRuby1.9.3で動かした結果だが、スタックはpush/popが、キューはunshift/popが速いという結論になった。標準ライブラリのthread.rbではpush/shift型のキューが実装されているのでこれをunshift/pop型に書き換えると速くなることが予想できる。
ただ、Ruby2.0.0ではこのコードの結果が以下のようになる。

  0.218000   0.000000   0.218000 (  0.218747)
  0.188000   0.000000   0.188000 (  0.187498)
  0.187000   0.000000   0.187000 (  0.187497)
  0.204000   0.000000   0.204000 (  0.203123)

結局のところ、Ruby内部の実装により性能の優劣は変わるから、こういうチューニングをしたければ常に「いま使ってる実装では」という前置きが必要ということだ。