たらい回し関数(続き…) - Mae向きなブログ

2009年1月30日の日記にたらい回し関数について書きました。Haskell, Scheme(Gauche)について書いたのですが，C言語ではどうかということで取り組んでみました。たらい回し関数のように，処理を次々にたらい回しにしていく関数を高速化するには，

メモ化
遅延評価

という手法があるのですが，C言語でメモ化を行う場合，3次元配列でやろうと思っても，どの位の大きさで確保すればよいのか，ハッシュを使うにしても面倒だなと思っていたところ，「C-Judyでたらい回し」という記事を見つけました。

まずは，C言語で普通の再帰を用いた方法です。

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;
}