2009年1月30日の日記にたらい回し関数について書きました。Haskell, Scheme(Gauche)について書いたのですが，C言語ではどうかということで取り組んでみました。たらい回し関数のように，処理を次々にたらい回しにしていく関数を高速化するには，
- メモ化
- 遅延評価
という手法があるのですが，C言語でメモ化を行う場合，3次元配列でやろうと思っても，どの位の大きさで確保すればよいのか，ハッシュを使うにしても面倒だなと思っていたところ，「C-Judyでたらい回し」という記事を見つけました。
tarai.c
#include <stdio.h> int tarai(int x, int y, int z); int tarai(int x, int y, int z) { if (x <= y) return y; else return tarai(tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y)); } int main(void) { printf("%d\n", tarai(100, 50, 0)); return 0; }
実行してみると，予想通り，結果が帰ってくるまでに相当時間がかかるので，Ctrl+c。
次に，Judyを使ったメモ化版です。
tarai_memo.c(メモ化)
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <Judy.h> #define KEYLEN 1024 Pvoid_t PJSLArray = (Pvoid_t) NULL; /* initialize JudySL array */ int tarai(int x, int y, int z); int tarai(int x, int y, int z) { Word_t *pvalue, value; uint8_t key[KEYLEN]; snprintf((char *)key, KEYLEN, "%d,%d,%d", x, y, z); /* x,y,zからkeyを作成 */ JSLG(pvalue, PJSLArray, key); /* keyから検索 */ if (pvalue != NULL) /* 既に計算済み */ return (int)*pvalue; if (x <= y) value = y; else value = tarai(tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y)); pvalue = &value; JSLI(pvalue, PJSLArray, key); /* 計算結果を登録 */ return value; } int main(void) { printf("%d\n", tarai(100, 50, 0)); return 0; }
Judyのインストール(Mac OS X)
$ sudo port install judy
