JavaScriptで配列から最大値を選択する処理の性能比較

JavaScriptで配列から最大値を選択する処理の、実装方法やアルゴリズムによる実行速度の違いをテストしてみました。

複数の数値の最大を得る関数としては「Math.max()」が組み込みで用意されています。 しかし、そのままでは事前に引数の数が決まっている場合にしか使えません。対象の数値の数が決まっていない場合には不便です。 なので、任意の長さの数値配列が与えられた場合に、その配列の中から最大値を得る処理を考えます。 JavaScriptに関し多少知識のある一般的なSEなら「Math.max.apply(null, array);」とするでしょう。 が、そこをあえていくつかのアルゴリズムで処理を書き比較してみます。

環境・条件は以下のとおりです。

環境

処理・データ条件

処理種類

※「こちら」のページで各ソースの確認と、あなたのブラウザを使って実際にテストを実行できます。


左から順に、Chrome43, IE11, Firefox38での結果です。



差が大きくつきすぎて驚きました。まずはブラウザ間に大きな差がありました。 おおむね「IE:Chrome:Firefox = 1:2:5」程度の性能差がありました。 以前、素数判定のアルゴリズムを比較した際にはほとんど差がありませんでした。 そちらは計算量が多いのでアルゴリズムが重要になるが、 こちらは単純なので個々の命令のコストが大きく反映されがちなのでしょう。

不思議だったのは、test02の組み込みの「Math.max()」を使ったロジックが、非常に遅かったことです。 さらに配列の要素数を30万にすると、この処理だけが「Uncaught RangeError: Maximum call stack size exceeded」 というエラーになりました。このことから、「Math.max()」は内部で再帰を使用しているのだろうと思われます。 単純なループに、これほどまでに速度差をつけられ、処理上限も低くなってしまうのでは、 「Math.max()」を使ったロジックは、少なくとも性能・仕様の面ではいいところ無しですね。 シンプルに書けるし処理内容が明確であるし、バグの心配もほぼないという点はメリットですが。

test03はtest02よりさらに劇的に遅い結果になりました。配列のソートをしただけなのですが…。 それだけソートのコストは高いということでしょう。他の処理でまかなえる場合はソートは避けるべきとの教訓を得ました。

test00とtest01の違いは、「ループの終了条件で、配列の長さを変数に格納しておく」か 「ループの終了条件で、配列の長さを毎回取得する」の違いです。 素数判定のパフォーマンステストでも比較し、その際には「有意な差はない」と結論付けました。 しかし、こちらは全体の処理コストが小さく、ほんの少しの差でもあれば 最終結果に差が大きく表れるかもしれないと思い、再度チャレンジしました。

結果としてChromeとFirefoxでは有意な差異は検出できませんでした。 しかしIEでは15%程度の処理速度の違いが生じました。やっぱり差はあるのですね…。 ただ、ループ内の処理内容としては「if (max < array[i]) max = array[i];」だけで、 空回しに近いようなループを何十万回も繰り返すだけだからようやく差が検出できたのであり、 他の処理があればそのコストなど無視できるほど小さくなるでしょう。

結論として「ループの終了条件で、配列の長さを変数に格納しておく」ことはIEでは、わずかに意味がある。 しかし、そう記述するよう強制するほど価値は高いとはいえず、好みの問題に過ぎない、と思います。

test99は、「Math.max.apply(null, array)」が劇的に遅くなった理由が、「apply」のせいかもしれないと思い、 test00のコードに、空の配列を渡し「Math.max.apply(null, array)」を呼び出すコードを無駄に追加しました。 結果として有意な速度低下は検出できず、「Math.max.apply(null, array)」の遅さが「apply」のせいでは無く、 「Math.max()」自体が遅いということを確認できました。


まとめ