JavaScriptでの素数判定アルゴリズムのパフォーマンステスト

JavaScriptでの素数判定アルゴリズムや実装方法の違いによる、実行速度差を計測してみました。環境・条件は以下のとおりです。

環境・条件

実装ロジックの違いの比較結果

実装ロジックを大きく変えて比較しました。 ざっくり言えば、手当たり次第に割るか、素数では無い数をできるだけ排除するかの違いといえます。

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


左から順に、Chrome56, IE11, Firefox51での結果です。(秒間実行回数。バーが長いほど速い)



明確に差が出ました。結果の傾向としては明らかで、 割る数の対象を減らしたロジックほど速いという結果になりました。 よく見かけるisPrimeB2と、素数リストを用意するisPrimeB9では、おおむね3倍の差という結果になりました。

ブラウザ間の差としては、IEが最も速く、ChromeがIEとほぼ同じかほんの少し遅い程度。 FirefoxはIEより20-30％程度遅いという結果でした。2年前に計測した際にはこれほどの差はありませんでした。 Firefoxが単独でかなり処理速度が低下したようです。 昔は「IEは遅い」ものでしたが、今では「Firefoxは遅い」という状況のようです。この結果はとても印象的でした。 ちなみにEdgeでも計測したかったのですが、JSLitmusがうまく動かず計測できませんでした。残念。

isPrimeB0, isPrimeB1, isPrimeB2のロジックはよく見かけます。 isPrimeB3はisPrimeB2を少し改良したバージョンです。 加算する数を固定し、ループの回数を半分にし、1ループの中で2回割るようにしました。 こうすることで、diff生成の加算に相当する処理を半分に削減しています。その分わずかに高速化しています。 「この方が処理が少し減らせそう」とある日突然思いつき試したところ、期待通りの結果が得られました。

isPrimeB4, isPrimeB5は、割る数をそれぞれ「2と3と5の倍数を除外」「2と3と5と7の倍数を除外」としたバージョンです。 この手法は少なくとも私はこれまで見たことがありませんでしたが、「2と3の倍数を除外」という考えがアリなら 除外する数をさらに増やせばさらに速くなるだろうと思い作ってみました。 コードの見た目は冗長になっていますが、実際に実行される無駄な比較・計算が減っており、期待通り、その分高速になっています。 さらにさらに11も追加すると、さらなる速度向上が望めそうですが、さらに大幅に冗長になることが分かっているため7まででやめておきます。

もしかすると、isPrimeB4, isPrimeB5, isPrimeB9のようなロジックが冗長に感じ 抵抗感を感じる人もいるかもしれません。しかし、上記の結果ほどの差が生じるのです。 見た目も重要ではあるのですが「常に最重要」とは考えず、何が重要なのかを状況に応じて考え、 もし速度が重要な場合にはあえて冗長なコードにし計算量を減らし、 実行速度を向上させるという選択もできるようにしておいた方がいいでしょう (言うまでもないことですが、冗長にすれば常に速くなるというわけではありません)。

あと、実は最遅アルゴリズムとして、ループの上限を対象数値の平方根ではなく、 対象数値そのものまでとするアルゴリズムでも試しました。 しかし「2271391831」の判定をするには遅すぎて、ブラウザに 「応答していません。応答があるまで待つか、強制終了してください」 というダイアログが出てしまい測定が出来ませんでした。 数字で出せば、「4.77万までの計算」と「22.7億までの計算」であり、 4.77万倍差が発生するのでそこを考えれば当然ではありますが、 上限値を平方根にかけるかどうかで驚異的な速度差が発生することを改めて確認できました。


結論としては…アルゴリズムは見た目と実行速度のバランスで決定すべきだと思います。 わずかな実行速度の差なら、わかりやすい記述を選んだ方がいいと思います。 しかし処理時間がそれなりにかかってしまう可能性のある処理では、 可能な限り処理速度を速くしようと努力すべきです。 とは言っても実行速度はロジックや環境によって変化するので、一概には言えません。 ですので、ロジックをいくつか書き実際にパフォーマンステストを行って判断すべきだと思います。

実際私も、今回意図的に遅くしようと書いたコードも遅くならなかったことから、 実際にパフォーマンステストを行うことの重要性を痛感しました。 「JSLitmus」を使用すると 割と手軽にパフォーマンステストが行えますので、試してみてはいかがでしょうか。


まとめ

ちょこっとアンケート＆メッセージ

このページに関するちょっとした感想または、要望、バグ・間違いの指摘などは、下記の送信欄からお送りください。 質問・その他お問合せなど、返信をご希望の方は「こちらのページ」からメッセージをお送りください。

「このページはお役に立ちましたか？」のアンケートと自由メッセージのどちらか一方でかまいません (両方だとよりうれしいです)。お気軽にご利用ください (感想・どんな用途で使用したかなどをいただけると作成・運営の励みになります！)。

このページはお役に立ちましたか？
自由メッセージ
認証コード 必須
画像のひらがな一文字を入力してください。拗音・促音・濁点・半濁点はありません。