素数とJavaと実行速度
はじめに
最近、素数にちょっとした縁があったので、素数を計算するプログラムをRuby書いてみました。
おそらく、もっと良いロジックやひょっとするとライブラリもあるかとは思ったんですが、なんとなく自力で書けるかなーと試してみたかったので。
あと、数学も詳しくないので、細かい表記が間違っていたらゴメンナサイ。
基本方針
- 小さい数から判定していく（素数か否かを検査する対象をnとする）
- 素数という事は、素因数分解できないはず->という事は、今まで素数と判定した数値群で割った時、余りが0ではない。
- 上記の数値群の小さい方から判定していき、数値群の数がnの平方根を超えたら、余りが0でない事が確定。（割り切れる場合は、それまでに余り0が出てるはず）
Rubyのコード
基本方針の仕様に基づいて、Rubyで書いてみたコードがこちら。
素数判定の部分をメソッドにして呼び出し、素数と判定されたものは数値群（配列）にどんどん追加していきました。
また、判定は2と3は初期値に設定しておき（2は配列に1つ以上の要素を入れる為、3は2が既に平方根の値を上回っているので）、5からメソッドで判定しています。
10万回判定すると終わります。
Javaでつまずいたこと
で、簡単なコードなので最近文法を勉強し始めたJavaでも書いてみて、LL言語とコンパイル言語がどれくらい実行速度が違うのかを試してみました。そのとき調べた事をまとめてみました。
Javaの配列は、固定長
Perl、Rubyでは何も考えずに配列を使っていましたが、Javaでは配列の中身に対して型を宣言するのはもちろんの事、配列の長さも宣言時、または初めて使う時に長さも指定する必要があります。
いくつ素数があるのか分からないし、最大限の目安で要素数確保するのも不格好なので、ググって調べた所、可変長の表現できる配列風クラスArrayListクラスがあったのでこれを使ってみました。
少し気をつけないといけないのは、配列は変数であるのに対して、ArrayListはクラス（使うときはインスタンスオブジェクト）なので、使い方も似て非なるところですね。
一番「そんな事までしないといけないのかー」と思ったのは、ArrayListはオブジェクトを格納するコレクションなので、1とか2とか、基本形の値を格納出来ない事でした。じゃ、どうやって格納するの？というと、intの"値"を数値のようなIntegerオブジェクトに変換して、オブジェクトとして格納、取り出す時もIntegerオブジェクトのメソッドで値を取り出す、という一手間が必要でした。（35行目、28行目あたりです）
それと、ArrayListのオブジェクトを引数で渡す時は、受け取るメソッドの仮引数宣言部分でも、中身の型まで宣言しておかないと警告が出る部分ですね。ここまで厳密だとは知らなかったので勉強になりました。
速度を試す
では、Javaのコードはjavacコマンドでコンパイルして、Rubyと実行速度を比べてみましょう。
Rubyの実行結果
Javaの実行結果
実行速度で約2倍くらいでしょうか。（実際は、最初に書いていたロジックがもっとドン臭くて全探索に近かったので、11倍くらいの圧倒的な差でした。） という事は、アルゴリズムのオーダによって、言語の速度差が加速度的に増すということですね。 効率良いロジック、大事。
@tomcha_ Java Appletの時はほんまに遅かったのでそのイメージがついて回ってるんですかね、僕もそういう印象ですし。
— ネコ半径 (@azumakuniyuki) December 19, 2014Javaは実行速度が遅いというイメージでしたが、LLよりはやはり速かったです。
ここまでくれば・・・
じゃぁ、Cとかだとどこまで速くなるんだ？ 好奇心にまかせて、初めてC++を書いてみました。可変長配列とか、Cだと大変そうな気がしたので。
C++の印象は、Javaほど書き方が面倒ではない印象でした。
で、実行速度は・・・
Javaとあまり変わらない・・・ってか、最初のドン臭いコードではJavaより少しだけ遅かった・・・。
もっと圧倒的な差が出ると思っていたのですが、以外でした。
しかし、この結果には少し注意点があって、Javaのコードの計測はVM（Javaを実行させる前準備作業）の時間が考慮されていないコードになっています。1回めのターミナルからコマンド打って実行した時は、書いたコードが走り出すまで少しタイムラグがあります。
もちろんC++ではこの時間は無いので、
C++の実行時間 ≒ VM起動時間+Javaの実行時間 ＜ Rubyの実行時間
という結果が妥当な様です。 文法も実行結果も、色んな言語を比較してみるのも面白いですね。
