性能优化-循环优化[三]

忘是亡心i 2023-01-23 03:53 25阅读 0赞

独立于语言

### 递归使用迭代替换 ###

递归调用栈太深，所有递归都能用迭代实现。以斐波那契数列为例子

递归实现：

var fib = function(n) { 
        if (n <=1) return n
        return fib(n - 1) +  fib(n - 2)
    };

缺点：调用栈太深

迭代替换：

var fib = function (n) { 
        if (n <= 1) return n
        let i = 1;
        let a = 0; let b = 1;
        while (i++ < n - 1) { 
           [a, b] = [b, a + b]
        }
        return a + b
    }

### 迭代的优化 ###

`Duff's Device` 减少迭代的次数

在数组长度达到一定数量级之后，后者效率比原始高很多(调整上面数组长度到百万级别，效率提升50%

### 缓存数据 ###

重复计算的数据缓存,还是以上面的Fibonacci数列为例，上面的将递归优化为迭代，实际上已经用到了缓存，但是我们再优化一下，将每种情况都缓存下来。

var fib3 = function (n) { 
        if (!fib3.memo) { 
            fib3.memo = { 
                0: 0,
                1: 1
            }
        }
        if (n <= 1) {  return fib3.memo[n] }
        if (fib3.memo[n]) {  return fib3.memo[n] }
        fib3.memo[n] = fib3.memo[n-1] + fib3.memo[n-2]
        return fib3.memo[n] 
    }

--------------------

[达夫设备： 维基百科][Link 1]

[Link 1]: https://zh.wikipedia.org/wiki/%E8%BE%BE%E5%A4%AB%E8%AE%BE%E5%A4%87