こんにちは。Cacooチームの中原です。
今回はプログラムを書くときArrayだけでなくSet, Mapを意識して使うことで大きくパフォーマンスを改善できるかもしれないという話です。
ここではJavaScriptで説明していますが、多くのプログラミング言語がArray、Set、MapといったAPIを標準でもっています。ぜひJavaScript以外の言語でも試してみてください。
ではさっそく初めましょう。この12個の数字の中に 15 が含まれているか探してみましょう。どう書きますか？
6, 11, 2, 1, 13, 4, 15, 18, 14, 16, 12, 8
See the Pen PVzqNv by shoji (@shoji-nulab) on CodePen.
次に探す数字が複数になったらどうでしょう。今度は4つの数字 15, 2, 5, 9 のうちいくつ、12個の数の中に含まれているか探してみましょう。どう書きますか?
See the Pen XOKbge by shoji (@shoji-nulab) on CodePen
Found 2
単純に繰り返しただけですね。もちろん、ちゃんとうごきました！
さて、さっきは12個の数字の中から4個の数字を探しましたが、この数がものすご～～く大きくなった場合はどうなるでしょう?
10万この数字の中から2万個の数字を探してみましょう。
See the Pen JxKqBv by shoji (@shoji-nulab) on CodePen.
動きましたが、ちょっと時間がかかってますね。私の環境だと2.5秒ほどかかりました。
では、ちょっとだけコードを変更してみましょう。ArrayのindexOf()を使わずに、一度Setに数を渡してhas()を使うようにしただけです。
では、実行してみましょう。
See the Pen Rvooqe by shoji (@shoji-nulab) on CodePen.
お、一瞬で終わりましたね。私の環境だと25ミリ秒。なんと 1/100 の時間で処理が終わりました。正にケタ違い。２桁違いますね。
では、ArrayとSetに一体どんな違いがあるんでしょう。よく挙げられる特徴として次の様なものがあります。
Array
- 順番がある
- 同じを要素を複数格納できる
- 要素の挿入・削除・検索に時間がかかる
- 添字を使ったアクセスが高速
Set
- 順番がない
- 同じ要素を複数格納できない
- 要素の挿入・削除・検索が高速
今回の場合、ArrayでindexOf() を使うと、Arrayの先頭から要素が見つかるまで1つずつ調べていたのが、Setを使うと1回で要素があるかどうかがわかるので非常に早くなったんですね。
実際にはただの数字でなく、オブジェクトを検索する場合が多いかと思います。その場合はどう書くでしょうか? Arrayを使った場合はこんな感じにです。
See the Pen OdbWWP by shoji (@shoji-nulab) on CodePen.
今度は Set でなく Map を使います。
See the Pen XONpeE by shoji (@shoji-nulab) on CodePen.
これでさっきと同じように処理時間が短くなります。
実際の開発でも、開発中はデータ件数が少ない状態で動作確認をしていて問題にならなかったけど、使われ始めると遥かに多いデータ数を処理することになって、ものすごく時間がかかるということはよくあることです。ループの処理を書くときには「これって最大で何回くらいループするんだろう？」とちょっと考えてみてください。そうするとものすごく時間がかかったり、CPUやメモリなどのリソースを食い潰してしまう問題に前もって対処できるかもしれません。
もし今回始めてSet, Map を知ったのであれば、この魔法のように高速な仕組みを調べてみてください。”ハッシュテーブル”、”アルゴリズム データ構造”でインターネットや書籍を検索するとたくさん情報が見つかると思います。
それでは、楽しいアルゴリズムとデータ構造の世界へようこそ!
