Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

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

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%は再利用されなかったということになります。