التخزين المؤقت: حفظ نتائج الاستدعاء الذاتي
طبّق @functools.lru_cache وقواميس memo اليدوية على Fibonacci وclimbing-stairs لإلغاء إعادة الحساب الأسية
التخزين المؤقت: حفظ نتائج الاستدعاء الذاتي درس مجاني في DSA Interview Prep على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في DSA Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
مشكلة الاستدعاء الذاتي المتكرر بلا حاجة
يحسب فيبوناتشي الساذج المعتمد على الاستدعاء الذاتي القيم نفسها مرارًا. يستدعي fib(5) كلًا من fib(4) وfib(3)؛ ويستدعي fib(4) كلًا من fib(3) وfib(2)، ولذلك تُحسب fib(3) مرتين. ينمو هذا التكرار نموًا أُسّيًا: إذ ينفّذ fib(40) أكثر من مليار استدعاء لدالة. يحل التخزين المؤقت هذه المشكلة عبر تخزين كل نتيجة عند حسابها للمرة الأولى، بحيث تسترجعها الاستدعاءات اللاحقة في O(1) بدلًا من إعادة حسابها.
# Count calls without memoisation
call_count = [0]
def fib_plain(n):
call_count[0] += 1
if n <= 1: return n
return fib_plain(n-1) + fib_plain(n-2)
fib_plain(20)
print(f'fib(20) without memo: {call_count[0]:,} calls')
# ~21,891 calls for n=20; ~1 billion for n=40التخزين المؤقت اليدوي باستخدام قاموس
أضف قاموس memo كمعامل، أو استخدم إغلاقًا. قبل إجراء الحساب، تحقق مما إذا كانت الإجابة موجودة بالفعل في memo. إذا كانت موجودة، فأعدها فورًا. وإذا لم تكن موجودة، فاحسبها وخزّنها في memo ثم أعدها. تُحسب كل مسألة فرعية فريدة مرة واحدة بالضبط، مما يحوّل التعقيد من O(2^n) إلى زمن O(n) ومساحة O(n) لقاموس memo، بالإضافة إلى مساحة مكدس مقدارها O(n).
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
print(fib_memo(10)) # 55
print(fib_memo(50)) # 12586269025
print(fib_memo(100)) # huge number — still fast!مزيّن functools.lru_cache
توفر Python @functools.lru_cache(maxsize=None)، والمتاحة أيضًا باسم @functools.cache في Python 3.9 والإصدارات الأحدث، لأتمتة التخزين المؤقت. تؤدي إضافة هذا المزيّن فوق الدالة إلى تخزين نتائج جميع الاستدعاءات وفقًا لمعاملاتها. وتعني maxsize=None أن حجم ذاكرة التخزين المؤقت غير محدود، إذ تُخزَّن كل تركيبة فريدة من المعاملات. يحوّل هذا أي دالة تعتمد على الاستدعاء الذاتي إلى إصدار يستخدم التخزين المؤقت، وذلك بسطر واحد من الشيفرة.
import functools
@functools.lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
print(fib(50)) # 12586269025
print(fib(100)) # 354224848179261915075
print(fib.cache_info()) # CacheInfo(hits=..., misses=..., maxsize=None, currsize=...)صعود السلالم (LeetCode 70)
في مسألة LeetCode 70 «Climbing Stairs»، يمكنك صعود درجة أو درجتين في كل مرة. كم عدد الطرق للوصول إلى الدرجة n؟ هذه المسألة هي فيبوناتشي متخفية: ways(n) = ways(n-1) + ways(n-2). حالات الأساس هي: ways(0) = 1، أي إن هناك طريقة واحدة للبقاء عند الأرض، وways(1) = 1. باستخدام التخزين المؤقت، يكون الزمن O(n) والمساحة O(n).
import functools
@functools.lru_cache(maxsize=None)
def climbStairs(n):
if n <= 1:
return 1
return climbStairs(n-1) + climbStairs(n-2)
for i in range(1, 8):
print(f'climbStairs({i}) = {climbStairs(i)}')
# 1,2,3,5,8,13,21تبديل العملات (LeetCode 322)
في مسألة LeetCode 322 «Coin Change»، مع إعطائك فئات العملات ومبلغ مستهدف، أوجد الحد الأدنى لعدد العملات. يستخدم الاستدعاء الذاتي من أعلى إلى أسفل مع التخزين المؤقت الصيغة: dp(amount) = 1 + min(dp(amount - coin)) لكل عملة صالحة. حالة الأساس هي: dp(0) = 0. خزّن كل مبلغ فرعي مؤقتًا. وإذا تعذر تكوين مبلغ فرعي، فأعد قيمة اللانهاية. يحوّل التخزين المؤقت الحل بالقوة الغاشمة ذي التعقيد الأُسّي إلى زمن O(amount × len(coins)).
import functools
def coinChange(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(rem):
if rem == 0:
return 0
if rem < 0:
return float('inf')
return 1 + min(dp(rem - c) for c in coins)
result = dp(amount)
return result if result != float('inf') else -1
print(coinChange([1, 5, 11], 15)) # 3 (5+5+5)
print(coinChange([1, 2, 5], 11)) # 3 (5+5+1)
print(coinChange([2], 3)) # -1تقسيم الكلمات (LeetCode 139) باستخدام التخزين المؤقت
في مسألة LeetCode 139 «Word Break»، حدّد ما إذا كان يمكن تقسيم سلسلة نصية إلى كلمات موجودة في القاموس. يجرّب الاستدعاء الذاتي من أعلى إلى أسفل كل بادئة s[start:end] في الدالة can_break(s, start)؛ فإذا كانت البادئة موجودة في القاموس وكانت نتيجة can_break(s, end) تساوي true، فأعد true. من دون التخزين المؤقت يكون التعقيد O(2^n)، أما باستخدامه، مع تخزين نتيجة كل فهرس بداية، فيصبح O(n² × L)، حيث L هو أقصى طول للكلمة.
import functools
def wordBreak(s, wordDict):
word_set = set(wordDict)
@functools.lru_cache(maxsize=None)
def can_break(start):
if start == len(s):
return True
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and can_break(end):
return True
return False
return can_break(0)
print(wordBreak('leetcode', ['leet', 'code'])) # True
print(wordBreak('applepenapple', ['apple','pen'])) # True
print(wordBreak('catsandog', ['cats','dog','sand','and','cat'])) # Falseالتخزين المؤقت مقابل بناء الجداول
يبدأ التخزين المؤقت، أو النهج من أعلى إلى أسفل، من المشكلة الأصلية ويخزّن الإجابات عند اكتشافها استدعاءً ذاتيًا. ولذلك فهو يحل المسائل الفرعية المطلوبة فعليًا فقط. أما بناء الجداول، أو النهج من الأسفل إلى الأعلى، فيملأ جدولًا مسبقًا بدءًا من المسائل الفرعية الصغيرة وصولًا إلى الكبيرة، ويحل جميع المسائل الفرعية دون استثناء. ومن الأسهل اشتقاق التخزين المؤقت من حل يعتمد على الاستدعاء الذاتي، بينما يتجنب بناء الجداول قيود عمق الاستدعاء الذاتي والكلفة الإضافية لاستدعاءات الدوال.
# Memoisation (top-down)
import functools
@functools.lru_cache(maxsize=None)
def fib_td(n):
if n <= 1: return n
return fib_td(n-1) + fib_td(n-2)
# Tabulation (bottom-up)
def fib_bu(n):
if n <= 1: return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fib_td(20), fib_bu(20)) # 6765 6765
# Both O(n) time; fib_bu avoids recursion limitتحسين المساحة: المتغيرات المتتابعة
يمكن تحسين كثير من مسائل DP التي يحلها الاستدعاء الذاتي مع التخزين المؤقت باستخدام مساحة O(n)، لتستخدم مساحة O(1) عندما لا نحتاج إلا إلى عدد ثابت من إجابات المسائل الفرعية السابقة. ففي فيبوناتشي، لا تهم إلا القيمتان الأخيرتان. وينطبق الأمر نفسه على صعود السلالم. ويحل استخدام متغيرين متتابعين محل قاموس memo أو الجدول بأكمله.
# Fibonacci with O(1) space
def fib_o1(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev2 + prev1
return prev1
for i in range(8):
print(f'fib({i})={fib_o1(i)}', end=' ')
print()
# Climbing stairs O(1) space
def climbStairs_o1(n):
if n <= 1: return 1
a, b = 1, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(climbStairs_o1(10)) # 89lru_cache مقابل الإغلاق مقابل القاموس العام
هناك ثلاث طرق لتنفيذ التخزين المؤقت يدويًا. القاموس العام بسيط، لكنه يلوّث نطاق الوحدة. أما الإغلاق فيحصر ذاكرة التخزين المؤقت داخل الدالة، مما يمنع تسرّبها، لكنه يتطلب غلافًا. ويُعد @lru_cache الخيار الأنظف، إذ يستبدل كل الشيفرة التمهيدية بمزيّن واحد. وفي سياق المقابلات، ابدأ باستخدام @lru_cache ما لم يطلب منك المحاوِر تحديدًا تنفيذًا يدويًا.
import functools
# 1. Global dict (messy)
memo_global = {}
def fib_global(n):
if n in memo_global: return memo_global[n]
if n <= 1: return n
memo_global[n] = fib_global(n-1) + fib_global(n-2)
return memo_global[n]
# 2. Closure (cleaner scope)
def make_fib():
cache = {}
def fib(n):
if n in cache: return cache[n]
if n <= 1: return n
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
return fib
fib_closure = make_fib()
# 3. lru_cache (best)
@functools.lru_cache(maxsize=None)
def fib_cached(n):
if n <= 1: return n
return fib_cached(n-1) + fib_cached(n-2)
print(fib_global(30), fib_closure(30), fib_cached(30)) # all 832040متى لا يفيد التخزين المؤقت
يسرّع التخزين المؤقت المشكلات التي تتضمن مسائل فرعية متداخلة فقط، أي الحالات التي تُحسب فيها المسألة الفرعية نفسها عدة مرات. فإذا كانت كل مسألة فرعية فريدة، كما في اجتياز شجرة بسيط تُزار فيه كل عقدة مرة واحدة بالضبط، فإن التخزين المؤقت يضيف كلفة دون فائدة. كما لا يستطيع التخزين المؤقت إصلاح المشكلات التي تكون فيها شجرة الاستدعاء الذاتي أُسّية بالنسبة إلى عدد المسائل الفرعية المميزة بدلًا من كونها أُسّية بسبب إعادة الاستخدام؛ فهذه المشكلات تتطلب خوارزمية مختلفة تمامًا.
# Memoisation DOES help: overlapping sub-problems (Fibonacci)
# fib(n) reuses fib(n-2), fib(n-3), etc.
# Memoisation does NOT help: distinct sub-problems (permutations)
# Each unique (remaining_elements, target) pair is truly distinct
# The exponential complexity comes from the state space itself
print('Memoisation: useful when SAME sub-problem recurs multiple times')
print('Not useful: when every sub-problem is unique to one recursive path')ملخص: قائمة التحقق من التخزين المؤقت
طبّق التخزين المؤقت عندما: يكون لديك حل يعتمد على الاستدعاء الذاتي وصحيح لكنه بطيء بسبب إعادة الحساب غير الضرورية، وتكون للدالة عدد صغير من تركيبات المعاملات المميزة، وتعتمد القيمة المعادة على المعاملات فقط، أي إن الدالة نقية ولا تتضمن آثارًا جانبية أو حالة عامة. افحص فضاء حالات المسائل الفرعية: فإذا كان هناك O(n) أو O(n²) حالة مميزة على الأكثر، يحوّل التخزين المؤقت الزمن الأُسّي إلى زمن كثير الحدود.
تحقق سريع
اختبر مدى فهمك لمفاهيم Data Structures & Algorithms — Coding Interview Prep التي تناولها هذا الدرس.
مراجعة الدرس
تعلمت في هذا الدرس أن: التخزين المؤقت يخزّن نتائج المسائل الفرعية لتجنب إعادة الحساب، محوّلًا الاستدعاء الذاتي الأُسّي إلى زمن كثير الحدود، وأن @functools.lru_cache هو الأداة الاصطلاحية في Python، ولا يتطلب سوى سطر واحد، وأن التخزين المؤقت، من أعلى إلى أسفل، وبناء الجداول، من الأسفل إلى الأعلى، هما الأسلوبان الأساسيان للبرمجة الديناميكية DP؛ فالتخزين المؤقت أسهل اشتقاقًا، بينما يتجنب بناء الجداول مشكلات عمق المكدس. تهانينا، لقد أتممت وحدتي الاستدعاء الذاتي وجداول التجزئة!
الأسئلة الشائعة
هل درس «التخزين المؤقت: حفظ نتائج الاستدعاء الذاتي» مجاني؟
نعم — نص درس «التخزين المؤقت: حفظ نتائج الاستدعاء الذاتي» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة DSA Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «التخزين المؤقت: حفظ نتائج الاستدعاء الذاتي»؟
طبّق @functools.lru_cache وقواميس memo اليدوية على Fibonacci وclimbing-stairs لإلغاء إعادة الحساب الأسية تتمرن على DSA Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ DSA Interview Prep؟
لا تُشترط خبرة سابقة. DSA Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «التخزين المؤقت: حفظ نتائج الاستدعاء الذاتي»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس DSA Interview Prep هذا؟
نعم. كل درس في DSA Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- إطار الاستدعاء الذاتي: الحالة الأساسية والثقة والبناء
- تصوير مكدس الاستدعاء
- مفاضلات الاستدعاء الذاتي والتكرار
- التخزين المؤقت: حفظ نتائج الاستدعاء الذاتي