2022-05-28 - JavaScript の Array difference を取得する時に `Array.prototype.includes()` を使っている説明例が多いけど、片方を Set にして `Set.prototype.has()` を使ったほうが無難だったりしないのかな

[kachick]

経緯 / History

JavaScript の Array difference (Ruby で言うところの [1, 2, 3] - [2] #=> [1, 3]) を取りたい時にググると大抵 Array.prototype.includes() を使っているような StackOverFlow とかが出てくる。 ぱっと見で一番 ⭐ 集めてた https://stackoverflow.com/a/4026828 とかもそう。 しかし実質ループの中でループ回す処理に見えてウッとなる。そういえば Ruby の この辺の処理は確か内部で hash 値? 使った lookup してたし、 Ruby の Set は Hash のラッパー。ということは JavaScript でもこの辺は Set 使うだけでマシになったりしないかな？と思ってちょっと試してみた。ここでは Node.js を使っているけれど、別に Node.js の実装を確認したりはしていない。 一々 npm でベンチマークツール入れてとか面倒なので REPL で雑に 処理が単調なので includes での探索でヒットするまでの回数が固定

const ints = [...Array(420000)].map((_, i) => i);
const evens = ints.filter((n) => n % 2 === 0);

console.time('bench: creating Set');
const evenSet = new Set(evens);
console.timeEnd('bench: creating Set');

console.time('bench: Array#includes');
const oddsWithArrayIncludes = ints.filter((n) => !evens.includes(n));
console.timeEnd('bench: Array#includes');

console.time('bench: Set#has');
const oddsWithSetHas = ints.filter((n) => !evenSet.has(n));
console.timeEnd('bench: Set#has');

const bothAreSame = JSON.stringify(oddsWithArrayIncludes) === JSON.stringify(oddsWithSetHas);
// Ensure true
bothAreSame

❯ node
Welcome to Node.js v16.15.0.
Type ".help" for more information.
> const ints = [...Array(420000)].map((_, i) => i);
undefined
> const evens = ints.filter((n) => n % 2 === 0);
undefined
>
> console.time('bench: creating Set');
undefined
> const evenSet = new Set(evens);
undefined
> console.timeEnd('bench: creating Set');
bench: creating Set: 21.271ms
undefined
>
> console.time('bench: Array#includes');
undefined
> const oddsWithArrayIncludes = ints.filter((n) => !evens.includes(n));

undefined
> console.timeEnd('bench: Array#includes');
bench: Array#includes: 48.317s
undefined
>
> console.time('bench: Set#has');
undefined
> const oddsWithSetHas = ints.filter((n) => !evenSet.has(n));
undefined
> console.timeEnd('bench: Set#has');
bench: Set#has: 51.217ms
undefined
>
> const bothAreSame = JSON.stringify(oddsWithArrayIncludes) === JSON.stringify(oddsWithSetHas);
undefined
> // Ensure true
undefined
> bothAreSame
true
> (48.713 * 1000) / 51.217
951.1099830134526
> (48.713 * 1000) / (51.217 + 21.271)
672.0146782915793

これぐらい大きな値になると流石に差が激しくて、700倍近い結果が出た。それなりに大きい Array でも Set に変換するコストは小さい感じなので、array1.filter((v) => array2.includes(v)) みたいなコードを書くときにはちょっと思い出すようにしたい

そもそも ECMA Script の proposal にも、Array というか Set に集合演算を用意しようという話は挙がってるみたい。 https://github.com/tc39/proposal-set-methods でも https://github.com/tc39/proposal-set-methods/blob/2e58731d1e88656f1abf1c0e5272ba320258cd30/spec/set-prototype-difference.html#L1-L17 見る限り引数に iterable 受け取る？ということは結局使い方気をつける必要ありそうな・・・？