無駄と文化

実用的ブログ

Array.prototype.includes と Set.prototype.has の速さ比べ

JavaScript プログラミング

配列がとある要素を含むかどうか調べるには Array.prototype.includes を使います。

const arr = [1, 2, 4, 8, 16];

arr.includes(4); // => true
arr.includes(7); // => false

ところで、JavaScript には Set というデータ型があり、同じように Set.prototype.has を使って要素を含んでいるか検索できます。

const set = new Set([1, 2, 4, 8, 16]);

set.has(4); // => true
set.has(7); // => false

mdn を見ると要素数が同じなら Array.prototype.includes より Set.prototype.has のほうが速いと 書いてあります 。

has メソッドは、値が Set 内にあるかどうかをチェックします。
これは、以前に Set に追加された要素のほとんどを確認するよりも平均すると高速なアプローチを使用します。
特に、 Array オブジェクトの length が Set オブジェクトの size と等しい場合、平均して Array.prototype.includes メソッドより速くなります。

本当でしょうか？実際にベンチマーク計測してみました。

 

3行まとめ

  • Array.prototype.includes より Set.prototype.has のほうが速い
  • ただし Set を初期化するのに時間がかかる
  • Array → Set の変換は遅い, Set → Array の変換は速い

 

Deno.bench で計測してみる

計測には Deno.bench を使います。
まず計測したい処理をコードに起こします。

import { assert } from "jsr:@std/assert";
import { crypto } from "jsr:@std/crypto/crypto";

// 1,000,000 要素の配列を作る
// 要素は何でもいいので uuid を詰めておく
const arr = Array.from({ length: 1_000_000 }, () => crypto.randomUUID());

// 検索対象を用意する
const found = arr[Math.floor(Math.random() * arr.length)]; // これは見つかる
const notfound = crypto.randomUUID(); // これは見つからない

// ここからが計測
Deno.bench({
  name: 'Array.prototype.includes',
  fn() {
    assert(arr.includes(found));
    assert(!arr.includes(notfound));
  },
});

そしてコマンド deno bench example.js でベンチマークを実行します。

$ deno bench example.js 
    CPU | Apple M2 Pro
Runtime | Deno 2.1.1 (aarch64-apple-darwin)

file:///Users/todays_mitsui/works/temp/example.js

benchmark                  time/iter (avg)        iter/s      (min … max)           p75      p99     p995
-------------------------- ----------------------------- --------------------- --------------------------
Array.prototype.includes            3.9 ms         258.6 (  3.7 ms …   4.3 ms)   3.9 ms   4.3 ms   4.3 ms

するとこのように結果が表示されます。

 

では具体的に比較してみましょう。

 

Array.prototype.includes vs in 演算子 vs Set.prototype.has

Array.prototype.includes と in 演算子 と Set.prototype.has の実行にかかる時間を比べます。
計測に使ったコードは ここ にあります。
要素数1,000,000件の Array と Object と Set を作って比較しています。

$ deno bench array_vs_object_vs_set.js 
    CPU | Apple M2 Pro
Runtime | Deno 2.1.1 (aarch64-apple-darwin)

file:///Users/todays_mitsui/works/temp/array_vs_object_vs_set.js

benchmark                  time/iter (avg)        iter/s      (min … max)           p75      p99     p995
-------------------------- ----------------------------- --------------------- --------------------------
Array.prototype.includes            3.1 ms         317.5 (  2.9 ms …   3.7 ms)   3.4 ms   3.6 ms   3.7 ms
in operator                        15.9 ns    62,780,000 ( 15.7 ns …  34.0 ns)  15.8 ns  18.5 ns  19.2 ns
Set.prototype.has                  13.1 ns    76,210,000 ( 13.0 ns …  15.8 ns)  13.1 ns  14.1 ns  14.6 ns

単位を揃えてみると、

time/iter (avg) iter/s
Array.prototype.includes 3.1 ms 317.5
in operator 0.0000159 ms 62,780,000.0
Set.prototype.has 0.0000131 ms 76,210,000.0

というわけで圧倒的に Set.prototype.has が速いようです。
Object から in 演算子で探すのもかなり速いですね。

 

Object と Set の初期化を加味した計測

先ほどの計測では Array, Object, Set を作る時間は計測せず、検索にかかる時間のみを対象にしていました。

では任意の Array が与えられたとき、検索のために Object や Set を初期化するところからやらないといけないようなシチュエーションではどうでしょうか。
そのシチュエーションを想定するなら Object や Set の初期化を計測に含めるべきですね。

その場合のコードが これ です。
実行してみます。

$ deno bench array_vs_object_vs_set_2.js 
    CPU | Apple M2 Pro
Runtime | Deno 2.1.1 (aarch64-apple-darwin)

file:///Users/todays_mitsui/works/temp/array_vs_object_vs_set_2.js

benchmark                  time/iter (avg)        iter/s      (min … max)           p75      p99     p995
-------------------------- ----------------------------- --------------------- --------------------------
Array.prototype.includes            4.0 ms         247.4 (  4.0 ms …   4.2 ms)   4.0 ms   4.2 ms   4.2 ms
in operator                       109.0 ms           9.2 ( 96.1 ms … 153.1 ms) 110.4 ms 153.1 ms 153.1 ms
Set.prototype.has                  84.8 ms          11.8 ( 72.4 ms … 146.7 ms)  76.8 ms 146.7 ms 146.7 ms

