Memoization 通常翻譯成 記憶化，或是工程師耳熟能詳的快取(Cache)。
來看看 Wiki 怎麼說：
在計算機科學中，記憶化是一種提高程序運行速度的優化技術。通過儲存大計算量函數的返回值，當這個結果再次被需要時將其從緩存提取，而不用再次計算來節省計算時間。 記憶化是一種典型的時間存儲平衡方案。
所以 Memoization 是用來提高運行速度，使用時機是大計算量函數，如果計算量不大，使用 Memoization 就沒什麼意義了。
Memoization 還有個前提：
相同的輸入時，回傳暫存值。
如果你的函數給予相同的input，卻會出現不同的結果，那也不適合用memorization。例如亂數，或需要用到當下時間。
在Rails 專案中，可能會看到像這樣的code
class User < ApplicationRecord
def all_users
@users ||= User.all
end
end
因為Query出所有使用者實在很耗資源，所以透過@users 把計算結果 Cache 起來，並使用||= (conditional assignment) 讓第二次呼叫all_users 不用再呼叫DB。
從第一個簡單範例可以了解到 Memoization 的好處，因為 User.all如果都沒有資料，@users會是空 array。
但如果昂貴的計算(ex. 下面的 expensive_calculation) 結果是 nil or false，||= 特性會把昂貴的計算再計算一遍，就失去Memoization 的作用了。
def wanna_cache_result
@result ||= expensive_calculation
end
def expensive_calculation
...
end
這時使用||=還不夠，需要用到 #defined? 這個operator。
改寫 wanna_cache_result
def wanna_cache_result
return @result if defined?(@result)
@result ||= expensive_calculatio
end
ps. #defined?(attr) 只要參數是沒定義過的，就回傳nil。如果定義過，會回傳參數的種類，像這裏 @result 如果被指定過值
defined?(@undefined_result)
# => nil
defined?(@result)
# => "instance-variable"
如果不用 #defined?，就多用個實體來存狀態吧
def wanna_cache_result
return @result if @has_checked
@has_checked = true
@result ||= expensive_calculatio
end
我們公司面試題很喜歡考費波納西數列，通常我們會這樣解
def fibonacci(n)
if n == 1 || n == 0
1
else
fibonacci(n - 1) + fibonacci(n - 2)
end
end
但是 fibonacci(n) 被呼叫的次數隨著n的增加會呈現指數級增長
以下紀錄被呼叫次數
def fibonacci(n)
@times += 1
if n < 2
1
else
fibonacci(n - 1) + fibonacci(n - 2)
end
end
def count_fibonacci(n)
@times = 0
@cache = {}
result = fibonacci(n)
p "參數為#{n}時，被呼叫#{@times}次，結果是#{result}"
@times = 0
end
count_fibonacci(1) # "參數為1時，被呼叫1次，結果是1"
count_fibonacci(2) # "參數為2時，被呼叫3次，結果是2"
count_fibonacci(3) # "參數為3時，被呼叫5次，結果是3"
count_fibonacci(5) # "參數為5時，被呼叫15次，結果是8"
count_fibonacci(7) # "參數為7時，被呼叫41次，結果是21"
count_fibonacci(10) #"參數為10時，被呼叫177次，結果是89"
count_fibonacci(20) #"參數為20時，被呼叫21891次，結果是10946"
計算第10個數字需要呼叫177次，計算第20個數字暴增到21891次。嚇到吃手手的數字
使用 Memoization 能夠做到大幅減少 fibonacci被呼叫的次數。
def fibonacci(n)
@times += 1
if @cache[n]
@cache[n]
else
result =
if n < 2
1
else
fibonacci(n - 1) + fibonacci(n - 2)
end
@cache[n] = result
end
end
def count_fibonacci(n)
@times = 0
@cache = {}
result = fibonacci(n)
p "參數為#{n}時，被呼叫#{@times}次，結果是#{result}"
@times = 0
end
count_fibonacci(1) # "參數為1時，被呼叫1次，結果是1"
count_fibonacci(2) # "參數為2時，被呼叫3次，結果是2"
count_fibonacci(3) # "參數為3時，被呼叫5次，結果是3"
count_fibonacci(5) # "參數為5時，被呼叫9次，結果是8"
count_fibonacci(7) # "參數為7時，被呼叫13次，結果是21"
count_fibonacci(10) # "參數為10時，被呼叫19次，結果是89"
count_fibonacci(20) # "參數為20時，被呼叫39次，結果是10946"
計算第20個數字只要39次，大幅減少呼叫方法的次數
使用benchmark來看執行時間
require 'benchmark'
def fibonacci_with_cache(n)
if @cache[n]
@cache[n]
else
result =
if n < 2
1
else
fibonacci_with_cache(n - 1) + fibonacci_with_cache(n - 2)
end
@cache[n] = result
end
end
def fibonacci(n)
if n < 2
1
else
fibonacci(n - 1) + fibonacci(n - 2)
end
end
def count_fibonacci_with_cache(n)
@cache = {}
fibonacci_with_cache(n)
end
Benchmark.bm do |x|
x.report('without_cache') do
fibonacci(10)
fibonacci(20)
end
x.report('with_cache') do
count_fibonacci_with_cache(10)
count_fibonacci_with_cache(20)
end
end
user system total real
without_cache 0.000991 0.000002 0.000993 ( 0.000991)
with_cache 0.000019 0.000000 0.000019 ( 0.000018)
四個數字依序為：
時間單位為秒
可以看到使用 Memoization 能夠做到大幅減少 fibonacci被呼叫的時間。
這裡要討論的是，是否該在最上層方法做cache。我覺得答案沒有一定，還是要看哪裡最吃系統資源，不過通常在相對底層做比較好。
舉例來說，如果今天收益是收入減去成本
# 雖然下次取得收益會很快，但計算收入跟成本又要再重算一次。
def profit
@profit ||= (revenue - costs)
end
def revenue
Sales.all.sum(:amount)
end
def costs
Cost.all.sum(:amount)
end
改在 #revenue 跟 #costs 做cache
# 減法不會耗去太多時間，又可以讓 revenue跟 costs 有cache效果
def profit
revenue - costs
end
def revenue
@revenue ||= Sales.all.sum(:amount)
end
def costs
@costs ||= Cost.all.sum(:amount)
end
看到這裡或許會想，既然Memoization這麼有效，那我把每個方法都用上它就好啦。可惜理想很豐滿，現實很骨感，如果你這麼做，Garbage Collection無法順利運作，系統可用記憶體越來越少，而越來越慢。
所以用Memozation之前，先找出最需要的地方就可以了。另外cache也是有時效性，還好我們都是cache在實體變數(instance variables)，對Rails來說，每次request都是產生不同的實體，通常不會有cache內容過期的問題。但如果有些東西很多request都會用到，就可以考慮存在類別實體變數(class variables)，但是資料的正確跟時效性就要考慮。
iThome鐵人賽
看影片追技術