アルゴリズムの勉強
今までアルゴリズムというものをほとんど勉強してこなかったのだけどもやっぱり重要だよね。というわけでメモ。
今回は「ある数までの全ての素数を求める」アルゴリズムについて考えてみる。
まずベンチマーク用にこんなコードを書く。
#include "prime.h" #include <cstdlib> int main(int argc, char *argv[]) { const int MAX_COUNT = 100 * 1000; for (int i = 1; i < MAX_COUNT; ++i) { isPrime(i); } return EXIT_SUCCESS; }
isPrimeという関数でiが素数かそうでないかを判断することにする。
で、prime.hでisPrime関数を定義してみる。
(結果を出力してないのはベンチマーク的に入出力が絡むとマズイと根拠も無しに思ったから。
でも結果が違うのはマズイので一応デバッグ中は出力してた)
まず最初、何も最適化とか考えずに漠然と書いたコード
#include <cassert> bool isPrime(int n) { assert(n > 0); if (n == 1) return true; const int END_N = n / 2; for (int i = 2; i <= END_N; i++) { if (n % i == 0) { return false; } } return true; }
n / 2を何回も評価しないようにEND_Nという変数に代入してあります。
なぜn / 2かというと、たとえばnが10でiが6以上の時には
n % i == 0
が成り立つことはもうないはずだから。
なので半分以下(nが10だったら5以下)の場合までn % i == 0かどうかを調べればいいはず。
nが奇数の場合END_Nは(奇数 - 1) / 2になりますが、これも成り立つことはないはず(たぶん
数学の証明とかここでできたらカッコイイけど自分はできない人なのでとりあえず適当な数を入れて成り立たないことを確認。確認したら次。
これのベンチマークは↓
> time ./prime ./prime 9.81s user 0.03s system 94% cpu 10.420 total
だいたい10秒くらい。
キャッシュしてみる
次にstd::vector
その素数だけで余剰が0かどうかを確認していけば非素数で確認する手間が省けるんじゃね？
とか適当に書いたのが次
#include <vector> typedef std::vector<int> Prime; Prime prime; // キャッシュ bool isPrime(int n) { assert(n > 0); if (n == 1) return true; const int END_N = n / 2; if (! prime.empty()) { for (Prime::iterator it = prime.begin(); it != prime.end(); ++it) { if (n % *it == 0) { return false; } } } for (int i = 2; i <= END_N; ++i) { if (n % i == 0) { return false; } } // 素数を見つけたらキャッシュしておく prime.push_back(n); return true; }
./prime 9.86s user 0.01s system 95% cpu 10.321 total
あれ・・・？あんまり変わんない・・・？
まぁ、そうだよね。素数で確認したあと結局また全部調べなおしてるし。意味ないじゃん何コレ。
っていうかこのprimeってグローバル変数にする意味ないじゃん。
isPrimeの静的変数にしちゃえばいいやと
bool isPrime(int n) { typedef std::vector<int> Prime; static Prime prime; // キャッシュ assert(n > 0); if (n == 1) return true;
とかやったら↓の結果に。
./prime 10.08s user 0.03s system 93% cpu 10.753 total
えええなんで遅くなるの？
「静的変数 遅い」とかやってもそれらしい検索結果がない。
で、これは宣言時の初期化のオーバーヘッドじゃないかと思って
「静的変数 初期化」でググってみると
http://www.geocities.jp/ky_webid/cpp/language/019.html
Ｃ言語では、静的ローカル変数は、プログラムの実行開始時点で初期化されますが、
C++では、通常のローカル変数と同様に、変数定義が記述されているところで初期化されます。
という記述があったのでとりあえずこれが原因だろうということにして次行ってみる(えー
なにがいけなかったか
で、キャッシュしてるのに結果が変わらなかった理由は、素数で確認したあと再び全部調べなおしていたから。
というわけでそこを改良してみる。
#include <vector> typedef std::vector<int> Prime; Prime prime; // キャッシュ bool isPrime(int n) { assert(n > 0); if (n == 1) return true; const int END_N = n / 2; if (! prime.empty()) { for (Prime::iterator it = prime.begin(); it != prime.end(); ++it) { if (n % *it == 0) { return false; } } if (prime.back() > END_N) { prime.push_back(n); return true; } } int i = prime.empty() ? 2 : prime.back() + 1; while (i <= END_N) { if (n % i == 0) { return false; } i++; } // 素数を見つけたらキャッシュしておく prime.push_back(n); return true; }
変更したのは↓の部分。
if (prime.back() > END_N) { prime.push_back(n); return true; }
見つかった素数のキャッシュで調べたあと、
int i = prime.empty() ? 2 : prime.back() + 1; while (i <= END_N) { if (n % i == 0) { return false; } i++; }
- もしキャッシュがあったらその最大値 + 1から調べなおす
- なかったら最初(nが1の場合は関数の頭部分でtrueを返してるのでこの場合は2)から調べる
./prime 3.15s user 0.03s system 95% cpu 3.337 total
速ええええ！！
かなり速くなった！！すげーー！
std::vector → std:: ?
というわけでかなり速くなったけどstd::vectorである必要はないんじゃないかと思ったので
他の色んなコンテナに変えて試してみる。
(っていってもempty(), push_back(), back()の全てメンバ関数を持つのはvector, list, dequeだけだったけど)
※以下typedefの部分とヘッダ部分を変えただけなのでコードは省略してベンチマークだけ
listの場合
./prime 2.84s user 0.01s system 95% cpu 3.003 total
ちょっと速くなった！！
多分要素の追加を頻繁に行うからだと思う。
