フィボナッってみた
なにも新しい事はやってない。
再帰を使わなければ簡単に書ける。
function fib(n) { if (n < 1) return 1; var [a, b] = [0, 1]; for (var i = 1; i < n; i++) { [a, b] = [b, a + b]; } return b; }
再帰を使ったものだと、↓とか参考になる。
最も簡単に fib を高速化する方法 - ドレッシングのような
この方法は、再帰を使わないコードと比べても可読性が落ちずに書けてていいな。
function fib(n) { function _fib(n) { if (n <= 1) return [1, 0]; var [a, b] = _fib(n-1); return [a + b, a]; } return _fib(n)[0]; }
テストしてみる。
コードは、
Re: 斜め上 - JavaScriptで遊ぶよ - g:javascript
から借用。
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 | 2 | 2.00 |
2 | 1 | 3 | 1.50 |
3 | 2 | 4 | 1.33 |
4 | 3 | 5 | 1.25 |
5 | 5 | 5 | 1.00 |
6 | 8 | 5 | 0.83 |
7 | 13 | 7 | 1.00 |
8 | 21 | 8 | 1.00 |
9 | 34 | 8 | 0.89 |
10 | 55 | 9 | 0.90 |
11 | 89 | 10 | 0.91 |
12 | 144 | 10 | 0.83 |
13 | 233 | 11 | 0.85 |
14 | 377 | 13 | 0.93 |
15 | 610 | 13 | 0.87 |
16 | 987 | 14 | 0.88 |
17 | 1597 | 15 | 0.88 |
18 | 2584 | 16 | 0.89 |
19 | 4181 | 17 | 0.89 |
20 | 6765 | 18 | 0.90 |
21 | 10946 | 18 | 0.86 |
22 | 17711 | 20 | 0.91 |
23 | 28657 | 20 | 0.87 |
24 | 46368 | 20 | 0.83 |
25 | 75025 | 22 | 0.88 |
26 | 121393 | 25 | 0.96 |
27 | 196418 | 30 | 1.11 |
28 | 317811 | 35 | 1.25 |
29 | 514229 | 31 | 1.07 |
30 | 832040 | 29 | 0.97 |
31 | 1346269 | 26 | 0.84 |
32 | 2178309 | 28 | 0.88 |
33 | 3524578 | 28 | 0.85 |
34 | 5702887 | 28 | 0.82 |
35 | 9227465 | 31 | 0.89 |
36 | 14930352 | 32 | 0.89 |
37 | 24157817 | 186 | 5.03 |
38 | 39088169 | 44 | 1.16 |
39 | 63245986 | 37 | 0.95 |
40 | 102334155 | 30 | 0.75 |
41 | 165580141 | 30 | 0.73 |
42 | 267914296 | 32 | 0.76 |
43 | 433494437 | 32 | 0.74 |
44 | 701408733 | 33 | 0.75 |
45 | 1134903170 | 34 | 0.76 |
46 | 1836311903 | 35 | 0.76 |
47 | 2971215073 | 36 | 0.77 |
48 | 4807526976 | 37 | 0.77 |
49 | 7778742049 | 38 | 0.78 |
50 | 12586269025 | 39 | 0.78 |
51 | 20365011074 | 39 | 0.76 |
52 | 32951280099 | 40 | 0.77 |
53 | 53316291173 | 40 | 0.75 |
54 | 86267571272 | 42 | 0.78 |
55 | 139583862445 | 45 | 0.82 |
56 | 225851433717 | 48 | 0.86 |
57 | 365435296162 | 49 | 0.86 |
58 | 591286729879 | 51 | 0.88 |
59 | 956722026041 | 193 | 3.27 |
60 | 1548008755920 | 64 | 1.07 |
61 | 2504730781961 | 76 | 1.25 |
62 | 4052739537881 | 45 | 0.73 |
63 | 6557470319842 | 46 | 0.73 |
64 | 10610209857723 | 47 | 0.73 |
65 | 17167680177565 | 49 | 0.75 |
66 | 27777890035288 | 49 | 0.74 |
67 | 44945570212853 | 54 | 0.81 |
68 | 72723460248141 | 63 | 0.93 |
69 | 117669030460994 | 72 | 1.04 |
70 | 190392490709135 | 58 | 0.83 |
71 | 308061521170129 | 56 | 0.79 |
72 | 498454011879264 | 57 | 0.79 |
73 | 806515533049393 | 57 | 0.78 |
74 | 1304969544928657 | 202 | 2.73 |
75 | 2111485077978050 | 68 | 0.91 |
76 | 3416454622906707 | 79 | 1.04 |
77 | 5527939700884757 | 57 | 0.74 |
78 | 8944394323791464 | 57 | 0.73 |