Memoize 是一種函式型程式的設計技巧, 基本上它的意思就是在函式中記錄計算的結果, 下一次再遇到同一個輸入參數時, 就可以把先前的計算結果直接取出, 不用再算一次。
雖然在本文中將使用 JavaScript 作為範例, 但 JavaScript 並不是唯一可以使用 memoize 的程式語言。例如 Python 也可以做到類似的功能, 如下例:
from functools import cache
@cache
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(5)) # 120
print(factorial(5)) # 120 (從上次的計算結果中取出, 不必重新計算)與 Python 不同, JavaScript 不必特別載入什麼模組, 而是利用它的 function 也同時是 object 的特性來做到相同的事情。這是什麼意思呢? 我們可以來看以下這個例子:
在上例中, fun 是定義為 function, 並不是 object, 但是它的行為卻和 object 一樣。所以你可以很簡單地直接指定 attrubute (也就是 repos) 給它。但是一個定義為 object 的變數, 我們可以看到它的輸出是略有不同的:
在上例中, obj 是一個普通的 obj, 我們使用正常的方法加入 repos 這個 attribute, 在 console 中列出這個變數時, 其下的 attribute 可以被條列出來。但相對地 fun 卻不會條列出 repos 這個 attribute。所以對外界而言, 除非我們本來就知道它有 repos 這個 attribute, 否則根本無法去取用它。我們只能透過 function.prototype 以得知有這個 attribute (如下圖)。
如果你從未寫過 memoize, 你可能會認為這種看來似乎違反直覺的方法太過 tricky, 可能觸犯到基本的程式寫作原則。事實上 , 有人認為 memoize 寫法並未違反 SOLID, 但也有人認為 memoize 寫法違反了 OCP 原則 (Open/Closed Principle), 因為它會修改原始函數的行為。其輸入和輸出會被儲存在 cache 中, 導致影響了原始函數的行為。
我個人的看法比較偏向第一種見解, 也就是它並未違反 OCP。尤其是依本文中的範例, 它的功能單一而且封閉性強, 並不會造成維護上的困難。
不管如何, 不能否認的是, 它的確是一種有趣的寫法。現在我就來示範如何利用 JavaScript 中 funcion 即 object 的這個特性去實作 memoize。
在以下的程式中, 輸入參數 value 會被計算是否為質數。如果不是則略過, 如果是則存進 isPrime.answers 裡面。如果相同的參數已經被輸入過, 程式會從 answers 中直接取出結果, 不會再重算一次。
// 程式一
function isPrime(value) {
if (value > 2 && value % 2 == 0) // Rule out all even numbers
return false;
let check = value > 1; // 1 is not prime number
if (!isPrime.repos) { // Create the "answers" object
isPrime.repos= {};
}
if (isPrime.repos[value] !== undefined) { // If value exists in answers, return true
return isPrime.repos[value];
}
for (var i = 2; i < value/2; i++) { // Check if any known prime number can devide value, if not, it is a prime number
if (value % i === 0) {
check = false;
break;
}
}
return check? isPrime.repos[value] = check : false;
}
如果你覺得這個程式很難懂的話, 你只要記得兩件事就好: 1. 如果輸入參數 value 已經被計算過, 它就從 isPrime.repos 直接取回結果即可; 2. 如果輸入值 value 尚未輸入過, 就從頭計算它是否能被 repos 中所有值整除。如果都不能被整除 (意思它就是質數), 就存進 repos 裡。
另外, 10000 以下的質數其實有 1229 個而不是 1228 個。這是因為我把所有的偶數都排除了, 所以雖然 2 也是質數, 但在程式一中並未列入 repos 物件裡。
請注意, 程式一所使用的邏輯並不是最好的。問題出在程式中的 for 迴圈那一段。照理說我們不需要把所有奇數的值帶進去算, 而是只需計算原本已存在 repos 物件裡的值就好。不過本文的重點並不在計算質數, 而是示範 memoize 函式。如果你真的有興趣的話, 可以自行改善這個程式。
為了驗證這個程式, 我寫了一個範例程式如下:
// 程式二
var timerTag = 0;
function enumeratePrimes(start, end) {
if (end <= start) {
console.warn('Parameter(s) is invalid.');
return;
}
console.log('Scanning', end-start, "numbers...");;
let iterated = 0;
if (start % 2 == 0) start++; // Discard the first even number
console.time(timerTag);
for (let i = start; i < end; i+=2) {
iterated++;
isPrime(i);
}
console.timeLog(timerTag++); // Measure durance
let itemsFound = Object.keys(isPrime.repos);
console.log(itemsFound);
console.log("Found", itemsFound.length, "items within", iterated, "iterations. (", itemsFound.length/(end-start)*100, "%)");
}由於本文的重點並不是程式二, 所以其中邏輯我就不解釋了。基本上 enumeratePrimes 函式需要兩個參數, 意思是算出從 start 到 end 範圍中所有的質數。所以如果我們執行 enumeratePrimes(0,10000) 就是指算出 0 到 10000 中間的所有質數。
在下圖中, 我們計算了兩次:
一模一樣的指令重複執行後, 二者的消耗時間差異相當大。這是當然的, 因為第二次執行時事實上根本沒有任何計算, 而是把 isPrime.repos 中已經有的值拿出來而已。當然會省下很多計算成本。而這就是 memoize 程式最重要的目的。
不過, 還是請留意, 程式二只是一個範例程式。基本上它只考慮「往後算」的情境, 並未考慮「往前算」的情境。所以如果你已經算過 enumeratePrimes(0,10000), 那麼如果你又去計算 enumeratePrimes(0,100) 或者任何在 10000 以下的範圍, 得出來的結果一定是錯的。你之後必須計算 10000 以後的值, 才有意義。