ماذا يكون الـ memoization وما فائدته في بايثون؟

حسناً أنت محظوظ فهذا النوع من البرمجة كان اختصاصي خلال مشاركاتي في المسابقات البرمجية.
عندما تتحدث عن ال memoization فهذا يعني أنك دخلت حقل البرمجة الديناميكية "Dynamic Programming" كبداية سأعرفك بالبرمجة الديناميكية:
البرمجة الديناميكية هي أسلوب أو نهج في حل المسائل لتحسين التعقيد الزمني للمسائل التي تحوي "العودية".
الفكرة هي ببساطة تخزين نتائج المشكلات الفرعية "Subproblems"، حتى لا نضطر إلى إعادة حسابها عند الحاجة لها لاحقاً. وهذا مايؤدي إلى تقليل  التعقيد الزمني للعديد من المسائل من تعقيد أسي إلى تعقيد خطي polynomail. على سبيل المثال، إذا كتبنا حلًا عودياً بسيطًا لأرقام فيبوناتشي، فإننا نحصل على تعقيد زمني أسي، وإذا قمنا بتحسينه عن طريق تخزين حلول المشكلات الفرعية، فإن تعقيد الوقت ينخفض إلى خطي.

# تايع لحساب أعداد فيبوناتشي بالطريقة العودية 
def Fib(n):
	if n<0:
		print("error")
	elif n==0:
		return 0
	elif n==1:
		return 1
	else:
		return Fib(n-1)+Fib(n-2)
print(Fib(5))
# هذا الكود تعقيده أسي وهذا سيئ وغير فعال

                          fib(5)   
                     /                \
               fib(4)                fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

#تستدعى مرتين fib 3 يمكن مثلاً ملاحظة أنّ الدالة
#وإن تسنّى لنا تخزين القيمة الناتجة عن استدعاء هذه الدالة، فستنتفي الحاجة إلى إعادة حساب هذه القيمة وسيكون بالإمكان استخدام القيمة المخزّنة سابقًا عوضًا عن ذلك. 

أما عند حله باستخدام مفهوم البرمجة الديناميكية:

# Dynamic Programming
def Fib(n):
	dp = [0, 1]
	for i in range(2, n+1):
		dp.append(dp[i-1] + dp[i-2])
	return dp[n]
print(Fib(5))

لكن يجب أن تعلم أن ليس كل مسألة عودية أو أي مسألة تحوي استدعاءات متكررة يمكن أن يكون لها حل باستخدام البرمجة الديناميكية، هناك شرطين يجب أن تحققهما أي مسألة قبل أن نحاول حلها باستخدام هذا المفهوم، فإذا تحققا هذا يعني أنه يمكن حلها في ال DP، وإلا فلا تحاول، وهما:

1. مسائل فرعية متداخلة "Overlapping Subproblems": أي هل يمكن تقسيم المسألة إلى مسائل فرعية أصغر، أو إلى مهام أصغر، أو بمعنى آخر هل يمكننا تقسيم المسألة إلى مسائل أصغر بحيث تجتمع هذه المسائل لحل المسألة الأكبر. حيث أن البرمجة الديناميكية تشبه نموذج فرّق تسد في أنها تدمج حلول المسائل الفرعية بعضها ببعض. تستخدم البرمجة الديناميكية عمومًا عندما تظهر الحاجة إلى استخدام حلول مجموعة معينة من المسائل الفرعية مرة بعد أخرى. تخزّن حلول المسائل الفرعية في البرمجة الديناميكية في مصفوفة وذلك لتجنّب حسابها مرة أخرى. هذا يعني أنّ البرمجة الديناميكية غير مفيدة عندما لا تكون هناك مسائل فرعية متداخلة؛ إذ لا فائدة من تخزين الحلول إن لم تكن الخوارزمية بحاجة إليها مرة أخرى. قمثلاً تتضمن عملية حساب أعداد فيبوناتشي بطريقة تعاودية العديد من المسائل الفرعية التي يجري حلّها مرة تلو الأخرى مثل fib3 كما رأينا.
2. بنية فرعية مثالية "Optimal Substructure":نقول أنّ مسألة معيّنة تمتلك بنية فرعية مثالية إذا كان بالإمكان الحصول على الحل المثالي للمسألة المعطاة بجمع الحلول المثالية للمسائل المتفرّعة عن المسألة الرئيسية.

الآن سأنتقل لك لمفهوم ال Memoization..
نحن قلنا أنه سيتم تخزين الحلول، حسناً كيف سيتم تخزينها؟ هناك طريقتين للقيام بذلك:

