[ADP開発日誌]Ver 0.56 アルファ版リリース

 前回のリリース告知からはや2ヵ月半が過ぎやっと述語キャッシュ機能を付けました。 キャッシュ機能ですが、同一の関数(述語)の呼び出し(評価)を行う場合に、1回目の呼び出しの結果を保存しておき、2回目の呼び出しでは1回目の呼び出し結果を使います。同一の判定ですが、述語名と引数の値が同じならキャッシュします。変数に関しては、値があればその値が同じか比較し、値がなければ同一とみなします(変数名が違っていてもキャッシュが有効になります)。 なので、printn関数のように副作用がある場合やrand関数のように毎回異なる値になることを期待する述語の場合はキャッシュ機能を使うとバグリます。つまりprintnの場合は2回目の画面出力が行われなくなり、rand関数の場合は同じ値を返して乱数でなくなります。   以下、フィボナッチ数例の値を求めるサンプルを例に、使い方を示します。   まずはキャッシュなし版のコード(fib1.p)で、
+fib(0,0);
+fib(1,1);
+fib($x,$y),fib($x - 1, $f1),fib($x - 2, $f2), $y == $f 1+ $f2;
,fib(25).printn;
以下、私のマシン(Core i7-920)での実行結果です。
D:>adp -t fib1.p
75025
time is  1538ms.
  以下、キャッシュあり版のコード(fib2.p)で、
+fib(0,0);
+fib(1,1);
+fib($x,$y),fib$($x - 1, $f1),fib$($x - 2, $f2), $y == $f 1+ $f2;
,fib(25).printn;
以下、私のマシン(Core i7-920)での実行結果です。
D:>adp -t fib2.p
75025
time is     3ms.
  キャッシュあり版のコードですがぱっとみた感じ違いが解らないかもしれませんが、fib述語を呼び出している部分『fib$($x - 1, $f1)』で、fib$ と述語名の終わりに $ が付いています。つまり、  述語名の後に $ をつけるとキャッシュ機能が有効になります。 キャッシュあり版となし版で、速度を比較しますとあり版が激速になっていることが分かるかと思います。 fib1.pフィボナッチ数例のコードですが、良く見るコードだと思いますが、このサンプルは実行速度の面で問題があります。2回再帰関数を呼び出しているので実行時間は、入力する値が大きくなると指数関数的に増えて行きます。 fib2.pの例で、キャッシュ機能を使いますと、再帰呼び出しが事実上1回になりますので、入力値が大きくなっても実行時間が指数関数的には増えなくなります。 キャッシュは万能でないので、fib2.pの例では、再帰関数を使う別の問題(大きな数を計算させるとスタックがあふれる)は解決できませんが、ADPのキャッシュ機能を使えば、コードを若干修正するだけでそこそこの性能が得られるので適用対象によっては有効な武器となるでしょう。 (ちなみにですが、フィボナッチ数例を求める実用的なコードではもっと別の実装を選択します。)   通常プログラムを高速化したいときですが、プログラマは追い込まれており、出来るだけお手軽にキャッシュ機能をつけたいと思います。また、不具合が出たときに取り外すのも手軽にやりたいと思います。このようなコンセプトの元、  ADPでは、関数(述語)の呼び出しそのものをキャッシュする機能 としてキャッシュ機能を実装しています。これは、なかなか便利だと思います。 次回は、別の例でキャッシュ機能を紹介します。
2010-11-16 | コメント:0件

コメントをどうぞ


『不適切なコメントへの対応』を一読下さい。
現在コメントは承認制となっております。

Previous Page | Next Page