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