はい、初期化の時間を加味すると in 演算子も Set.prototype.has も遅いという結果になりました。

先ほどの結果と合わせてまとめると、

検索 初期化 + 検索
Array.prototype.includes 3.1 ms -
in operator 0.0000159 ms 109.0 ms
Set.prototype.has 0.0000131 ms 84.8 ms

このように。

数回だけ検索するだけであれば、Object や Set を作らず愚直に Array.prototype.includes を使ったほうがトータルで速くなりそうです。
数十回以上の検索を繰り返すのであれば初期化のコストを払ってでも Object や Set を作ったほうが有利になります。

 

Object と Set の初期化のコストを測ってみる

せっかくなので Array から Object や Set を作るのにかかる時間を測ってみます。
要素数が10件~1,000,000件の場合で見てみましょう。

計測に使ったコードは これ です。

$ deno bench array_to.js
    CPU | Apple M2 Pro
Runtime | Deno 2.1.1 (aarch64-apple-darwin)

file:///Users/todays_mitsui/works/temp/array_to.js

benchmark                             time/iter (avg)        iter/s      (min … max)           p75      p99     p995
------------------------------------- ----------------------------- --------------------- --------------------------
Array -> Set    > length:        10          159.9 ns     6,256,000 (150.3 ns … 195.0 ns) 163.7 ns 190.9 ns 194.4 ns
Array -> Set    > length:       100            2.2 µs       453,800 (  2.1 µs …   3.1 µs)   2.2 µs   3.1 µs   3.1 µs
Array -> Set    > length:     1,000           26.0 µs        38,510 ( 24.5 µs … 160.3 µs)  25.6 µs  33.4 µs  38.0 µs
Array -> Set    > length:    10,000          369.5 µs         2,706 (339.4 µs … 916.9 µs) 363.2 µs 722.2 µs 789.4 µs
Array -> Set    > length:   100,000            3.8 ms         262.1 (  3.6 ms …   4.5 ms)   4.1 ms   4.4 ms   4.5 ms
Array -> Set    > length: 1,000,000           94.0 ms          10.6 ( 78.9 ms … 118.7 ms)  97.2 ms 118.7 ms 118.7 ms
Array -> Object > length:        10          178.1 ns     5,615,000 (163.7 ns … 586.9 ns) 176.4 ns 321.6 ns 341.2 ns
Array -> Object > length:       100            1.9 µs       521,300 (  1.9 µs …   2.1 µs)   1.9 µs   2.1 µs   2.1 µs
Array -> Object > length:     1,000           21.6 µs        46,290 ( 18.4 µs … 150.1 µs)  22.7 µs  30.5 µs  91.3 µs
Array -> Object > length:    10,000          335.2 µs         2,983 (287.7 µs … 976.0 µs) 320.2 µs 730.0 µs 797.1 µs
Array -> Object > length:   100,000            6.4 ms         155.5 (  5.7 ms …   7.3 ms)   6.7 ms   7.3 ms   7.3 ms
Array -> Object > length: 1,000,000          107.9 ms           9.3 ( 96.2 ms … 171.6 ms) 102.2 ms 171.6 ms 171.6 ms
要素数 Array -> Object Array -> Set
10 0.0001781 ms 0.0001599 ms
100 0.0019 ms 0.0022 ms
1,000 0.0216 ms 0.0260 ms
10,000 0.3352 ms 0.3695 ms
100,000 6.4 ms 3.8 ms
1,000,000 107.9 ms 94.0 ms

Object と Set で大きな差があるわけではなく、要素が増えることによる影響が大きいように見えます。

 

Object や Set から Array を得るときのコスト

逆に Object や Set を持っている状態から Array がほしいときにはどれくらいのコストがかかるのでしょうか。
要素数1,000,000件の Object と Set に対して、Object.key(obj), Array.from(set.keys()) を比べてみます。

計測に使ったコードは これ です。

$ deno bench array_from.js 
    CPU | Apple M2 Pro
Runtime | Deno 2.1.1 (aarch64-apple-darwin)

file:///Users/todays_mitsui/works/temp/array_from.js

benchmark            time/iter (avg)        iter/s      (min … max)           p75      p99     p995
-------------------- ----------------------------- --------------------- --------------------------
Object.keys                 131.1 ms           7.6 (122.1 ms … 160.5 ms) 135.8 ms 160.5 ms 160.5 ms
Set.prototype.keys            1.5 ms         657.1 (  1.4 ms …   2.2 ms)   1.5 ms   2.1 ms   2.2 ms
要素数 Object -> Array Set -> Array
1,000,000 131.1 ms 1.5 ms

意外にも Set から Array を作る方が Object から作るのに比べて80倍ほど速いという結果になりました。

 

まとめ

Set から要素を検索するのは確かに速い、ただし Set を作るのにかなりの時間がかかる。
少し残念な結果でした。

 

 

私からは以上です。