Pymi.vn

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

written by HVN

I. Memoization

Memoization không phải là một từ Tiếng Anh có thể tìm thấy trong từ điển Oxford Online . 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ủa stack)

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

II. 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.
  • ...

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

Tham khảo: