読者です 読者をやめる 読者になる 読者になる

Mae向きなブログ

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

Judyのインストール(Mac OS X)

$ sudo port install judy

コンパイル&実行

MacBook(Mac OS X, 2.4GHz Intel Core 2 Duo, 2GBメモリ)で試してみました。

$ gcc -L/opt/local/lib -I/opt/local/include/ tarai_memo.c -o tarai_memo -lJudy
$ time ./tarai_memo
100

real 0m0.102s
user 0m0.026s
sys 0m0.003s

まとめ

2009年1月30日の日記と総合すると,実行速度は以下の順でした。

  1. Haskell(コンパイル版) … 0.004s
  2. Gauche(遅延評価) … 0.023s
  3. Ruby(メモ化) … 0.090s
  4. C(Judyによるメモ化) … 0.102s
  5. Haskell(インタプリタ) … 0.132s
  6. Ruby, Gauche, Cの普通の再帰は遅すぎたので,途中でCtrl+c