Memoization and Decorator
Python
40
programming
71
White

Vu Nhat Minh viết ngày 26/11/2015

What is memoization

Trước hết chúng ta làm quen với khái niệm memoization. Ngôn ngữ ở đây là Python, bài toán là viết hàm tính giai thừa (n!)

Hàm giai thừa thông thường sẽ được viết đệ quy như sau:

def fac(n):
    if n < 2: return 1
    return n * fac(n - 1)

Có gì không ổn ở đoạn code này ? Cách giải quyết hoàn toàn không có vấn đề, nhưng nếu tinh ý bạn sẽ nhận thấy có 1 khối lượng tính toán bị lặp lại khá nhiều khi chạy nhiều hàm fac(n). VD, nếu tính fac(3), fac(4) và fac(10) lần lượt sẽ đòi hỏi 3 flow tính toán riêng rẽ mà không có reuse: fac(3) sẽ tính đệ quy từ fac(2) xuống fac(1), fac(4) tính đệ quy từ fac(3) xuống fac(1) và fac(10) tính đệ quy từ fac(9) xuống fac(1) !

Áp dụng memoization dưới dạng dict, ta có thể viết hàm fac_m như sau:

memo = {}
def fac_m(n):
    if n<2: return 1
    if n not in memo:
        memo[n] = n * fac_m(n-1)
    return memo[n]

Ở đây memo đóng vài trò như 1 cache. fac(3) sẽ generate ra 3 record in cache, và fac(4) sẽ hit cache khi chạy đệ quy được 1 lần. Tương tự fac(10) sẽ hit cache khi đệ quy xuống đến fac(4)

Như vậy memoization đơn giản chỉ là tìm cách nhớ những phần tử để giảm khối lượng tính toán

Memoization có thể implement dưới dạng function...

def memoize(fn, arg):
    memo = {}
    if arg not in memo:
        memo[arg] = fn(arg)
    return memo[arg]
def fac_m_f(n):
    return memoize(fac,n)

...hoặc class

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        return self.memo[args]
fac= Memoize(fac)

Thêm 1 step nữa, thay vì "fac=Memoize(fac)" như ở trên, bạn có thể viết hàm mới theo kiểu decorator

@Memoize
def fac_m_d(n):
    if n<2: return 1
    return n * fac_m_d(n-1)

Decorator ở đây là từ khoá "@Memoize" trước định nghĩa của hàm fac_m_d

Vậy decorator trong Python là gì và cách dùng ra sao ?

Python decorator


Trong số các design pattern, có 1 design pattern gọi là "decorator design pattern". Python decorator chỉ là 1 cách implement của decorator design pattern. 2 khái niệm này không hoàn toàn giống nhau. Một điểm nữa cần nhớ là, memoization ở trên chỉ là 1 trong các ứng dụng của python decorator, python decorator còn có nhiều ứng dựng khác.

Mọi function trong python đều là object, cho phép ta có thể assign funtion cho variable hoặc define function trong chính 1 function khác. Dựa vào đó, decorator có thể dưới dạng decorator function như ví dụ dưới đây:

def gotham(f):
    def inside_gotham():
        print "Gotham needs Batman"
        f()
    return inside_gotham

@gotham
def batman():
    print "Batman Here! Gotham is saved! "

batman()

Đoạn code sẽ cho output:

Gotham needs Batman
Batman Here! Gotham is saved!

Cơ chế của decorator có thể hiểu đơn giản là, khi intepreter đọc đến đoạn code đefine function với decorator, interpreter sẽ evaluate function 1 cách bình thường và pass function object kết quả thẳng cho decorator(dưới dạng function hoặc class). Decorator(function hoăc class) lấy agrument là 1 function object và return kết quả là 1 function object khác.

Function object kết quả nói trên gồm function object ban đầu đã được gói lại và "thêm thắt", và từ nay về sau sẽ được gọi thay cho function object ban đầu mỗi khi có lệnh call.

Ngoài memoization bên trên, bạn có thể dễ thấy rất nhiều ứng dụng của decorator trong các task liên quan đến wrap VD như:

Timing, benchmark tính toán thời gian run code

def time_cal(func):
    def wrapper(*arg):
        t = time.time()
        res = func(*arg)
        print func.func_name, time.time()-t
        return res
    return wrapper

@time_cal
def fac(n):
    if n < 2: return 1
    return n * fac(n - 1)

hay trong web application, nếu bạn đã dùng Flaskr, bạn có thể thấy đoạn code sau

@mod.route('/me/')
@requires_login
def home():
...

Ở đây trang web của bạn ở sublink ".../me" sẽ được đảm bảo chỉ viewable với user đã login. Decorator "@requires_login" có thể viết ở 1 file độc lập và mọi hàm cần tính đảm bảo như trên chỉ cần thêm "@requires_login" đằng trước.

from functools import wraps
...
def requires_login(f):
    @wraps(f)
    def decorated_function(*args, **kwargs):
        if g.user is None:
            flash(u'You need to be signed in for this page.')
            return redirect(url_for('users.login', next=request.path))
        return f(*args, **kwargs)
    return decorated_function

Kết luận

  • Memoization: pattern dùng để nhớ các tính toán nhằm làm giảm workload khi gặp các bài toán đệ quy
  • Decorator pattern: decorator design pattern
  • Python Decorator: Python tools để implement decorator pattern
Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Vu Nhat Minh

54 bài viết.
777 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
120 30
Nếu bạn thường vào trang mua sắm của amazon, chắc sẽ chẳng lạ gì với menu Shop by Department. Tốc độ hiển thị nội dung của menu là tức thì so với d...
Vu Nhat Minh viết gần 3 năm trước
120 30
White
93 4
Lời người dịch Người dịch là một developer , sau khi tìm đọc được bài viết này bằng bản gốc tiếng Anh đã cảm thấy như được "khai sáng" về khả năng...
Vu Nhat Minh viết 3 năm trước
93 4
White
62 5
Đây là phần cuối của một series chuyên về thiết kế UI. Bạn nên đọc (Link) trước khi bắt đầu đọc phần này. Luật số 7: "Ăn trộm" như là một nghệ sỹ...
Vu Nhat Minh viết gần 3 năm trước
62 5
Bài viết liên quan
White
1 0
Mở đầu Như đã nói ở bài trước, mình đang nghiên cứu về Spark nên cần log lại một số thứ để dành sau này dùng đến :smile: Đối tượng hướng đến vẫn ...
Phạm Quốc Thắng viết hơn 2 năm trước
1 0
White
5 3
Observer pattern (python example) 1. Observer là gì : Theo như (Link) Observer Pattern là : A software design pattern in which an object, calle...
Khôi Trọng Nguyễn viết gần 2 năm trước
5 3
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
54 bài viết.
777 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!