Array#delete_if が思ったよりも遅かった

Ruby の Array は可変長配列だと聞いていたので、先頭への要素の追加削除は既存の要素の再配置が必要になるから遅かろうと思っていた。ところが、実測してみると unshift/shift は push/pop と同等の速度だった。

ふむ。Array は可変長配列(C++ でいう vector)というよりは、むしろdeque のように双方に伸びる作りになっているのかもしれない。では Array はどんな操作でも速いのかと言ったらそうではなく、調べてみると delete_if が遅かった*1。

以下の表は 250,000 個の Fixnum からなる配列について delete_if を使って全て/半分/0個を削除する操作の実行時間を計ったもの。

                  user     system      total        real
delete all   10.040000   0.680000  10.720000 ( 10.738826)
delete half   4.920000   0.360000   5.280000 (  5.285048)
delete none   0.010000   0.000000   0.010000 (  0.011248)

およそ削除した個数に比例する時間がかかっている。要素数を n 倍すると n^2 倍以上の時間がかかるようになるので、O(n^2) の計算量なのではないか。

delete_if の非破壊版は reject だが、こちらは残す要素を新しい配列に追加してゆくため、さっきとは逆に削除する量が増えるほど高速になる。いずれにせよ何も削除しない場合以外は桁違いに速い。

                  user     system      total        real
reject all    0.010000   0.000000   0.010000 (  0.010794)
reject half   0.010000   0.000000   0.010000 (  0.012102)
reject none   0.010000   0.000000   0.010000 (  0.014866)

どんなメソッドでも破壊版のほうが非破壊版よりも高速なのだろうと思っていたので、この結果は驚きだった。delete_if はよく使っていたのだが、データがそれなりの量になると簡単にボトルネックになりそうだ。

ところで ary.delete_if { ... } は ary.replace(ary.reject { ... }) でその効果を再現できる。この方法で半数の削除を行う場合も計測してみた。

                  user     system      total        real
reject-replace  0.010000   0.000000   0.010000 (  0.012122)

うむ、こうなるとメモリが何よりも貴重な場合を除いて、delete_if を reject-replace で実装しなおしたほうがよい気さえしてくる。

ベンチマークに使ったスクリプトは以下の通り。

require 'benchmark'

n = 250_000
ints = [*1..n]

Benchmark.bm(11) do |bm|
  ar = ints.dup
  bm.report('delete half') do
    ar.delete_if(&:odd?)
  end

  ar = ints.dup
  bm.report('delete none') do
    ar.delete_if { false }
  end

  ar = ints.dup
  bm.report('reject all') do
    ar.reject { true }
  end

  ar = ints.dup
  bm.report('reject half') do
    ar.reject(&:odd?)
  end

  ar = ints.dup
  bm.report('reject none') do
    ar.reject { false }
  end

  ar = ints.dup
  bm.report('reject-replace') do
    ar.replace ar.reject(&:odd?)
  end
end

*1:公平を期せば「遅くすることが可能だった」ということだが。