Ruby 2.6のArray#differenceはArray#-と同じ振る舞いだけど、なにか違いはあるのかと実装やパフォーマンスを調べた


# はじめに

Ruby 2.6には配列の差集合を返す `Array#difference` メソッドが追加されました。
もともとあった `Array#-` 演算子と同じ振る舞いをしますが、複数の引数を取れるというメリットがあります。

参考： [サンプルコードでわかる！Ruby 2.6の主な新機能と変更点](https://qiita.com/jnchito/items/ce11cb7fccdf4b66af24) の [和集合と差集合を返すunion/differenceメソッド](https://qiita.com/jnchito/items/ce11cb7fccdf4b66af24#%E5%92%8C%E9%9B%86%E5%90%88%E3%81%A8%E5%B7%AE%E9%9B%86%E5%90%88%E3%82%92%E8%BF%94%E3%81%99uniondifference%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89)

`Array#difference` と `Array#-` の実装は同じなのか、パフォーマンス的に違いはないのか、など気になったので調べてみました。

# 実装の比較

Githubにあるruby 2.6の、C言語で書かれたArrayクラスの実装 [array.c](https://github.com/ruby/ruby/blob/ruby_2_6/array.c) をみてみます。

## rb_define_xxx

[Array#difference](https://github.com/ruby/ruby/blob/ruby_2_6/array.c#L6804)

```c
    rb_define_method(rb_cArray, "difference", rb_ary_difference_multi, -1);
```

[Array#-](https://github.com/ruby/ruby/blob/ruby_2_6/array.c#L6862)

```c
    rb_define_method(rb_cArray, "-", rb_ary_diff, 1);
```

どちらも `rb_define_alias` ではなく `rb_define_method` と書かれているので、 `Array#difference` と `Array#-` は別の実装のようです。ただ、メソッドの実装の中で一方がもう一方を呼び出している、という可能性が残っていますね。

## メソッドの実装

[rb_ary_difference_multi (`Array#difference`の実装)](https://github.com/ruby/ruby/blob/ruby_2_6/array.c#L4515)

```c
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)

```c
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#-`の実装](https://github.com/ruby/ruby/blob/trunk/lib/set.rb#L465)

```rb
   def -(enum)
     dup.subtract(enum)
   end
   alias difference -
```

そしてArrayとは異なって、 `Set#difference` は `Set#-` のaliasです。
なぜArrayとSetはこんなに違うのか、私にはわかりませんでした。こちらも知っている方がいたら教えてください。

# パフォーマンスの比較

パフォーマンスの比較もしてみましょう。
こんなスクリプトを書いてみました。

https://gist.github.com/Akiyah/c55e0f218e342cbed8f8b23ffa74a0e6#file-benchmark_-_difference-rb

```rb
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ファイル](https://gist.github.com/Akiyah/c55e0f218e342cbed8f8b23ffa74a0e6#file-benchmark_-_difference_output-csv)にして、[Tableau Public](https://public.tableau.com/)に入れて[グラフ](https://public.tableau.com/profile/.7787#!/vizhome/Ruby2_6ArraydifferenceArray-/Ruby2_6ArraydifferenceArray-)にしてみました。

![スクリーンショット 2019-03-03 11.26.37.png](https://qiita-image-store.s3.amazonaws.com/0/62293/2ea0dab8-2e4a-dbe2-8492-ed36e6d79387.png)

`Array#difference` の方が `Array#-` よりも少し早いようですね。n=1000の場合の傾きを比べると、`Array#difference` は `Array#-` の80%程度のようです。ただしそれは配列を引く回数が多い場合で、１つしか引かない場合はほぼ同じ実行時間ですね。

「複数の引数を取れる `Array#difference` はメソッドコールの回数を節約できるので `Array#-` よりも高速」と、どこかで聞いた気がしたのですが、配列が大きくなるにつれて実行時間の差が開いていくので、厳密にはメソッドコールの回数が差を生んでいるというわけではなさそうです。メソッドコールというより、一回ごとに配列オブジェクトを作るから `Array#-` が不利という感じでしょうか。呼び出しごとに配列オブジェクトを作ることもメソッドコールのうちと思えば、メソッドコールの回数が影響していると言っても間違いではなさそうです。

まあ、とにかく、この場合には `Array#difference` の方が `Array#-` よりも速いことがわかりました。ただし実行時間が80%になる程度なので、通常の使い方の場合は速いか遅いかは気にせずに、読みやすい方を採用すれば良さそうですね。

## おまけ: 逆転する場合もある

普通の場合には `Array#difference` の方が速そうですが、特別な場合には `Array#-` が速くなる場合もあります。

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