photo credit: hehaden D is for dry via photopin (license)
ObjectとMapの速度を比較をしてみたんですが、予想外の結果を得ましたのでご報告します。
JavaScript で Key-Valueマップ（=ディクショナリ）を操作する場合、今まで何の疑いもなく object でやっていました。 しかし、ES6 で Mapクラスというのが追加されていて、Key-Valueマップとしては、こちらを使うのがオススメだそうなんです。 MDNのリファレンスでは、「（MapとObjectを比較すると）いくつかの場面で Map の方が勝るような重要な違いがあります」と書かれています。 ほぼ同じことがObjectで実現できるのに、なにが違っているのだろう？ そして、パフォーマンス的にはどっちが有利なんだろう？といった疑問が出てきたので、検証用のプログラムを書いて確認してみました。
※ 以降で紹介している検証は Node.js v14.15.1 (lts/fermium) で行いました。自宅の貧弱PCでの検証です。別の環境だと違う結果になるかも知れませんのでご留意を。
［ゲーム＆モダンJavaScript文法で2倍楽しい］グラフィックスプログラミング入門——リアルタイムに動く画面を描く。プログラマー直伝の基本 WEB+DB PRESS plus
杉本 雅広(著)
新品 ￥2,905 
18個の評価
Amazon.co.jpで詳細を見る
MapとObjectの比較検証
ObjectとMapのインスタンスに対して、以下の内容の操作を行い、その処理速度を比較します。
- Key-Valueの挿入(Insert) - 新たなキーを複数回挿入する。
- Valueの上書き(Update) - 既存のキーの値を更新する。
- Valueの取得(Get) - 特定のキーを指定して値を取り出す。
- Keyの列挙(Keys) - 内包するキーをすべて列挙する。
- Valueの列挙(Values) - 内包する値をすべて列挙する。
- Key-Valueの削除(Delete) - 既存のキーを削除する
また、キーの型によって優劣に差が出るかも知れないと思い、とりあえず「文字列をキーにした場合」と、「数値をキーにした場合」の両方で検証しました。
検証用のプログラム
ちょっと長いですが、上記の内容をゴリゴリっと書いた結果がコレ。 もう少し短くできると思ったのですが、途中で諦めた。
"use strict"; const ListIt = require("list-it"); class TestRun { elapse; constructor(x, keys, handler) { const t0 = Date.now(); handler(x, keys); const t1 = Date.now(); this.elapse = t1 - t0; } } const TEST_AMOUNT = 2000000; const STRING_KEYS = Array(TEST_AMOUNT).fill(null).map((_, i) => `STR-${i}`); const NUMBER_KEYS = Array(TEST_AMOUNT).fill(null).map((_, i) => i); const tests = [ { name: "insert", operation: { obj: (obj, keys) => keys.forEach((key, i) => obj[key] = i), map: (map, keys) => keys.forEach((key, i) => map.set(key, i)), }, }, { name: "update", operation: { obj: (obj, keys) => keys.forEach((key, i) => obj[key] = i * 2), map: (map, keys) => keys.forEach((key, i) => map.set(key, i * 2)), }, }, { name: "get", operation: { obj: (obj, keys) => keys.forEach((key, i) => obj[key] = obj[key] * 2), map: (map, keys) => keys.forEach((key, i) => map.set(key, map.get(key))), }, }, { name: "keys", operation: { obj: (obj, keys) => Object.keys(obj), map: (map, keys) => map.keys(), }, }, { name: "values", operation: { obj: (obj, keys) => Object.values(obj), map: (map, keys) => map.values(), }, }, { name: "delete", operation: { obj: (obj, keys) => keys.forEach((key, i) => delete obj[key]), map: (map, keys) => keys.forEach((key, i) => map.delete(key)), }, }, ]; const targetNames = tests.map(test => test.name); const transpose = (arr) => { const rows = Math.max(...arr.map(arr1 => arr1.length)); const tArr = Array(rows).fill(null).map(()=>(Array(arr.length).fill(0))); arr.forEach((arr1, row) => { arr1.forEach((data, col) => { tArr[col][row] = data; }); }); return tArr; }; const obj1 = {}; const map1 = new Map(); const testObjStr = tests.map(test => (new TestRun(obj1, STRING_KEYS, test.operation.obj))); const testMapStr = tests.map(test => (new TestRun(map1, STRING_KEYS, test.operation.map))); const resultS = transpose([ ["operation", ...targetNames], ["object", ...testObjStr.map(result => result.elapse)], ["Map", ...testMapStr.map(result => result.elapse)], ]); const listitS = new ListIt({headerBold: true, headerColor: "green", headerUnderline: true}); console.log("Key=string"); console.log(listitS.setHeaderRow(resultS.shift()).d(resultS).toString()); console.log(""); const obj2 = {}; const map2 = new Map(); const testObjNum = tests.map(test => (new TestRun(obj2, NUMBER_KEYS, test.operation.obj))); const testMapNum = tests.map(test => (new TestRun(map2, NUMBER_KEYS, test.operation.map))); const resultN = transpose([ ["operation", ...targetNames], ["object", ...testObjNum.map(result => result.elapse)], ["Map", ...testMapNum.map(result => result.elapse)], ]); const listitN = new ListIt({headerBold: true, headerColor: "green", headerUnderline: true}); console.log("Key=number"); console.log(listitN.setHeaderRow(resultN.shift()).d(resultN).toString()); console.log("");
結果発表
上記プログラムを実行すると「キーを文字列にした場合」と「キーを整数にした場合」の2つの表がコンソールに出力されます。 表には、それぞれの操作を行ったときのミリ秒単位の時間を表示しています。 さて、それぞれについて見ていきましょう。
※ キーや値の列挙操作以外は、二千万回の操作をしている時間ですが、ループのオーバーヘッドがあるので純粋な処理時間ではありません。 なので以下の内容で「差がある」と書いていても、それほど大きな違いではありません。
キーを文字列にした場合
コンソール出力：
Key=string operation object Map --------- ------ ---- insert 3888 1558 update 388 846 get 398 1086 keys 2452 0 values 4381 0 delete 936 1127
パッと見感想：不思議な結果ですが、何度やり直してもこれぐらいの数値になりますので、そういうことなんでしょう。
個別の操作について：
- 挿入 - Mapの勝ち。Objectへのキーの挿入はMapの倍以上の時間がかかる。
- 更新 - Objectの勝ち。Mapより3倍近く速い。
- 取得 - Objectの勝ち。更新操作の時間も含まれているので、1行上の時間を減じると object: 10ms, Map: 240ms となり、実質的に24倍！！！
- Key列挙 - Mapの勝ち。Objectめちゃ遅い。Mapはおそらくイテレータを包有しているのでしょう。
- Value列挙 - Mapの勝ち。Objectめちゃめちゃ遅い。Mapはおそらく（同上）
- 削除 - Objectの勝ち。接戦だけど優位な差がある。
キーを整数にした場合
コンソール出力：
Key=number operation object Map --------- ------ ---- insert 244 1161 update 83 501 get 105 515 keys 530 0 values 54 0 delete 426 694
パッと見感想：一部を除いてObjectが爆速。内部的に配列として実装されているのではないか？
個別の操作について：
- 挿入 - Objectの勝ち。Mapの4倍以上の速度。
- 更新 - Objectの勝ち。Mapの6倍以上の速度。
- 取得 - Mapの勝ち。実質的に object: 22ms, Map: 14ms となりますので、ほとんど差はありませんがMapの逆転勝ち。
- Key列挙 - Mapの勝ち。Objectがやはり遅いが、文字列をキーとした場合より4倍以上は頑張っている。
- Value列挙 - Mapの勝ち。Objectが遅いけど、文字列をキーとした場合よりは極端に速い。
- 削除 - Objectの勝ち。接戦だけど優位な差がある。
結果まとめ
ObjectとMapのどちらを使うかと迷ったら、処理内容に応じて、なんとなく以下の順番で検討すれば良いのかなと思いました。
- キーや値を列挙する操作が多い場合 → Mapが優位。
- キーが整数値 → Objectが優位。
- あらかじめキーと値を設定しておき更新や参照をする場合には、Objectが優位。
- 削除の操作は大差なし。
MDNの「キー付きコレクション」というページには以下の文面があります。
Map と Object のどちらを使用すべきかを決めるには下記の 3 つのヒントが役立つでしょう :
- 実行時までキーが不明なとき、またはすべてのキーが同じ型、すべての値が同じ型のときは Object よりも Map を使用しましょう。
- プリミティブ値をキーとして保存する必要がある場合に Map を使用しましょう。Object はキーが数値、真偽値、もしくはいずれのプリミティブ値であるかどうかに関わらず、それぞれのキーを文字列として扱います。
- 個々の要素を操作するロジックがある場合は、Object を使用しましょう。
「実行時までキーが不明なときはMap」というのはObjectへのInsertが遅いためですね。これはわかります。 しかし、「プリミティブ値をキーとして保存するならMap」というのが検証結果とは多少ニュアンスが違っていますが、キーを整数にしたときのObjectの速さは魅力ですね。 まんべんなくいろんな操作をしているのであれば、勝敗表的には引き分けですから、MDNの推奨通りMapを使えばよいのではないでしょうか。
ただし、これは、あくまでも 現在の Node.js v14.15.3 で、自宅PCで実行した結果に基づくものです。 別のプラットフォーム（ブラウザとか）だと別の結果になるかも知れませんからご注意ください。