1. التحفيظ Memoization (من الأعلى إلى الأسفل): تشبه طريقة التحفيظ في حل مسألة معينة الطريقة التعاودية ولكن مع تعديل بسيط، وهو أنّ هذه الطريقة تبحث في جدول البحث lookup table معين قبل حساب الحلول. تبدأ العملية بتهيئة مصفوفة بحث تحمل القيمة NIL كقيمة أولية. وفي كل مرّة نحتاج فيها إلى إيجاد حلٍّ لمسألة فرعية، نبدأ بالبحث في جدول البحث، فإن كانت القيمة محسوبة مسبقًا موجودة فيه فسنعيد حينئذٍ تلك القيمة، وإلا سنحسب القيمة ونضع النتيجة في جدول البحث ليتسنى لنا إعادة استخدامها في وقت لاحق.
   مثال لاستخدام هذه الطريقة مع المسألة السابقة:

   # الدالة المسؤولة عن حساب العدد ذي الترتيب المعطى في متتالية فيبوناتشي
   def fib(n, lookup): 
       # الحالة الأساس
       if n == 0 or n == 1 : 
           lookup[n] = n 
     # إن لم تكن القيمة محسوبة مسبقًا فسنحسبها الآن
     if lookup[n] is None: 
           lookup[n] = fib(n-1 , lookup) + fib(n-2 , lookup) 
     # n تعيد الدالة القيمة المرتبطة بالقيمة المعطاة
     return lookup[n] 
   # اختبار الدالة السابقة
   def main(): 
       n = 34
       # إنشاء جدول البحث
       # يستوعب الجدول 100 عنصر
       lookup = [None]*(101) 
       print "Fibonacci Number is ", fib(n, lookup) 
   if __name__=="__main__": 
       main()

   2.الجدولة Tabulation (من الأسفل إلى الأعلى): تبني هذه الطريقة جدولًا من الأسفل إلى الأعلى وتعيد آخر قيمة من الجدول عند الحاجة. فعلى سبيل المثال، تحسب دالة فيبوناتشي الأعداد في المتتالية حسب التسلسل fib(0)‎ ثم fib(1)‎ ثم fib(2)‎ ثم fib(3)‎ وهكذا. وهذا يعني أنّنا نبني جدول الحلول للمسائل الفرعية من الأسفل إلى الأعلى حرفياً. وهي ذات الطريقة التي استخدماتها لتخزين الحلول للمسألة في البداية.

مثال آخر للتحفيظ:
لنفترض أن لدينا الأعداد ‎{1, 3, 5}‎ والمطلوب هو إيجاد عدد الطرق التي يمكن استخدام هذه الأرقام فيها لحساب رقم معيّن (ليكن N) وذلك بإجراء عملية الجمع مع السماح بتكرار الأعداد وتغيير ترتيبها.
لكي نتمكّن من حلّ هذه المسألة ديناميكيًا يجب في البداية اتخاذ قرار بشأن الحالة الخاصة بالمسألة المعطاة، وسنستخدم معاملًا (ليكن n) لاتخاذ القرار بشأن الحالة الراهنة وذلك لإمكانية استخدام هذه المعامل في تشخيص أي مسألة فرعية بطريقة فريدة. وبهذا تكون الحالة في هذه المسألة هي state(n)‎، والتي تمثّل هنا العدد الكلي للترتيبات التي يمكن استخدامها لتكوين العدد n باستخدام العناصر ‎{1, 3, 5}‎.
ولمّا كان بالإمكان استخدام الأعداد 1 و 3 و 5 فقط لتكوين العدد المعطى، سنفترض أنّنا نعرف نتائج الأعداد n = 1, 2, 3, 4 , 5, 6 مسبقًا، وبمعنى آخر فإنّنا نعرف نتائج كلّ من ‎state (n = 1), state (n = 2), state (n = 3) ……… state (n = 6)‎.

// تعيد الدالة عدد الترتيبات لتكوين العدد المعطى
int solve(int n) 
{ 
// الحالة الأساس
if (n < 0) 
	return 0; 
if (n == 0) 
	return 1; 
return solve(n-1) + solve(n-3) + solve(n-5); 
}

تعمل الشيفرة السابقة بتعقيد زمني أسّي وتحسب الحالة نفسها مرارًا وتكرارًا؛ ولهذا يجب إضافة عملية التحفيظ memoization.
إضافة عملية التحفيظ إليها::

// تهيئة القيمة لتكون -1 
int dp[MAXN]; 
// تعيد هذه الدالة عدد الترتيبات لتكوين العدد `n`
int solve(int n) 
{ 
// الحالة الأساس
if (n < 0) 
	return 0; 
if (n == 0) 
	return 1; 
// التحقق من أنّ الحالة الراهنة محسوبة مسبقًا
if (dp[n]!=-1) 
	return dp[n]; 
// تخزين النتيجة وإعادتها
return dp[n] = solve(n-1) + solve(n-3) + solve(n-5); 
}

Memoization هي طريقة تستخدم لتخزين نتائج استدعاءات الدوال functions السابقة لتسريع العمليات الحسابية المستقبلية. إذا تم إجراء استدعاءات دالة متكررة باستخدام نفس المُدخلات ، فيمكننا تخزين القيم السابقة بدلاً من تكرار العمليات الحسابية غير الضرورية. يمكنك التفكير به ك cache لنتائج الدوال

ولهذا فائدة كبيرة جداً حيث ينتج عن هذا تسريع كبير في العمليات الحسابية.

وهناك عدة حالات لإستخدام Memoization فعلى سبيل المثال لتسريع دالة المعامل كما هو مبين في الكود

factorial_memo = {}
def factorial(k):
    if k < 2: return 1
    if k not in factorial_memo:
        factorial_memo[k] = k * factorial(k-1)
    return factorial_memo[k]