算法技巧: 如何使用JavaScript编写高效的fabonac

2015-04-19 本文已影响8703人 Tulayang

<br />

斐波那契数列，（意大利语：Successione di Fibonacci），又译做费波拿契数列、费氏数列、黄金分割数列。发明者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci）。

斐波那契数列指的是这样一个数列：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

在数学上，斐波那契数列是以递归的方式定义：

f(0) = 0
f(1) = 1
f(n) = f(n - 1) + f(n - 2) // n >= 2

1202年，斐波那契完成了巨著《计算之书》（Liber Abaci），斐波那契数列便是出自这本著作，它来自一个“兔子繁殖”问题：

假定兔子在出生两个月后就有繁殖能力，一对兔子每个月能生出一对小兔子。如果所有兔子都不死，那么一年后可以繁殖多少对兔子？
兔子繁殖

程序员的信仰

作为一个Programmer，多年经验给我的印象，我们不是纯的数学家，我们也解决数学问题，并用数学的知识武装自己。然而有时候，我们还要考虑一些非纯数学的问题。比如性能，维护，可扩展，...

接下来，我们不再过多的关注斐波那契数列的历史，和其在物理化学上的贡献，把关注点集中在编程实现上。

第一个fabonacci程序

根据fabonacci的定义，我们可以很轻松的编写出实现代码：


function fabonacci(n) {
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    return fabonacci(n - 1) + fabonacci(n - 2);
}

让我们来测试一下所编写的程序，测试计算第50个值fabonacci(50):


var start  = new Date();
var result = fabonacci(50);
var end    = new Date();

console.log('fabonacci(%d) = %d, use time %dms.', 
            50, 
            result,
            end.getTime() - start.getTime());

打开Shell，运行Node.js:
$ node

然后，复制上面的代码，回车，得到如下的控制台输出:
> fabonacci(50) = 12586269025, use time 242702ms.

天啊！
在我的笔记本上计算fabonacci(50)，竟然花费了242秒（4分钟）！
一定是出现了什么问题！

让我们仔细的推导整个计算过程，来找出潜在的问题：


* f(0) = 0

* f(1) = 1

* f(2) = f(1) + f(0)

* f(3) = f(2) + f(1) 
       = (f(1) + f(0)) + f(1)

* f(4) = f(3) + f(2) 
       = (f(2) + f(1)) + (f(1) + f(0))
       = ((f(1) + f(0)) + f(1)) + (f(1) + f(0))

* f(5) = f(4) + f(3)
       = (f(3) + f(2)) + (f(2) + f(1))
       = ((f(2) + f(1)) + (f(1) + f(0))) + ((f(1) + f(0)) + f(1))
       = (((f(1) + f(0)) + f(1)) + (f(1) + f(0))) + ((f(1) + f(0)) + f(1))

* ...

看出来了吗？

当我们计算f(0)的时候，计算了１次f(0) => f(0)
当我们计算f(1)的时候，计算了１次f(1) => f(1)
当我们计算f(2)的时候，计算了１次f(1) + f(0) => f(2)
当我们计算f(3)的时候，根据递归过程，实际计算了
- 1次f(1) + f(0) => f(2)
- 1次f(2) + f(1) => f(3)
当我们计算f(4)的时候，根据递归过程，实际计算了
- 2次f(1) + f(0) => f(2)
- 1次f(2) + f(1) => f(3)
- 1次f(3) + f(2) => f(4)
当我们计算f(5)的时候，根据递归过程，实际计算了
- 3次f(1) + f(0) => f(2)
- 2次f(2) + f(1) => f(3)
- 1次f(3) + f(2) => f(4)
- 1次f(4) + f(3) => f(5)
...

通过这个规律，我们发现

计算f(4)的时候，f(2)的值被重复计算了2次
计算f(5)的时候，f(2)的值被重复计算了3次，f(3)的值被重复计算了2次
...

计算的数字越大，重复的计算就会越多。

怎么解决重复计算的问题？

通过上面的过程推导，我们可以这样思考：

既然是计算过的数字值被重复计算，那么我们可以使用缓存的方式，把计算过的结果保存起来，更大的数字计算直接从缓存中取，不就可以省去计算过程了吗？

因此，我们可以设定一个缓存对象:

var cache = {};

用来保存我们已经计算过的值，cache的使用过程将会是这样的：
假设我们已经计算过了0～9的结果

cache = {
    0: 0,
    1: 1,
    2: 1,
    3: 2,
    4: 3,
    5: 5,
    6: 8,
    7: 13,
    8: 21,
    9: 34
};

当我们要计算fabonacci(5)的时候，我们就能够1次从缓存中取出结果：

return cache[5];

是不是十分完美？
这样就只计算了1次cache[5]！

那么，当我们计算fabonacci(10)的时候，我们只需要：

var result = cache[10] = cache[8] + cache[9];
return result;

只计算了1次cache[8] + cache[9]，同时把结果保存进了缓存cache！

新版本的，性能高效的fabonacci程序

经过我们的努力，实现了如下性能高效的fabonacci程序：

var cache = {
    0: 0,
    1: 1
};

function fabonacci(n) {
    if (typeof cache[n] === 'number') { 
        return cache[n];
    }
    var result = cache[n] = fabonacci(n - 1) + fabonacci(n - 2);
    return result;
}

这个代码，我们还可以再写的优雅些，像下面这样：

var cache = {
    0: 0,
    1: 1
};

function fabonacci(n) {
    return typeof cache[n] === 'number'
           ? cache[n]
           : cache[n] = fabonacci(n - 1) + fabonacci(n - 2);
}

OK!

现在，用我们上面的测试代码测试一下新版本的fabonacci程序吧：

var start  = new Date();
var result = fabonacci(50);
var end    = new Date();

console.log('fabonacci(%d) = %d, use time %dms.', 
            50, 
            result,
            end.getTime() - start.getTime());

// fabonacci(50) = 12586269025, use time 2ms.

！！！Perfect！！！这次计算fabonacci(50)只用了2ms的时间！

你喜欢函数式吗？

上面的是C语言的风格，cache放在外部，你喜欢函数式编程吗？
我们也可以编写函数式风格的fabonacci程序，有助于减少变量混乱：

function fabonacci() {
    var cache = {
        0: 0,
        1: 1
    };
    return function __fabonacci(n) {
        return typeof cache[n] === 'number'
               ? cache[n]
               : cache[n] = __fabonacci(n - 1) + __fabonacci(n - 2);
    };
}

var fb = fabonacci();
fb(50);

另外，你会发现cache的键都是数字，而且是从0开始递增计数，
所以，cache也可以用数组代替：

function fabonacci() {
    var cache = [0, 1];
    return function __fabonacci(n) {
        return typeof cache[n] === 'number'
               ? cache[n]
               : cache[n] = __fabonacci(n - 1) + __fabonacci(n - 2);
    };
}

使用纯C风格的代码好，还是函数式风格的代码好？
我觉得这两个都很好，很直观，容易维护，容易理解。
在Node.js的模块下，你可以很安全的放置你的变量，所以C风格也不是问题。

这完全取决于你的风格！！！

当然，我们也可以奉上面向对象的风格：

function Fabonacci() {
    if (!(this instanceof Fabonacci)) {
        return new Fabonacci();
    }
    this._cache = [0, 1];
}
Fabonacci.prototype.compute = function (n) {
    return typeof this._cache[n] === 'number'
           ? this._cache[n]
           : this._cache[n] = this.compute(n - 1) + this.compute(n - 2);
};


Fabonacci().compute(50);