たらい回し関数(続・続き…)

2009年2月3日の日記に対して，nobsunさんから

実行速度の比較をするなら、一つのパラメータでの計算時間だけじゃなくて、パラメータを増加させながら、計算時間がどう変化するかを比較したほうがいいと思いますよ。tarai関数の場合メモ化するよりも、遅延評価するほうがはるかに効果的なはず。

id:SaitoAtsushiさんからは，

私も以前に C++ でたらいまわし関数の遅延評価をやってみたことがあるので紹介しておきます。
http://d.hatena.ne.jp/SaitoAtsushi/20060109/1136785331

というコメントをいただきましたので，

• メモ化(tarai_memo.c)
• 遅延評価(tarai_lazy.cpp)

で値を変えながら実験してみました(CとC++なので条件は違うのですが…)。

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(int argc, char **argv)
{
  int x = 10;
  int y =  5; 
  int z =  0;
  if (argc > 3) {
    x = atoi(argv[1]);
    y = atoi(argv[2]);
    z = atoi(argv[3]);
  }
  printf("%d\n", tarai(x, y, z)); 
  return 0;
}

tarai_lazy.cpp(遅延評価)

C++は全く分からないので，id:SaitoAtsushiさんのを利用させていただきました。

#include <iostream>
using namespace std;

class tarai {
  const int x, y;
  const tarai* tp;
public:
  tarai(int y)
    : x(y), y(y), tp(NULL) {}

  tarai(int x, int y, const tarai& t)
    : x(x), y(y), tp(&t) {}

  operator int() const {
    return (x <= y) ? y :
      (int) tarai(tarai(x-1,y,*tp),
		  tarai(y-1,*tp,x),
		  tarai(*tp-1,x,y));
  }
};

int main(int argc, char **argv) {
  int x = 10;
  int y =  5;
  int z =  0;
  if (argc > 3) {
    x = atoi(argv[1]);
    y = atoi(argv[2]);
    z = atoi(argv[3]);
  }
  cout << tarai(x, y, z);
  return 0;
}

実行結果

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

x	y	z	メモ化(s)	遅延評価(s)
100	50	0	0.023	0.002
200	100	0	0.090	0.005
300	150	0	0.198	0.006
400	200	0	0.364	0.008
500	250	0	0.566	0.015
600	300	0	0.811	0.012
700	350	0	1.116	0.016

実行結果を見てみると，nobsunさんが言われるように，メモ化よりも遅延評価のほうがはるかに効果的でした。

追記

id:SaitoAtsushiさんの「ヒット率を調べてみれば面白いのでは」というアドバイスを受けて，調べてみました。

x	y	z	ヒット率(s)
100	50	0	0.61
200	100	0	0.62
300	150	0	0.62
400	200	0	0.62
500	250	0	0.62
600	300	0	0.62
700	350	0	0.62

上記のx,y,zの組み合わせでは，約60%のヒット率でした。ということは，せっかくメモした40%は再利用されなかったということになります。