資訊專欄INFORMATION COLUMN
摘要：在上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡(jiǎn)單的優(yōu)化和用另一種方法實(shí)現(xiàn)。動(dòng)態(tài)規(guī)劃解決方案斐波那契數(shù)列求和除了可以用遞歸的方法解決，還可以用動(dòng)態(tài)規(guī)劃的方法解決。
在codewars上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡(jiǎn)單的優(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ù)列求和，但效率十分低，很多值會(huì)重復(fù)求值。題目要求使用 memoization方案進(jìn)行優(yōu)化。
My Solutionmemoization方案在《JavaScript模式》和《JavaScript設(shè)計(jì)模式》都有提到。memoization是一種將函數(shù)執(zhí)行結(jié)果用變量緩存起來(lái)的方法。當(dāng)函數(shù)進(jìn)行計(jì)算之前，先看緩存對(duì)象中是否有次計(jì)算結(jié)果，如果有，就直接從緩存對(duì)象中獲取結(jié)果；如果沒(méi)有，就進(jìn)行計(jì)算，并將結(jié)果保存到緩存對(duì)象中。
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ù)。測(cè)試通過(guò)之后，突然我有一個(gè)小疑問(wèn)，如果將memory的類型由數(shù)組換成對(duì)象，它的運(yùn)算效率會(huì)有什么變化？于是，我將memory的類型換成了對(duì)象，并寫(xiě)了一個(gè)函數(shù)測(cè)試兩種數(shù)據(jù)類型的運(yùn)算效率。
function speed(n) {
let start = performance.now()
fibonacci(n)
let end = performance.now()
console.log(end - start)
}
所有測(cè)試只在Chrome控制臺(tái)測(cè)試,并且測(cè)試次數(shù)不多，結(jié)果不嚴(yán)謹(jǐn)，請(qǐng)多多包涵。
memory類型為數(shù)組時(shí)（單位：毫秒）：
speed(500) // 0.8150000050663948 speed(5000) // 3.1799999997019768 speed(7500) // 4.234999991953373 speed(10000) // 8.390000000596046
memory類型為對(duì)象時(shí)（單位：毫秒）：
speed(500) // 0.32499999552965164 speed(5000) // 1.6499999985098839 speed(7500) // 2.485000006854534 speed(10000) // 2.9999999925494194
雖然測(cè)試過(guò)程不嚴(yán)謹(jǐn)，但還是可以說(shuō)明一點(diǎn)問(wèn)題的。memory類型為對(duì)象是明顯比類型為數(shù)組時(shí)，運(yùn)算速度快很多。至于為什么對(duì)象操作比數(shù)組操作的速度快，請(qǐng)?jiān)徫宜接邢?，暫時(shí)答不上來(lái)。（先挖好坑，以后回來(lái)填坑，逃）現(xiàn)在回來(lái)填坑，例如我們調(diào)用fibonacci(100)，這時(shí)候，fibonacci函數(shù)在第一次計(jì)算的時(shí)候會(huì)設(shè)置memory[100]=xxx，此時(shí)數(shù)組長(zhǎng)度為101，而前面100項(xiàng)會(huì)初始化為undefined。正因?yàn)槿绱耍琺emory的類型為數(shù)組的時(shí)候比類型是對(duì)象的時(shí)候慢。（這里藥感謝hsfzxjy的提醒）
別人的解決方案給了我靈感，讓我想出了一個(gè)緩存效率高很多的方案。
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]
}
})()
測(cè)試結(jié)果就不放了（因?yàn)槲野l(fā)現(xiàn)在Chrome控制臺(tái)中運(yùn)行測(cè)試代碼時(shí)，輸出結(jié)果不穩(wěn)定）。不過(guò)，這里的緩存效率的確是提高了，前面的方案，一次計(jì)算最多緩存一個(gè)結(jié)果，而這個(gè)方案，一次計(jì)算最多緩存三個(gè)結(jié)果。從這個(gè)方面考慮，運(yùn)算速度理論上是會(huì)比前面的方案快的。
動(dòng)態(tài)規(guī)劃解決方案斐波那契數(shù)列求和除了可以用遞歸的方法解決，還可以用動(dòng)態(tài)規(guī)劃的方法解決。由于我是算法渣，對(duì)動(dòng)態(tài)規(guī)劃了解不多，只懂一點(diǎn)點(diǎn)皮毛，所以這里就不解釋動(dòng)態(tài)規(guī)劃的概念了。（一不小心又挖了一個(gè)坑，逃）
直接貼代碼好了：
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ī)范中，有一個(gè)尾調(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)
}
通項(xiàng)公式方案ES6的尾調(diào)用優(yōu)化只在嚴(yán)格模式下開(kāi)啟，正常模式是無(wú)效的。
斐波那契數(shù)列是有通項(xiàng)公式的，但通項(xiàng)公式中有開(kāi)方運(yùn)算，在js中會(huì)存在誤差，而fib函數(shù)中的Math.round正式解決這一問(wèn)題的。（感謝公子的指導(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é)語(yǔ)
只要注意細(xì)節(jié)，我們的代碼還是有很大的優(yōu)化空間的。有時(shí)候，你可能會(huì)疑惑，優(yōu)化前后的性能沒(méi)有明顯的變化。我認(rèn)為，那是你的應(yīng)用規(guī)?；蛘邤?shù)據(jù)量不夠大而已，當(dāng)它們大到一定程度的時(shí)候，優(yōu)化的效果就很明顯了。優(yōu)化還是要堅(jiān)持的，萬(wàn)一哪一天我們接手大型應(yīng)用呢？
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/80652.html
摘要：根據(jù)該規(guī)則，返回第個(gè)斐波那契數(shù)。尾遞歸函數(shù)調(diào)用自身，稱為遞歸。一個(gè)前端眼中的斐波那契數(shù)列解斐波那契數(shù)列的實(shí)用解法調(diào)用棧尾遞歸和手動(dòng)優(yōu)化尾調(diào)用優(yōu)化譯我從用寫(xiě)斐波那契生成器中學(xué)到的令人驚訝的件事 斐波那契數(shù)列是以下一系列數(shù)字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數(shù)字 0 和 1 ...
摘要：前言前幾天面試被問(wèn)到了斐波那契數(shù)列的實(shí)現(xiàn)以及優(yōu)化的問(wèn)題，當(dāng)時(shí)現(xiàn)場(chǎng)卡了挺久的，現(xiàn)在進(jìn)行一下總結(jié)使用實(shí)現(xiàn)。題目介紹斐波那契數(shù)列又被稱為黃金分割數(shù)列，指的是這樣的一個(gè)數(shù)列，它有如下遞推的方法定義是正整數(shù)，請(qǐng)使用實(shí)現(xiàn)斐波那契函數(shù)。 前言 前幾天面試被問(wèn)到了斐波那契數(shù)列的實(shí)現(xiàn)以及優(yōu)化的問(wèn)題，當(dāng)時(shí)現(xiàn)場(chǎng)卡了挺久的，現(xiàn)在進(jìn)行一下總結(jié)（使用js實(shí)現(xiàn)）。 題目介紹 ??斐波那契數(shù)列又被稱為黃金分割數(shù)列，指...
摘要：大名鼎鼎的斐波那契數(shù)列，，，，，，，，使用數(shù)學(xué)歸納法可以看出其規(guī)律為。對(duì)于斐波那契數(shù)列的求解，有自頂向下的記憶化搜索遞歸和自下向上的迭代法，他們都使用了動(dòng)態(tài)規(guī)劃的思想。 大名鼎鼎的斐波那契數(shù)列：0，1，1，2，3，5，8，13，21...使用數(shù)學(xué)歸納法可以看出其規(guī)律為：f(n) = f(n-1) + f(n-2)。 遞歸 下面首先直接使用遞歸（JavaScript實(shí)現(xiàn)）來(lái)求解第 n ...
摘要：遞歸概念遞歸是一種針對(duì)簡(jiǎn)單循環(huán)難以編程實(shí)現(xiàn)的問(wèn)題，通過(guò)函數(shù)調(diào)用自身，提供優(yōu)雅解決方案的技術(shù)。擁有基礎(chǔ)情況或終止條件來(lái)停止遞歸。這個(gè)稱之為遞歸調(diào)用。為了避免重新創(chuàng)建字符串，使用遞歸輔助方法來(lái)進(jìn)行改良。 遞歸概念 遞歸是一種針對(duì)簡(jiǎn)單循環(huán)難以編程實(shí)現(xiàn)的問(wèn)題，通過(guò)函數(shù)調(diào)用自身，提供優(yōu)雅解決方案的技術(shù)。 遞歸都具有以下三個(gè)要點(diǎn)： 使用 if-else 或 switch 語(yǔ)句來(lái)引導(dǎo)不同的情況。 ...
摘要：那其實(shí)這個(gè)問(wèn)題還可以換個(gè)問(wèn)法實(shí)現(xiàn)一個(gè)函數(shù)，輸入一個(gè)數(shù)字能返回斐波那契數(shù)列的第個(gè)值。文章預(yù)告更多的前端面試分享我都會(huì)第一時(shí)間更新在我的公眾號(hào)閏土大叔里面，歡迎關(guān)注 面試攢經(jīng)驗(yàn)，lets go！ 值此高考來(lái)臨之際，閑不住的我又雙叒叕出發(fā)去面試攢經(jīng)驗(yàn)了，去了公司交待一番流程后，面試官甩給了我一張A4紙，上面寫(xiě)著一道js算法筆試題（一開(kāi)始我并不知道這是在考察js算法），上面寫(xiě)著1、1、2、3、...
閱讀 3315·2021-09-23 11:55
閱讀 2674·2021-09-13 10:33
閱讀 1693·2019-08-30 15:54
閱讀 3118·2019-08-30 15:54
閱讀 2384·2019-08-30 10:59
閱讀 2393·2019-08-29 17:08
閱讀 1823·2019-08-29 13:16
閱讀 3611·2019-08-26 12:25
