はじめに

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);

Array#-

    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で実装されていますね。

Set#-の実装

   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#- よりもちょっと速い（限定された状況でのパフォーマンス計測で）
速さの差は小さいので、通常は読みやすい方を使えばよい
どうしてこういう実装なのかはわからないので、詳しい方教えてください