はじめに
Ruby 2.6には配列の差集合を返す Array#difference メソッドが追加されました。
もともとあった Array#- 演算子と同じ振る舞いをしますが、複数の引数を取れるというメリットがあります。
参考： サンプルコードでわかる！Ruby 2.6の主な新機能と変更点 の 和集合と差集合を返すunion/differenceメソッド
Array#difference と Array#- の実装は同じなのか、パフォーマンス的に違いはないのか、など気になったので調べてみました。
実装の比較
Githubにあるruby 2.6の、C言語で書かれたArrayクラスの実装 array.c をみてみます。
rb_define_xxx
rb_define_method(rb_cArray, "difference", rb_ary_difference_multi, -1);
rb_define_method(rb_cArray, "-", rb_ary_diff, 1);
どちらも rb_define_alias ではなく rb_define_method と書かれているので、 Array#difference と Array#- は別の実装のようです。ただ、メソッドの実装の中で一方がもう一方を呼び出している、という可能性が残っていますね。
メソッドの実装
rb_ary_difference_multi (Array#differenceの実装)
static VALUE
rb_ary_difference_multi(int argc, VALUE *argv, VALUE ary)
{
VALUE ary_diff;
long i, length;
volatile VALUE t0;
bool *is_hash = ALLOCV_N(bool, t0, argc);
ary_diff = rb_ary_new();
length = RARRAY_LEN(ary);
for (i = 0; i < argc; i++) {
argv[i] = to_ary(argv[i]);
is_hash[i] = (length > SMALL_ARRAY_LEN && RARRAY_LEN(argv[i]) > SMALL_ARRAY_LEN);
if (is_hash[i]) argv[i] = ary_make_hash(argv[i]);
}
for (i = 0; i < RARRAY_LEN(ary); i++) {
int j;
VALUE elt = rb_ary_elt(ary, i);
for (j = 0; j < argc; j++){
if (is_hash[j]) {
if (rb_hash_stlike_lookup(argv[j], RARRAY_AREF(ary, i), NULL))
break;
}
else {
if (rb_ary_includes_by_eql(argv[j], elt)) break;
}
}
if (j == argc) rb_ary_push(ary_diff, elt);
}
ALLOCV_END(t0);
return ary_diff;
}
[rb_ary_diff (Array#-の実装)]
(https://github.com/ruby/ruby/blob/ruby_2_6/array.c#L4467)
static VALUE
rb_ary_diff(VALUE ary1, VALUE ary2)
{
VALUE ary3;
VALUE hash;
long i;
ary2 = to_ary(ary2);
ary3 = rb_ary_new();
if (RARRAY_LEN(ary1) <= SMALL_ARRAY_LEN || RARRAY_LEN(ary2) <= SMALL_ARRAY_LEN) {
for (i=0; i<RARRAY_LEN(ary1); i++) {
VALUE elt = rb_ary_elt(ary1, i);
if (rb_ary_includes_by_eql(ary2, elt)) continue;
rb_ary_push(ary3, elt);
}
return ary3;
}
hash = ary_make_hash(ary2);
for (i=0; i<RARRAY_LEN(ary1); i++) {
if (rb_hash_stlike_lookup(hash, RARRAY_AREF(ary1, i), NULL)) continue;
rb_ary_push(ary3, rb_ary_elt(ary1, i));
}
ary_recycle_hash(hash);
return ary3;
}
２つのメソッドの実装を見ると、似てはいるけど、それぞれ別の実装ですね。もしかして、複数の引数を取れる rb_ary_difference_multi 側に寄せてもいいんじゃないのかな、と思いました。そうしていない理由を知っている方がいたら教えてください。
おまけ： Setクラス
Arrayとは違ってSetはC言語ではなくrubyで実装されていますね。
def -(enum)
dup.subtract(enum)
end
alias difference -
そしてArrayとは異なって、 Set#difference は Set#- のaliasです。
なぜArrayとSetはこんなに違うのか、私にはわかりませんでした。こちらも知っている方がいたら教えてください。
パフォーマンスの比較
パフォーマンスの比較もしてみましょう。
こんなスクリプトを書いてみました。
require 'benchmark'
M = 1000
Benchmark.bm 30 do |r|
[1, 10, 100, 1000].each do |n|
a = (0...(n*100)).to_a
b0 = ((0*n)...(1*n)).to_a
b1 = ((1*n)...(2*n)).to_a
b2 = ((2*n)...(3*n)).to_a
b3 = ((3*n)...(4*n)).to_a
b4 = ((4*n)...(5*n)).to_a
b5 = ((5*n)...(6*n)).to_a
b6 = ((6*n)...(7*n)).to_a
b7 = ((7*n)...(8*n)).to_a
b8 = ((8*n)...(9*n)).to_a
b9 = ((9*n)...(10*n)).to_a
r.report("#{n}, Array#-, 1,") { M.times { a - b0 } }
r.report("#{n}, Array#-, 2,") { M.times { a - b0 - b1 } }
r.report("#{n}, Array#-, 3,") { M.times { a - b0 - b1 - b2 } }
r.report("#{n}, Array#-, 4,") { M.times { a - b0 - b1 - b2 - b3 } }
r.report("#{n}, Array#-, 5,") { M.times { a - b0 - b1 - b2 - b3 - b4 } }
r.report("#{n}, Array#-, 6,") { M.times { a - b0 - b1 - b2 - b3 - b4 - b5 } }
r.report("#{n}, Array#-, 7,") { M.times { a - b0 - b1 - b2 - b3 - b4 - b5 - b6 } }
r.report("#{n}, Array#-, 8,") { M.times { a - b0 - b1 - b2 - b3 - b4 - b5 - b6 - b7 } }
r.report("#{n}, Array#-, 9,") { M.times { a - b0 - b1 - b2 - b3 - b4 - b5 - b6 - b7 - b8 } }
r.report("#{n}, Array#-, 10,") { M.times { a - b0 - b1 - b2 - b3 - b4 - b5 - b6 - b7 - b8 - b9 } }
r.report("#{n}, Array#difference, 1,") { M.times { a.difference(b0) } }
r.report("#{n}, Array#difference, 2,") { M.times { a.difference(b0, b1) } }
r.report("#{n}, Array#difference, 3,") { M.times { a.difference(b0, b1, b2) } }
r.report("#{n}, Array#difference, 4,") { M.times { a.difference(b0, b1, b2, b3) } }
r.report("#{n}, Array#difference, 5,") { M.times { a.difference(b0, b1, b2, b3, b4) } }
r.report("#{n}, Array#difference, 6,") { M.times { a.difference(b0, b1, b2, b3, b4, b5) } }
r.report("#{n}, Array#difference, 7,") { M.times { a.difference(b0, b1, b2, b3, b4, b5, b6) } }
r.report("#{n}, Array#difference, 8,") { M.times { a.difference(b0, b1, b2, b3, b4, b5, b6, b7) } }
r.report("#{n}, Array#difference, 9,") { M.times { a.difference(b0, b1, b2, b3, b4, b5, b6, b7, b8) } }
r.report("#{n}, Array#difference, 10,") { M.times { a.difference(b0, b1, b2, b3, b4, b5, b6, b7, b8, b9) } }
end
end
1,10,100,1000の100倍の大きさの配列aに対して、aの1/100の大きさの別々の配列を1回〜10回引いています。
パフォーマンスに影響を与えないように、出来るだけベタに書きました。（が、後の結果を見るとここはあまり神経質にならなくて良さそうです）
このスクリプトは、上に書いたようなごく限られたパターンのパフォーマンスを計測していることに注意してください。
上記のスクリプトの実行結果を少し加工してcsvファイルにして、Tableau Publicに入れてグラフにしてみました。
Array#difference の方が Array#- よりも少し早いようですね。n=1000の場合の傾きを比べると、Array#difference は Array#- の80%程度のようです。ただしそれは配列を引く回数が多い場合で、１つしか引かない場合はほぼ同じ実行時間ですね。
「複数の引数を取れる Array#difference はメソッドコールの回数を節約できるので Array#- よりも高速」と、どこかで聞いた気がしたのですが、配列が大きくなるにつれて実行時間の差が開いていくので、厳密にはメソッドコールの回数が差を生んでいるというわけではなさそうです。メソッドコールというより、一回ごとに配列オブジェクトを作るから Array#- が不利という感じでしょうか。呼び出しごとに配列オブジェクトを作ることもメソッドコールのうちと思えば、メソッドコールの回数が影響していると言っても間違いではなさそうです。
まあ、とにかく、この場合には Array#difference の方が Array#- よりも速いことがわかりました。ただし実行時間が80%になる程度なので、通常の使い方の場合は速いか遅いかは気にせずに、読みやすい方を採用すれば良さそうですね。
おまけ: 逆転する場合もある
普通の場合には Array#difference の方が速そうですが、特別な場合には Array#- が速くなる場合もあります。
require 'benchmark'
a = (0...100000).to_a
Benchmark.bm do |r|
r.report("-"){a-a-a}
r.report("d"){a.difference(a,a)}
end
# =>
# user system total real
# - 0.009689 0.000928 0.010617 ( 0.010765)
# d 0.016169 0.001048 0.017217 ( 0.018013)
配列aから配列aを引いて、さらに配列aを引くような場合、1回目の引き算で空っぽになってしまうので、2回目の実行時間が極端に短くなって、 Array#- が Array#difference よりも2倍近く速くなることがあります。
まとめ
-
Array#differenceとArray#-は別実装 -
Array#differenceの方がArray#-よりもちょっと速い（限定された状況でのパフォーマンス計測で） - 速さの差は小さいので、通常は読みやすい方を使えばよい
- どうしてこういう実装なのかはわからないので、詳しい方教えてください