[Tự học Python] Kỹ thuật Memoization bằng cách sử dụng các Decorators trong Python

Đệ quy là một kỹ thuật lập trình mà trong đó một hàm tự gọi lại chính nó, lặp đi lặp lại cho đến khi một điều kiện dừng cụ thể được đáp ứng. Có thể kể đến một số ví dụ mà đệ quy được sử dụng là: tính chuỗi số fibonacci, tính giai thừa, v.v… Tuy nhiên, có một vấn đề mà chúng ta luôn gặp phải khi sử dụng đệ quy đó là sẽ có một xác suất ở trong cây đệ quy của chương trình mà một vấn đề nhỏ đã được giải quyết trước đó, lại được giải quyết lại một vài lần nữa, điều này làm tiêu tốn rất nhiều tài nguyên máy tính.

Memoization là một kỹ thuật ghi nhớ các kết quả trung gian sao cho chúng có thể được sử dụng để tránh lặp lại việc xử lý các bài toán đã từng được giải quyết xong rồi, nhằm tăng tốc các chương trình. Nó có thể được sử dụng để tối ưu các chương trình sử dụng đệ quy. Trong Python, kỹ thuật Memoization có thể được thực hiện với sự trợ giúp của các function decorators.

Để giúp bạn hình dung được sự khác biệt, chúng ta sẽ xét các ví dụ, đầu tiên là ví dụ tính giai thừa của một số, sử dụng đệ quy:

# Simple recursive program to find factorial 
def facto(num): 
    if num == 1: 
        return 1
    else: 
        return num * facto(num-1) 
          
  
print(facto(5)) 

Đoạn chương trình trên có thể được tối ưu lại nhờ kỹ thuật Memoization bằng cách sử dụng các decorators.

# -----------------------------------------------------------
#Cafedev.vn - Kênh thông tin IT hàng đầu Việt Nam
#@author cafedevn
#Contact: cafedevn@gmail.com
#Fanpage: https://www.facebook.com/cafedevn
#Instagram: https://instagram.com/cafedevn
#Twitter: https://twitter.com/CafedeVn
#Linkedin: https://www.linkedin.com/in/cafe-dev-407054199/
# -----------------------------------------------------------


# Factorial program with memoization using 
# decorators. 
  
# A decorator function for function 'f' passed 
# as parameter 
def memoize_factorial(f): 
    memory = {} 
  
    # This inner function has access to memory 
    # and 'f' 
    def inner(num): 
        if num not in memory:          
            memory[num] = f(num) 
        return memory[num] 
  
    return inner 
      
@memoize_factorial
def facto(num): 
    if num == 1: 
        return 1
    else: 
        return num * facto(num-1) 
  
print(facto(5)) 

Giải thích:

1. Một hàm có tên là memoize_factorial đã được khai báo. Mục đích chính của nó là để lưu lại các kết quả trung gian nằm trong biến memory.

2. Hàm thứ hai được gọi là facto có nhiệm vụ tính giai thừa. Nó được đánh dấu bởi một decorator (chính là hàm memoize_factorial). Hàm facto có quyền truy cập tới biến memory, điều này có được là nhờ kỹ thuật closure. Việc đánh dấu hàm facto bằng một decorator thì tương đương với việc viết câu lệnh sau:

facto = memoize_factorial(facto)

3. Khi hàm facto(5) được gọi, việc xử lý đệ quy sẽ bắt đầu, song song với đó, việc lưu lại các kết quả trung gian cũng sẽ được tiến hành. Mỗi lần một phép toán xử lý đệ quy được hoàn thành, nó sẽ kiểm tra liệu rằng kết quả có tồn tại trong biến mảng memory hay không? Nếu có, vậy thì nó sẽ được sử dụng luôn; nếu không thì giá trị này sẽ được tính toán và lưu lại trong biến mảng memory.

4. Chúng ta có thể xác minh liệu rằng kỹ thuật Memoization có thực sự hoạt động hay không bằng cách theo dõi output của chương trình.