Kỹ thuật Memoize - Cache Function Results

Bạn có thấy bạn truy cập ở một trang web nhanh hơn so với lần đầu truy cập không, rất có thể là trình duyệt của bạn đã dùng bộ nhớ đệm để tải và lưu trữ những dữ liệu của trang web.
Memoize là một kỹ thuật Caching(bộ nhớ đệm), bộ nhớ đệm lưu trữ kết quả của một công việc nào đó để sử dụng cho lần sau, nó được sử dụng như một kỹ thuật tối ưu hóa phần mềm và có thể ứng dụng ở mọi ngôn ngữ.
Trong bài viết này, mình sẽ giới thiệu các bạn sử dụng kỹ thuật này bằng Python.

Nhắc lại vấn đề: bài toán tìm số Fibonacci thứ n

Vấn đề : nhìn hình ta có thể thấy f(33) được tính 2 lần và f(32) được tính 3 lần, ... và các số phía dưới sẽ tính đi tính lại rất nhiều lần.
Thuật toán tìm số fibonacci với n=35:

import timeit
def f(n):
  if n <= 1:
     return n;
  return f(n -1) + f(n - 2)
print(timeit.timeit('f(35)', globals=globals(), number=1))
//kết quả: 6.298800060000303 khoảng 6 seconds

Cách giải quyết vấn đề

Ta cần tìm một cách nào đó để lưu trữ kết quả tính f(33) và f(32) .... .Để lưu kết quả và thực hiện tính toán ở các lần sau. Ở đây mình sẽ tạo một dictionary với key là số fibonacci thứ i với (i<=n) và value là giá trị của nó.

import timeit
cache = {}
def f(n):
    if n <= 1:
        return n
    else:
        if n not in cache:
            cache[n] = f(n - 1) + f(n - 2)
        return cache[n]
//kết quả: 3.7292000342858955e-05 khoảng 3 microseconds

Nó chỉ mất 3 microseconds để thực hiện, bởi vì nó trả về kết quả ngay lập tức và chỉ tính f(33),f(32) .... duy nhất một lần, nếu đã tồn tại bộ key-value trong cache thì chúng ta chỉ cần lấy kết quả và thực hiện việc cộng thôi.

Sử dụng LRU-Cache

Một giải pháp tương tự với cách trên là sử dụng LRU-cache.

import functools
@functools.lru_cache(maxsize=none)
def f(n):
    if n <=1:
        return n
    return f(n - 1) + f(n - 2) 
print(timeit.timeit('f(35)', globals=globals(), number=1))
//kết quả: 3.056201967410743e-05 khoảng 3 microseconds

Lưu ý: đối số maxsize dùng để để giới hạn số lượng được lưu trữ trong bộ đệm tại cùng một thời điểm. có thể set bằng None để không giới hạn số lượng lưu trữ.
Các bạn nên sử dụng LRU-Cache bởi:

giải quyết được các vấn đề một cách toàn diện các bạn có thể xem ở đây Py-Source-code.
cho phép bạn biết được số liệu thống kê bộ nhớ đệm với phương thức func.cache_info().
cho phép giới hạn số lượng kết quả lưu vào cache với tham số maxsize.
ngoài ra có thể sử dụng tham số typed=True để nói với bộ nhớ đệm rằng nếu tham số truyền vào là khác nhau thì sẽ lưu riêng biệt. VD: f(35),f(35.0).
một tính năng hữu ích khác là có thể xoá bộ nhớ đệm bất cứ lúc nào bằng phương thức func.clear_cache().

Nếu bạn muốn tìm hiểu nhiều hơn về LRU-Cache, mình khuyên bạn nên tham khảo theo tài liệu chuẩn Python tại : Py-LRU-Cache.

Bạn có thể sử dụng kỹ thuật này để áp dụng trong bài toán giai thừa thử xem.

Khi nào không dùng Caching

from datetime import datetime
def nondeterministic_adder(x, y):
    # Check to see if today is Monday (weekday 0)
    if datetime.now().weekday() == 0:
        return x + y + x
    return x + y

Như các bạn thấy khi sử dụng hàm nondeterministic_adder thì dữ liệu thay đổi phụ thuộc vào ngày trong tuần nếu là thứ 2 sẽ cho kết quả là : 2*x+y và các ngày trong tuần còn lại sẽ là x+y
Nhìn chung dữ liệu thay đổi không phụ thuộc vào giá trị truyền vào của hàm thì sử dụng Memoize cũng vô dụng. Nói chung nếu có bất kì một hàm nào cập nhật một bản ghi hoặc trả về thông tin thay đổi theo thời gian ví dụ giá chứng khoán ... là một lựa chọn kém để sử dụng Memoize.

There are only two hard things in Computer Science: cache invalidation and naming things.
— Phil Karlton

Và bạn nên nhớ việc sử dụng bộ nhớ đệm, tức là bạn đang đánh đổi memory để đổi lấy tốc độ chạy nhanh hơn, nếu bạn để app chạy trong một thời gian dài, thì memory cũng vì thế mà tăng lên, nên bạn phải nghĩ tới việc giải phòng bộ nhớ cache trong thời gian chạy chương trình để tránh tràn bộ nhớ.

Kết luận

Qua bài viết này mình đã cho các bạn cái nhìn đơn giản về kĩ thuật Memoize:

Memoization là một kỹ thuật tối ưu hoá phần mềm, lưu trữ và trả kết quả của một hàm dựa trên tham số của nó.
Nếu đoạn mã của bạn đáp ứng một số tiêu chí nhất định, Memoization là một phương pháp tuyệt vời để tăng tốc ứng dụng của bạn
Bạn nên sử dụng LRU-Cache từ thư viện chuẩn của python trong module functools.

Kỹ thuật Memoize - Cache Function Results

Kỹ thuật Memoize - Cache Function Results

Nhắc lại vấn đề: bài toán tìm số Fibonacci thứ n

Cách giải quyết vấn đề

Sử dụng LRU-Cache

Khi nào không dùng Caching

Kết luận

Cùng trao đổi

Nhận xét

Đăng nhận xét