斐波那契數(shù)列求和的js方案以及優(yōu)化

xinhaip 發(fā)布于2019-08-20 11:35 / 1568人閱讀

摘要：在上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡單的優(yōu)化和用另一種方法實(shí)現(xiàn)。動態(tài)規(guī)劃解決方案斐波那契數(shù)列求和除了可以用遞歸的方法解決，還可以用動態(tài)規(guī)劃的方法解決。

在codewars上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡單的優(yōu)化和用另一種方法實(shí)現(xiàn)。

題目

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

以上函數(shù)使用遞歸的方式進(jìn)行斐波那契數(shù)列求和，但效率十分低，很多值會重復(fù)求值。題目要求使用 memoization方案進(jìn)行優(yōu)化。

My Solution

memoization方案在《JavaScript模式》和《JavaScript設(shè)計模式》都有提到。memoization是一種將函數(shù)執(zhí)行結(jié)果用變量緩存起來的方法。當(dāng)函數(shù)進(jìn)行計算之前，先看緩存對象中是否有次計算結(jié)果，如果有，就直接從緩存對象中獲取結(jié)果；如果沒有，就進(jìn)行計算，并將結(jié)果保存到緩存對象中。

let fibonacci = (function() {
  let memory = []
  return function(n) {
      if(memory[n] !== undefined) {
        return memory[n]
    }
    return memory[n] = (n === 0 || n === 1) ? n : fibonacci(n-1) + fibonacci(n-2)
  }
})()

使用閉包實(shí)現(xiàn)的memoization函數(shù)。測試通過之后，突然我有一個小疑問，如果將memory的類型由數(shù)組換成對象，它的運(yùn)算效率會有什么變化？于是，我將memory的類型換成了對象，并寫了一個函數(shù)測試兩種數(shù)據(jù)類型的運(yùn)算效率。

function speed(n) {
    let start = performance.now()
    fibonacci(n)
    let end = performance.now()
    console.log(end - start)
}

所有測試只在Chrome控制臺測試,并且測試次數(shù)不多，結(jié)果不嚴(yán)謹(jǐn)，請多多包涵。

memory類型為數(shù)組時（單位：毫秒）：

speed(500)      // 0.8150000050663948
speed(5000)     // 3.1799999997019768
speed(7500)     // 4.234999991953373
speed(10000)    // 8.390000000596046

memory類型為對象時（單位：毫秒）：

speed(500)      // 0.32499999552965164
speed(5000)     // 1.6499999985098839
speed(7500)     // 2.485000006854534
speed(10000)    // 2.9999999925494194

雖然測試過程不嚴(yán)謹(jǐn)，但還是可以說明一點(diǎn)問題的。memory類型為對象是明顯比類型為數(shù)組時，運(yùn)算速度快很多。~~至于為什么對象操作比數(shù)組操作的速度快，請原諒我水平有限，暫時答不上來。（先挖好坑，以后回來填坑，逃）~~現(xiàn)在回來填坑，例如我們調(diào)用fibonacci(100)，這時候，fibonacci函數(shù)在第一次計算的時候會設(shè)置memory[100]=xxx，此時數(shù)組長度為101，而前面100項(xiàng)會初始化為undefined。正因?yàn)槿绱耍琺emory的類型為數(shù)組的時候比類型是對象的時候慢。（這里藥感謝hsfzxjy的提醒）

Best Solution

別人的解決方案給了我靈感，讓我想出了一個緩存效率高很多的方案。

var fibonacci = (function () {
  var memory = {}
  return function(n) {
    if(n==0 || n == 1) {
      return n
    }
    if(memory[n-2] === undefined) {
      memory[n-2] = fibonacci(n-2)
    }
    if(memory[n-1] === undefined) {
      memory[n-1] = fibonacci(n-1)
    }
    return memory[n] = memory[n-1] + memory[n-2]
  }
})()

測試結(jié)果就不放了（因?yàn)槲野l(fā)現(xiàn)在Chrome控制臺中運(yùn)行測試代碼時，輸出結(jié)果不穩(wěn)定）。不過，這里的緩存效率的確是提高了，前面的方案，一次計算最多緩存一個結(jié)果，而這個方案，一次計算最多緩存三個結(jié)果。從這個方面考慮，運(yùn)算速度理論上是會比前面的方案快的。

動態(tài)規(guī)劃解決方案

斐波那契數(shù)列求和除了可以用遞歸的方法解決，還可以用動態(tài)規(guī)劃的方法解決。由于我是算法渣，對動態(tài)規(guī)劃了解不多，只懂一點(diǎn)點(diǎn)皮毛，所以這里就不解釋動態(tài)規(guī)劃的概念了。（一不小心又挖了一個坑，逃）

直接貼代碼好了：

function fibonacci(n) {
    let n1 = 1,
        n2 = 1,
        sum = 1
    for(let i = 3; i <= n; i += 1) {
        sum = n1 + n2
        n1 = n2
        n2 = sum
    }
    return sum
}

尾遞歸方案

在ES6規(guī)范中，有一個尾調(diào)用優(yōu)化，可以實(shí)現(xiàn)高效的尾遞歸方案。（感謝李引證的提醒）

"use strict"
function fibonacci(n, n1, n2) {
    if(n <= 1) {
        return n2
    }
    return fibonacci(n - 1, n2, n1 + n2)
}

ES6的尾調(diào)用優(yōu)化只在嚴(yán)格模式下開啟，正常模式是無效的。

通項(xiàng)公式方案

斐波那契數(shù)列是有通項(xiàng)公式的，但通項(xiàng)公式中有開方運(yùn)算，在js中會存在誤差，而fib函數(shù)中的Math.round正式解決這一問題的。（感謝公子的指導(dǎo)）

function fibonacci(n){
    var sum = 0
    for(let i = 1; i <= n; i += 1) {
        sum += fib(i)
    }
    return sum

    function fib(n) {
      const SQRT_FIVE = Math.sqrt(5);
      return Math.round(1/SQRT_FIVE * (Math.pow(0.5 + SQRT_FIVE/2, n) - Math.pow(0.5 - SQRT_FIVE/2, n)));
    }
}

結(jié)語

只要注意細(xì)節(jié)，我們的代碼還是有很大的優(yōu)化空間的。有時候，你可能會疑惑，優(yōu)化前后的性能沒有明顯的變化。我認(rèn)為，那是你的應(yīng)用規(guī)模或者數(shù)據(jù)量不夠大而已，當(dāng)它們大到一定程度的時候，優(yōu)化的效果就很明顯了。優(yōu)化還是要堅持的，萬一哪一天我們接手大型應(yīng)用呢？