Memoization là gì? LRU cache là gì?

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:

fib_memo = {}
def fib(n):
    if n <= 2: return 1
    else:
        if n not in fib_memo:
            fib_memo[n] = fib(n - 1) + fib(n - 2)
        return fib_memo[n]

In [23]: fib(75)
Out[23]: 2111485077978050

In [24]: print(fib_memo)
{3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233,
14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181, 20: 6765, 21: 10946,
22: 17711, 23: 28657, 24: 46368, 25: 75025, 26: 121393, 27: 196418, 28: 317811,
29: 514229, 30: 832040, 31: 1346269, 32: 2178309, 33: 3524578, 34: 5702887, 35:
9227465, 36: 14930352, 37: 24157817, 38: 39088169, 39: 63245986, 40: 102334155,
41: 165580141, 42: 267914296, 43: 433494437, 44: 701408733, 45: 1134903170, 46:
1836311903, 47: 2971215073, 48: 4807526976, 49: 7778742049, 50: 12586269025,
51: 20365011074, 52: 32951280099, 53: 53316291173, 54: 86267571272, 55:
139583862445, 56: 225851433717, 57: 365435296162, 58: 591286729879, 59:
956722026041, 60: 1548008755920, 61: 2504730781961, 62: 4052739537881, 63:
6557470319842, 64: 10610209857723, 65: 17167680177565, 66: 27777890035288, 67:
44945570212853, 68: 72723460248141, 69: 117669030460994, 70: 190392490709135,
71: 308061521170129, 72: 498454011879264, 73: 806515533049393, 74:
1304969544928657, 75: 2111485077978050}

Và kết quả trả về trong chớp mắt.

In [25]: %time fib(75)
CPU times: user 104 µs, sys: 107 µs, total: 211 µs
Wall time: 168 µs
Out[25]: 2111485077978050

2. LRU cache

LRU (least recently used) cache (đọc là [/kaʃ/])là một trong các thuật toán cache phổ biến.
Cache được dùng để lưu trữ các kết quả tính toán vào một nơi và khi cần tính
lại thì lấy trực tiếp kết quả đã lưu ra thay vì thực hiện tính.
Cache thường có kích thước nhất định và khi đầy, cần bỏ đi một số kết quả đã
tồn tại trong cache. Việc kết quả nào sẽ bị bỏ đi phân loại các thuật toán
cache này thành:

- LRU (Least Recently Used): bỏ đi các item trong cache ít được dùng gần đây nhất.
- MRU (Most Recently Used): bỏ đi các item trong cache được dùng gần đây nhất.
- ... https://en.wikipedia.org/wiki/Cache_algorithms#Examples

Việc sử dụng kỹ thuật memoization để tối ưu các quá trình tính toán như vậy là
chuyện thường ở huyện, vậy nên từ Python 3.2, trong standard library
``functools`` đã có sẵn function ``lru_cache`` giúp thực hiện công việc này ở
dạng decorator.
Khi gọi function với một bộ argument, ``lru_cache`` sẽ lưu các argument lại
thành key của dict, và sử dụng kết quả gọi function làm value tương ứng.
``lru_cache`` có option để chỉnh kích thước của cache, phân biệt kiểu của
argument.

functools.lru_cache?
Signature: functools.lru_cache(maxsize=128, typed=False)
Docstring:
Least-recently-used cache decorator.

Một điểm đáng chú ý là các argument được gọi với function đều phải là immutable object
 bởi chúng được dùng làm key của dict. Khi dùng decorator ``lru_cache``, ta chỉ cần tập trung vào viết function cần viết, ``lru_cache`` sẽ lo việc thực hiện caching/memoization.

In [8]: @lru_cache(maxsize=None)
def fib(n):
    if n <= 2: return 1
    else:
        return fib(n-1) + fib(n-2)
   ...:

In [9]: %time fib(75)
CPU times: user 84 µs, sys: 26 µs, total: 110 µs
Wall time: 114 µs
Out[9]: 2111485077978050

Bài viết sử dụng IPython với Python 3.5

Tham khảo

- https://docs.python.org/3/library/functools.html#functools.lru_cache
- https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize
- http://stackoverflow.com/questions/1988804/what-is-memoization-and-how-can-i-use-it-in-python

Theo FML.vn