« シンボルテーブルのFUNCについて | トップページ

2007年11月 8日 (木)

擬似的末尾再帰最適化

なんか中国語みたいなタイトルになってますがお気にせずに。
コンパイラには(インタプリタにも?)末尾再帰の最適化がありますが、擬似的に手動でかけないかとやってみた。ちなみに言語はC言語。

こういう0~nまでの和を出す再帰関数を最適化してみる。

long long func(int n)
{
    if (n == 0)
        return 0;
    else
        return n + func(n-1);
}

自分の理解だとスタックを積まないで関数の先頭にgotoするというのが末尾再帰の最適化。なので、再帰するところで関数を呼び出さずに値を更新して先頭に戻ればよい。

long long func2(int n)
{
    long long ans = 0;
f:
    if (n == 0) {
        return ans;
    }
    ans += n;
    n--;
    goto f;
}

精度があんまりよくないclock関数で、テキトーにテストする。

int main()
{
    clock_t start, end;
    int i;

    start = clock();
    for (i = 0; i < 10000; i++) {
        func(65536);
    }
    end = clock();
    printf("%f\n", (double)(end - start) / (double)CLOCKS_PER_SEC);

    start = clock();
    for (i = 0; i < 10000; i++) {
        func2(65536);
    }
    end = clock();
    printf("%f\n", (double)(end - start) / (double)CLOCKS_PER_SEC);

    return 0;
}

Mac OS X, gcc 4.0.1で実験した結果が以下。

[~]% gcc test.c
[~]% ./a.out
12.750000
1.950000
[~]% gcc -O2 test.c
[~]% ./a.out
1.770000
0.740000
[~]% gcc -O3 test.c
[~]% ./a.out
1.900000
0.250000

結構違いがでた。たぶん他の環境でも擬似的に最適化した方が速いと思う。
あと、最適化した方はスタックオーバフローしない。
今回は簡単な関数でやったけど、末尾再帰の部分と関数先頭を少し書き換えるだけなので、他の再帰関数にも結構簡単に適用できる方法かもしれない。

一応まとまったファイルは「test.c」です。コメントゼロでごめんなさい。

|

« シンボルテーブルのFUNCについて | トップページ

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/126478/17010063

この記事へのトラックバック一覧です: 擬似的末尾再帰最適化:

« シンボルテーブルのFUNCについて | トップページ