کوتاه‌ترین و بهینه‌ترین روش Memoization (پایتون)

نکته : برا درک محتوای این پست باید مفهوم Memoization را از قبل بدونید.

وقتی بخوایم برا یه مسئله یا الگوریتم تابعی بازگشتی بنویسیم ممکنه این تابع محاسبات تکراری داشته باشه به عبارتی مسئله Overlapping Subproblems باشه.

درصورت برخورد با چنین مسائلی برا بهینه کردن الگوریتم و کاهش زمان اجرای اون از برنامه‌نویسی پویا یا همون Dynamic Programming استفاده می‌کنیم. برای حل مسئله به کمک Dynamic Programming دو روش کلی وجود داره :

• حل زیرمسائل (Subproblems) از پایین به بالا (Buttom-Up)
• حل زیرمسائل از بالا به پایین (Top-Down)

توجه : روش دوم همون Memoization است.

فرض کنید می‌خوایم جمله nاُم فیبوناچی رو حساب کنیم. برا این‌کار کافیه که تابع بازگشتی اونو پیاده‌سازی کنیم، اینطوریه :

def fib(n) : 
    if n <= 2 : return 1
    return fib(n-1) + fib(n-2)

زمان اجرای الگوریتم بالا نمایی (Exponential) هست. همونطور که می‌دونید توابع نمایی رشد سریعی دارن و سرعت الگوریتمی که از زمان اجرای اون نمایی باشه خیلی کنده.

برا بهینه‌سازی می‌تونیم از برنامه‌نویسی پویا استفاده کنیم. اگر بخوایم تابع بالا را به‌صورت بالا به پایین حل کنیم می‌تونیم از حافظه کمک بگیریم که در مثال زیر از یک دیکشنری استفاده کردیم :

 memo = { 1:1, 2:1 }
 def fib(n) :
    global memo
    if n not in memo :
        memo[n] =  fib(n-1) + fib(n-2)
    return memo[n]

و اما مهمترین بخش این پست، چطوری این‌کار رو به ساده‌ترین و سریع‌ترین روش انجام بدیم؟

به کمک ابزار lru_cache در کتابخانه functools این‌کار امکان‌پذیره.

اگر به بالای هرتابع عبارت که پایین اومده رو اضافه کنیم مثل اینه که Memoization رو پیاده‌سازی کردیم چراکه داده‌ای که از تابع برمی‌گرده تو یه فضای مخصوص (cache) توسط پایتون ذخیره میشه.

@functools.lru_cache(None)

توجه : برای استفاده از lru_cache باید کتابخانه functools رو فراخونی کنیم.

اینطوری تابع فیبوناچی رو دوباره پیاده‌سازی می‌کنیم :

import functools
@functools.lru_cache(None)
 def fib(n) :     
 if n <= 2 : return 1     
 return fib(n-1) + fib(n-2) 

می‌بینید که کد تابع مثل همون روش ساده بازگشتیه.

شاید بگین این که زیاد فایده نداشت و کدمون همونطوریه تقریبا ولی بیشتر موقع‌ها Memoization مثل الان راحت نیست و حافظه‌ای که استفاده میشه سرعت کد شما رو کند میکنه. اون موقع است که با این روش خیلی حال می کنید :)

روش کلاسیک Memoization برای حل یه الگوریتم‌ (Longest Palindromic SubSequence) :

memo = {}
def LPS(s, i, j):
    global memo
    if i > j :         
        return 0   
    if (i, j) not in memo:   
        if i == j :
            memo[(i, j)] = 1
        elif s[i] == s[j] :    
             memo[(i, j)] = LPS(s, i+1, j-1) + 2  
         else :
             memo[(i, j)] = max(LPS(s, i, j-1), LPS(s, i+1, j)) 
     return memo[(i, j)]

بهره‌گیری از lru_cache برای حل همون الگوریتم‌ :

import functools
@functools.lru_cache(None)
def LPS(s,i,j):
    if i == j :
        return 1
    if i > j :
        return 0
    if s[i] == s[j]:
        return LPS(s, i+1, j-1) + 2  
    else:
        return max(LPS(s, i, j-1), LPS(s, i+1, j)) 

شاید باز با خودتون بگین این که زیاد فرقی نمیکنه (از نظر حجم کد) ولی سرعت کد دوم بیشتره و این سرعتو تو محاسبات بزرگ میشه کامل درک کرد.