Hatena::Groupjavascript

JavaScriptで遊ぶよ

 | 

2010-09-12

Re: 斜め上

14:24

フィボナッチ数を線形時間で計算する方法。すごい。

前に Haskell で遅延評価を使って似たようなことやる方法を見たことがあったんだけど、まさか JavaScript でもこういうふうにできるとは、という感じ。

fib1, fib2, fib3 とするのは、arguments.callee.caller. (...) .caller.arguments が循環的(再帰的)になってしまったときに、本来の呼び出し元の arguments が取れずにスタックの浅い方が引っかかってしまうためらしい。(これって ECMAScript で定義されてるんだろうか?)

そんじゃあこうしたらいいんじゃないでしょうか。

function fib(n) {
  function _fib(n, a, b, arg1, arg2) {
    if(n>1) _fib(n-1, a, b, arguments, arg1);
    return arg1[2] = arg2[1] = a+b;
  }

  return _fib(n, 0, 1, [], []);
}

テストしてみる。

function test(n) {
  var t = new Date;
  for (var i = 0; i < 1000; i++) {
    var res = fib(n);
  }
  t = new Date - t;
  console.log('| ' + n + ' | ' + res + ' | ' + t + ' | ' + (t/n).toFixed(2) + ' |'); // はてな記法
}

for (var i = 1; i < 79; i++) {
  test(i);
}

結果。

i 番目 フィボナッチ数 所要時間 (ms / 1000回) 時間 / i
1 1 5 5.00
2 1 8 4.00
3 2 11 3.67
4 3 12 3.00
5 5 14 2.80
6 8 17 2.83
7 13 19 2.71
8 21 21 2.63
9 34 23 2.56
10 55 26 2.60
11 89 29 2.64
12 144 31 2.58
13 233 32 2.46
14 377 34 2.43
15 610 37 2.47
16 987 39 2.44
17 1597 42 2.47
18 2584 43 2.39
19 4181 45 2.37
20 6765 48 2.40
21 10946 52 2.48
22 17711 99 4.50
23 28657 59 2.57
24 46368 59 2.46
25 75025 58 2.32
26 121393 60 2.31
27 196418 63 2.33
28 317811 64 2.29
29 514229 66 2.28
30 832040 70 2.33
31 1346269 71 2.29
32 2178309 73 2.28
33 3524578 75 2.27
34 5702887 86 2.53
35 9227465 151 4.31
36 14930352 86 2.39
37 24157817 99 2.68
38 39088169 91 2.39
39 63245986 89 2.28
40 102334155 91 2.27
41 165580141 93 2.27
42 267914296 95 2.26
43 433494437 96 2.23
44 701408733 106 2.41
45 1134903170 165 3.67
46 1836311903 110 2.39
47 2971215073 113 2.40
48 4807526976 107 2.23
49 7778742049 110 2.24
50 12586269025 112 2.24
51 20365011074 122 2.39
52 32951280099 116 2.23
53 53316291173 178 3.36
54 86267571272 142 2.63
55 139583862445 124 2.25
56 225851433717 125 2.23
57 365435296162 129 2.26
58 591286729879 132 2.28
59 956722026041 133 2.25
60 1548008755920 195 3.25
61 2504730781961 152 2.49
62 4052739537881 138 2.23
63 6557470319842 140 2.22
64 10610209857723 143 2.23
65 17167680177565 145 2.23
66 27777890035288 217 3.29
67 44945570212853 170 2.54
68 72723460248141 154 2.26
69 117669030460994 155 2.25
70 190392490709135 157 2.24
71 308061521170129 158 2.23
72 498454011879264 227 3.15
73 806515533049393 181 2.48
74 1304969544928657 166 2.24
75 2111485077978050 167 2.23
76 3416454622906707 170 2.24
77 5527939700884757 230 2.99
78 8944394323791464 189 2.42

ほぼ線形。Firebug のコンソールで試した。

sumimsumim2010/09/12 15:43なるほど arguments を渡してしまえば簡単ですね。ありがとうございます。
Argumentsオブジェクトと [] の多態を利用したエラー回避も素敵です。w

「本来の呼び出し元の arguments が取れずにスタックの浅い方が―」にはワケが分からず苦しめられました。これは仕様なのでしょうかね。だとしたら困った仕様です。

edvakfedvakf2010/09/12 16:38>これは仕様なのでしょうかね。

ちょっと仕様を読み始めましたが、面倒だったのでググっただけでお茶を濁させてください。

http://my.opera.com/hallvors/blog/2007/01/22/quirky-arguments#comment2549736
ここのコメントによると、ECMA262 1 の時点で既に非推奨(互換性のために残してあるだけ)だったらしく、その直後に跡形もなく消えたそうです。
なので ECMAScript 3 や ECMAScript 5 には関数の arguments プロパティというものは無いそうです。

edvakfedvakf2010/09/12 16:42ちなみに ECMAScript 5 の strict mode で arguments.callee や Function.prototype.caller はエラーとなります。
主にパフォーマンスの問題だという話です。将来の言語仕様からは消えると思われます。
(arguments という特殊変数自体は消えません)

sumimsumim2010/09/12 23:52将来的には消えてしまう機能なのですね。残念。

 |