1. Memoization
Memoization không phải là một từ Tiếng Anh có thể tìm thấy trong từ điển
Oxford. Nó là biến thể của từ gốc Latin "memoradum" với nghĩa "to be remembered"
(được nhớ).
Trong lập trình, memoization là một kỹ thuật tối ưu, nhằm tăng tốc chương trình
bằng cách lưu trữ kết quả của các câu gọi function và trả về các kết quả này
khi function được gọi với cùng input đã gọi.
Hiểu đơn giản, trong python ta có thể implement memoization với dict bằng cách
lưu kết quả gọi function f vào một dict theo dạng:
{
input1: result1, # f(input1)
input2: result2, # f(input2)
inputN: resultN # f(inputN)
}
và sửa lại function để nó lấy result1 nếu input1 có trong dict.
Với bài toán tìm số
Fibonacci,kết quả của câu gọi function sau bằng tổng kết quả của 2 lần gọi function liền trước, dễ thấy ta có thể sử dụng memoization để tránh việc tính lại (đồng thời
tránh luôn cả việc recursive call quá nhiều khiến
vượt quá kích thước củastack )
def fib(n):
if n <= 2: return 1
else:
return fib(n - 1) + fib(n - 2)
In [9]: fib(6)
Out[9]: 8
In [12]: fib(25)
Out[12]: 75025
In [13]: fib(75)
... chờ mãi không thấy
In [13]: %time fib(30)
CPU times: user 244 ms, sys: 1.83 ms, total: 246 ms
Wall time: 245 ms
Out[13]: 832040
Nếu dùng memoization để tối ưu việc tính số
Fibonacci, ta không phải tính lại các giá trị đã tính rồi:
