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

JavaScriptでの素数判定アルゴリズムや実装方法の違いによる、実行速度差を計測した際のおまけの情報です。

※元のページは2017年にアルゴリズムを追加し、計測しなおした情報に差し替えました。

環境・条件


小手先修正バリエーションの比較結果

基本となるロジックは奇数での試し割り法です。割る数を3から開始し2ずつ加算し割りまくる、 原始的かつオーソドックスな試し割り法をです。 そしてこのロジックに、小手先の工夫・変化を加え比較しました。

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


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



意外なことに、この全てのコード・すべてのブラウザで有意な差は出ませんでした。 強いて言うとIEでisPrimeA7がわずかに他より遅くなったことと、 「Chrome < IE < Firefox」という傾向がうっすらとありました。

加算よりインクリメントの方が速かった記憶があったので、isPrimeA2を試したのですが、差は確認できませんでした。 別の言語だったかのか改善されたのかもしれません。

isPrime6は「グローバル変数を使うと遅くなる」という説の検証です。 これについては少なくとも今回のロジックでは、有意な差は全く確認できませんでした。 変数のアクセスだけしかしない非実用的なコードで速度差が出るのは確かです。 しかし、一般的な処理の中ではグローバル変数を使うことによる速度の低下は、 認識することが不可能なほど小さいことが確認できました。 どこかのブログの記事か何かを見て「グローバル変数を使うと遅くなる」という人もいますが、 実際には速度の差など無いに等しいので、必要なら気にせず使っていいと思います。

特にisPrime7はかなり遅くなることを期待し書いたのですが、有意な差は生じませんでした。 古いブラウザだったら差があったと記憶していますが、 最近はJavaScriptエンジンで最適化してくれるようになっているのかもしれません。 経験や古い情報を信じ続けるのではなく、時代の流れにとともに 現状・実態を確認し続けることは大切だなと感じました。

とにかく、ちょっとした記述の違いや小手先のテクニックでは、 有意な実行速度の差は出ないことが分かりました。


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

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

※「こちらのページ」で各ソースの確認と、あなたのブラウザを使って実際にテストを実行できます。 ただし、2017年にアルゴリズムを追加し、このページの関数名とは番号がずれています。


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



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

印象的だったのは、どのブラウザでも似た結果が出たことです。 傾向が似るのは当然としても、「Ops/sec」の値もほぼ同じでした。 個人的には「IEは遅い」と思い込んでいたのですが、Chrome・Firefoxに引けをとらない成績を残しました。 「IEは遅い」といわれ続けたため、Microsoftが奮起したのでしょうか。 とにかく、現在ではIEの処理速度は大幅に改善されているようです。 イメージだけで「IEは遅い」というのは、やめた方がよさそうです。

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

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

もしかすると、isPrimeB4, isPrimeB5, isPrimeB9のようなロジックが冗長に感じ 抵抗感を感じる人もいるかもしれません。しかし、上記の結果ほどの差が生じるのです。 見た目も重要ではあるのですが、「最重要」とは考えず、実行速度をより重視した方がいいでしょう。

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


結論としては…アルゴリズムは見た目と実行速度のバランスで決定すべきだと思います。 どんなロジックを書いても大して変わらないような小さな処理や「小手先修正バリエーション」 ほどのわずかな実行速度の差ならこだわる必要はなく、わかりやすい記述を選べばいいと思います。

しかし処理時間がそれなりにかかってしまう可能性のある処理では、 可能な限り処理速度を速くしようと努力すべきです。 とは言っても実行速度はロジックや環境によって変化するので、一概には言えません。 ですので、ロジックをいくつか書き実際にパフォーマンステストを行って判断すべきだと思います。

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


まとめ

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

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

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

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