教程【免費(fèi)下載鏈接】jstipsThis is about useful JS tips!項(xiàng)目地址https://gitcode.com/gh_mirrors/js/jstips點(diǎn)擊查看免費(fèi)下載本文源自 jstips 開(kāi)源倉(cāng)庫(kù)GitHub 加速計(jì)劃 / js / jstips第 29 期 JavaScript 技巧Speed up recursive functions with memoization。文章以斐波那契數(shù)列為切入點(diǎn)剖析樸素遞歸的重復(fù)計(jì)算問(wèn)題并給出閉包緩存與通用 memoize 高階函數(shù)兩種優(yōu)化方案覆蓋 ES5 與 ES6 兩套寫(xiě)法最后推廣到最大公約數(shù)GCD與階乘等典型遞歸場(chǎng)景。讀完本文你將掌握 memoization 的核心原理、通用封裝方法與適用邊界能夠直接為項(xiàng)目中的遞歸計(jì)算函數(shù)提速。問(wèn)題引入20 秒就能寫(xiě)出的低效遞歸斐波那契Fibonacci數(shù)列對(duì)開(kāi)發(fā)者而言再熟悉不過(guò)。原文檔給出了一個(gè) 20 秒內(nèi)就能寫(xiě)出的樸素實(shí)現(xiàn)見(jiàn) _posts/en/javascript/2016-01-29-speed-up-recursive-functions-with-memoization.mdvar fibonacci function(n) { return n 2 ? n : fibonacci(n - 1) fibonacci(n - 2); }這段代碼能正確運(yùn)行但效率極低。原因在于它做了大量重復(fù)計(jì)算以fibonacci(5)為例fibonacci(3)會(huì)被重復(fù)調(diào)用多次——左側(cè)分支算一遍、右側(cè)分支又算一遍且這種重復(fù)隨n增大呈指數(shù)級(jí)擴(kuò)散。整個(gè)調(diào)用過(guò)程會(huì)形成一個(gè)巨大的遞歸調(diào)用樹(shù)同一子問(wèn)題被反復(fù)求解計(jì)算量呈O(2^n)量級(jí)膨脹。關(guān)于遞歸調(diào)用過(guò)程的形態(tài)倉(cāng)庫(kù)第 67 期 Recursion, iteration and tail calls in JS 有更深入的剖析每次函數(shù)調(diào)用都會(huì)保存返回位置與當(dāng)前棧幀信息隨后不斷壓棧、再逐層出棧展開(kāi)。樸素遞歸正是這種遞歸過(guò)程的典型代表——它在計(jì)算完成后仍需回溯棧幀做乘法組合既慢又容易觸碰棧深度上限。方案一閉包 緩存數(shù)組用空間換時(shí)間既然重復(fù)計(jì)算是瓶頸最直接的思路就是把算過(guò)的結(jié)果緩存起來(lái)下次直接取用。原文檔給出了基于 IIFE立即調(diào)用函數(shù)表達(dá)式與閉包的實(shí)現(xiàn)var fibonacci (function() { var cache [0, 1]; // cache the value at the n index return function(n) { if (cache[n] undefined) { for (var i cache.length; i n; i) { cache[i] cache[i - 1] cache[i - 2]; } } return cache[n]; } })();這段代碼的精妙之處在于cache [0, 1]作為閉包內(nèi)的私有狀態(tài)預(yù)先存入數(shù)列的前兩個(gè)基準(zhǔn)值fibonacci(0) 0、fibonacci(1) 1且用注釋明確說(shuō)明緩存第 n 個(gè)索引位置的值外部函數(shù)體只能通過(guò)返回的匿名函數(shù)訪問(wèn)cache緩存對(duì)外部完全隔離不會(huì)被意外污染當(dāng)請(qǐng)求的n尚未計(jì)算cache[n] undefined時(shí)自底向上從已有緩存的末尾逐項(xiàng)遞推補(bǔ)齊cache[i] cache[i - 1] cache[i - 2]直到填滿n一旦cache[n]已存在直接O(1)返回不再遞歸。這種自底向上 順序填表的做法本質(zhì)上就是動(dòng)態(tài)規(guī)劃的迭代形態(tài)每次調(diào)用最多補(bǔ)算n - cache.length個(gè)新項(xiàng)后續(xù)相同或更小的n全部命中緩存整體時(shí)間復(fù)雜度從指數(shù)級(jí)降為線性O(shè)(n)。倉(cāng)庫(kù)的多語(yǔ)言版本中中文簡(jiǎn)體版_posts/zh_CN/javascript/2016-01-29-speed-up-recursive-functions-with-memoization.md與繁體版_posts/zh_TW/javascript/2016-01-29-speed-up-recursive-functions-with-memoization.md保留了完全相同的算法骨架繁體版進(jìn)一步將var升級(jí)為const/let并改用self(n-1) self(n-2)的遞歸填表方式——這說(shuō)明該緩存思路在不同語(yǔ)言變體中被一致認(rèn)可只是實(shí)現(xiàn)細(xì)節(jié)各有取舍。方案二通用 memoize 高階函數(shù)針對(duì)斐波那契單獨(dú)寫(xiě)緩存雖然直觀但每個(gè)遞歸函數(shù)都要手寫(xiě)一遍閉包太繁瑣。原文檔隨即給出了更優(yōu)雅的抽象定義一個(gè)高階函數(shù)memoize它接收任意函數(shù)作為參數(shù)返回該函數(shù)的帶記憶版本。ES5 版本var memoize function(func) { var cache {}; return function() { var key JSON.stringify(Array.prototype.slice.call(arguments)); return key in cache ? cache[key] : (cache[key] func.apply(this, arguments)); } } fibonacci memoize(fibonacci);逐行拆解其工作原理cache {}是閉包內(nèi)的鍵值緩存鍵為參數(shù)序列化后的字符串值為對(duì)應(yīng)計(jì)算結(jié)果Array.prototype.slice.call(arguments)把類(lèi)數(shù)組對(duì)象arguments轉(zhuǎn)換為真正的數(shù)組從而能調(diào)用數(shù)組方法JSON.stringify(...)將參數(shù)列表序列化為唯一字符串鍵——這是本實(shí)現(xiàn)的關(guān)鍵不同參數(shù)組合對(duì)應(yīng)不同緩存鍵天然支持多參數(shù)函數(shù)key in cache ? cache[key] : (cache[key] func.apply(this, arguments))是短路求值的經(jīng)典寫(xiě)法鍵已存在則直接返回緩存值否則調(diào)用原函數(shù)func計(jì)算并寫(xiě)入緩存后返回通過(guò)func.apply(this, arguments)保留調(diào)用時(shí)的this上下文與全部實(shí)參使被包裝函數(shù)的行為不被破壞。最后一行fibonacci memoize(fibonacci)用帶記憶的版本覆蓋原函數(shù)對(duì)外調(diào)用方式完全不變即插即用。JSON.stringify在這里的作用值得單獨(dú)說(shuō)明——倉(cāng)庫(kù)第 40 期 Using JSON.Stringify 詳細(xì)講解了它的高級(jí)用法選擇性序列化屬性、replacer 函數(shù)、縮進(jìn)格式化。memoize 正是利用了它把任意 JS 值變成字符串的能力來(lái)生成緩存鍵可視為該技巧在緩存場(chǎng)景的實(shí)戰(zhàn)應(yīng)用。需要注意的是當(dāng)參數(shù)包含對(duì)象時(shí)序列化結(jié)果是按內(nèi)容生成的字符串因此內(nèi)容相同的對(duì)象會(huì)命中同一緩存鍵若參數(shù)是函數(shù)、undefined或存在循環(huán)引用JSON.stringify會(huì)失效這是該實(shí)現(xiàn)的主要局限詳見(jiàn)后文適用邊界。ES6 版本原文檔接著給出更簡(jiǎn)潔的 ES6 版本利用剩余參數(shù)rest parameters與箭頭函數(shù)var memoize function(func) { const cache {}; return (...args) { const key JSON.stringify(args); return key in cache ? cache[key] : (cache[key] func(...args)); } } fibonacci memoize(fibonacci);與 ES5 版相比變化一目了然維度ES5 版本ES6 版本參數(shù)收集Array.prototype.slice.call(arguments)...args剩余參數(shù)直接得到真數(shù)組鍵生成JSON.stringify(數(shù)組)JSON.stringify(args)省去顯式轉(zhuǎn)換調(diào)用原函數(shù)func.apply(this, arguments)func(...args)展開(kāi)參數(shù)閉包變量聲明var cache {}const cache {}ES6 版去掉了arguments與apply的樣板代碼可讀性顯著提升。值得注意的是倉(cāng)庫(kù)的中文簡(jiǎn)體版_posts/zh_CN/javascript/2016-01-29-speed-up-recursive-functions-with-memoization.md與西班牙語(yǔ)版_posts/es_ES/javascript/2016-01-29-speed-up-recursive-functions-with-memoization.md在鍵生成上采用了另一種等價(jià)寫(xiě)法[...args].toString()它借助展開(kāi)運(yùn)算符將剩余參數(shù)轉(zhuǎn)為數(shù)組再調(diào)用toString()效果與JSON.stringify(args)類(lèi)似對(duì)數(shù)字、字符串等原始類(lèi)型參數(shù)完全一致屬于同一思路的變體讀者可對(duì)比體會(huì)。實(shí)戰(zhàn)推廣memoize 的更多應(yīng)用場(chǎng)景原文檔明確指出memoize()可以用于很多其他場(chǎng)景并給出了兩個(gè)經(jīng)典示例。最大公約數(shù) GCDvar gcd memoize(function(a, b) { var t; if (a b) t b, b a, a t; while (b ! 0) t b, b a % b, a t; return a; }); gcd(27, 183); // 3這里先通過(guò)交換確保a b再用輾轉(zhuǎn)相除法歐幾里得算法求最大公約數(shù)。gcd(27, 183)的正確結(jié)果是3。memoize 包裝后當(dāng)程序中反復(fù)以相同參數(shù)對(duì)調(diào)用 GCD 時(shí)例如循環(huán)內(nèi)對(duì)固定組合求公約數(shù)可直接命中緩存。多參數(shù)場(chǎng)景正好驗(yàn)證了 memoize 用序列化參數(shù)組合作為緩存鍵的設(shè)計(jì)是必要的——單個(gè)參數(shù)的緩存無(wú)法區(qū)分不同參數(shù)對(duì)。階乘計(jì)算var factorial memoize(function(n) { return (n 1) ? 1 : n * factorial(n - 1); }) factorial(5); // 120階乘是教科書(shū)級(jí)的遞歸案例。注意這里的閉包技巧factorial已經(jīng)被重新賦值成了 memoize 包裝后的函數(shù)因此遞歸調(diào)用factorial(n - 1)實(shí)際調(diào)用的是帶緩存的版本每一層的中間結(jié)果都會(huì)被記錄下來(lái)。調(diào)用factorial(5)返回120后再調(diào)用factorial(10)時(shí)5!及以下的結(jié)果全部命中緩存只需補(bǔ)算6!到10!。倉(cāng)庫(kù)第 67 期 Recursion, iteration and tail calls in JS 對(duì)階乘遞歸的兩種寫(xiě)法樸素遞歸 vs 尾遞歸攜帶累加參數(shù)做了完整的執(zhí)行過(guò)程推演并討論了 ES6 尾調(diào)用優(yōu)化TCO的現(xiàn)狀。與 memoization 相比兩者解決的是不同維度的問(wèn)題尾調(diào)用優(yōu)化減少調(diào)用棧深度memoization 消除重復(fù)子計(jì)算——對(duì)于同一參數(shù)會(huì)被反復(fù)求解的遞歸memoization 的收益更為直接。memoization 的適用邊界與注意事項(xiàng)結(jié)合原文檔實(shí)現(xiàn)與倉(cāng)庫(kù)其他 tip可以總結(jié)出使用 memoization 時(shí)值得注意的邊界緩存鍵的序列化局限JSON.stringify無(wú)法正確處理function、undefined、Symbol以及循環(huán)引用對(duì)象遇到這些參數(shù)時(shí)鍵生成會(huì)失敗或產(chǎn)生歧義如undefined與缺失參數(shù)可能序列化出相同鍵。若函數(shù)參數(shù)包含這類(lèi)值需改用自定義鍵函數(shù)對(duì)象參數(shù)的語(yǔ)義JSON.stringify按對(duì)象內(nèi)容生成鍵兩個(gè)內(nèi)容相同但引用不同的對(duì)象會(huì)命中同一緩存——多數(shù)情況下符合預(yù)期但若函數(shù)依賴(lài)對(duì)象身份identity或內(nèi)部狀態(tài)則可能得到錯(cuò)誤結(jié)果內(nèi)存占用緩存隨調(diào)用參數(shù)組合的增長(zhǎng)而無(wú)限膨脹屬于典型的空間換時(shí)間。對(duì)參數(shù)組合數(shù)量極大或參數(shù)為大型對(duì)象的高頻函數(shù)需要引入緩存淘汰LRU或容量上限策略純函數(shù)前提memoization 只對(duì)確定性純函數(shù)安全。如果原函數(shù)依賴(lài)外部可變狀態(tài)、當(dāng)前時(shí)間、隨機(jī)數(shù)或產(chǎn)生副作用緩存結(jié)果將失去意義——這是使用 memoize 之前必須先確認(rèn)的前提t(yī)his的處理ES5 版本通過(guò)func.apply(this, arguments)保留了this綁定因此可用于對(duì)象方法ES6 箭頭函數(shù)版本中箭頭函數(shù)不綁定自己的this若被包裝函數(shù)依賴(lài)動(dòng)態(tài)this需注意上下文差異與函數(shù)式風(fēng)格的關(guān)系倉(cāng)庫(kù)中 _posts/en/javascript/2017-06-14-immutable-structures-and-cloning.md 討論了不可變結(jié)構(gòu)與克隆的話題——memoization 在函數(shù)式編程中常與引用透明引用透明即相同輸入永遠(yuǎn)產(chǎn)生相同輸出配合使用純函數(shù)是安全記憶化的前提這一原則同樣適用于本 tip。小結(jié)本 tip 以斐波那契為引子完整覆蓋了 memoization 的三層遞進(jìn)樸素遞歸暴露重復(fù)計(jì)算問(wèn)題 → 閉包緩存數(shù)組給出專(zhuān)用解 → 通用memoize高階函數(shù)給出可復(fù)用抽象ES5/ES6 雙版本并以 GCD、階乘驗(yàn)證其通用性。其核心要點(diǎn)可濃縮為樸素遞歸因重復(fù)求解同一子問(wèn)題而低效時(shí)間復(fù)雜度可呈指數(shù)增長(zhǎng)用閉包持有緩存數(shù)組或?qū)ο蠹纯砂岩阉憬Y(jié)果記憶下來(lái)將指數(shù)級(jí)降為線性memoize(func)通過(guò)參數(shù)序列化 → 鍵值緩存 → 短路返回三步實(shí)現(xiàn)任意函數(shù)的記憶化包裝多參數(shù)支持來(lái)自JSON.stringify的鍵生成memoization 僅適用于純函數(shù)使用前需權(quán)衡序列化局限與內(nèi)存占用。想深入了解相關(guān)主題的讀者可繼續(xù)閱讀倉(cāng)庫(kù)中的關(guān)聯(lián) tipRecursion, iteration and tail calls in JS遞歸過(guò)程與尾調(diào)用優(yōu)化、Using JSON.Stringify緩存鍵生成依賴(lài)的序列化機(jī)制以及 Immutable structures and cloning純函數(shù)與狀態(tài)管理的關(guān)系。本 tip 的完整源文件見(jiàn) _posts/en/javascript/2016-01-29-speed-up-recursive-functions-with-memoization.md倉(cāng)庫(kù)還提供了簡(jiǎn)體中文、繁體中文與西班牙語(yǔ)的對(duì)照版本便于多語(yǔ)言閱讀。贊分享教程【免費(fèi)下載鏈接】jstipsThis is about useful JS tips!項(xiàng)目地址https://gitcode.com/gh_mirrors/js/jstips點(diǎn)擊查看免費(fèi)下載相關(guān)推薦用 JavaScript 遞歸實(shí)戰(zhàn)斐波那契數(shù)列與歸并排序Fibonacci Merge Sort用 JavaScript 遞歸實(shí)戰(zhàn)斐波那契數(shù)列與歸并排序Fibonacci Merge Sort 導(dǎo)讀 本篇實(shí)戰(zhàn)項(xiàng)目來(lái)自 curriculum htt文檔教程教育Floccus跨瀏覽器書(shū)簽同步完整操作手冊(cè)打造你的私有書(shū)簽云Floccus跨瀏覽器書(shū)簽同步完整操作手冊(cè)打造你的私有書(shū)簽云 在當(dāng)今多設(shè)備、多瀏覽器的數(shù)字生活中書(shū)簽同步已成為現(xiàn)代互聯(lián)網(wǎng)用戶(hù)的核心需求。Floccus作為一前端移動(dòng)開(kāi)發(fā)數(shù)據(jù)同步Python遞歸算法優(yōu)化gh_mirrors/da/data-science-interviews項(xiàng)目階乘與斐波那契尾遞歸實(shí)現(xiàn)Python遞歸算法優(yōu)化gh_mirrors/da/data science interviews項(xiàng)目階乘與斐波那契尾遞歸實(shí)現(xiàn) 遞歸是Python編程中解決復(fù)文檔知識(shí)庫(kù)數(shù)據(jù)科學(xué)教程創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考