アルゴリズムの勉強


今までアルゴリズムというものをほとんど勉強してこなかったのだけどもやっぱり重要だよね。というわけでメモ。
今回は「ある数までの全ての素数を求める」アルゴリズムについて考えてみる。


まずベンチマーク用にこんなコードを書く。

#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型のprimeという変数に素数をキャッシュしておいて
その素数だけで余剰が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言語では、静的ローカル変数は、プログラムの実行開始時点で初期化されますが、
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;
        }

見つかった素数のキャッシュで調べたあと、

  • その素数の最大値(prime.back())がEND_Nより大きかったら「もう割り切れない = 素数
  • 最大値が小さかったらまだ素数かどうか判断できないので↓に続く
    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

ちょっと速くなった!!
多分要素の追加を頻繁に行うからだと思う。

dequeの場合
./prime  3.52s user 0.03s system 95% cpu 3.718 total

遅くなったorz
そもそもdequeってなんだっけ?と思ってググってみると


7章:STL

コンテナの両端への追加および削除が頻繁に行われる 操作に向いています。
また、ランダムアクセスも可能で、定数時間でアクセス可能です。

両端への追加、削除とランダムアクセスも得意、と。

  • vectorは追加、削除が苦手だけどランダムアクセスは得意
  • listは追加、削除が得意だけどランダムアクセスは苦手

というのを考えると赤魔導師みたいな感じだろうか(うまいこといった

まとめ

アルゴリズム大事。それとコンテナの選択も大事。
自分はvectorとlistぐらいしか使ったことなかったように思うので
これからは色んなコンテナを状況に合わせて使っていこうと思った。


とりあえず積読してたSTLの本を最後まで読み切ろう・・・