スタックとキューの速度
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内部の実装により性能の優劣は変わるから、こういうチューニングをしたければ常に「いま使ってる実装では」という前置きが必要ということだ。