المذكرة مقابل الجدولة
طريقتان لتخزين إجابات المسائل الفرعية مؤقتًا
المذكرة مقابل الجدولة درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
لماذا نستخدم التخزين المؤقت
تعيد الاستدعاءات العودية الساذجة العمل نفسه مرارًا وتكرارًا. وتخزّن البرمجة الديناميكية كل إجابة مرة واحدة، فلا تعيد حسابها أبدًا.
fib(40) # slow: recomputes endlesslyالمسائل الفرعية المتداخلة
تُستخدم البرمجة الديناميكية عندما تنقسم المسألة إلى مسائل فرعية متداخلة. فتظهر الحالة الأصغر نفسها في فروع عديدة من الاستدعاء العودي.
fib(5) needs fib(3) twiceمن الأعلى إلى الأسفل: الحفظ المؤقت
إن الحفظ المؤقت هو الاستدعاء العودي العادي مضافًا إليه ذاكرة مؤقتة. تحسب النتيجة عند الحاجة وتتذكرها عند أول ظهور لكل مُدخل.
memo = {}حفظ مؤقت سهل في Python
يحوّل المزيّن lru_cache الاستدعاء العودي البطيء إلى برمجة ديناميكية سريعة في سطر واحد، إذ يخزّن نتيجة كل استدعاء تلقائيًا.
from functools import lru_cache
@lru_cache(None)
def f(n): ...من الأسفل إلى الأعلى: الجدولة
تملأ الجدولة جدولًا بدءًا من أصغر الحالات وصولًا إلى الإجابة، باستخدام حلقة بدلًا من الاستدعاء العودي.
dp = [0] * (n + 1)متتالية فيبوناتشي مجدولة
عيّن القيم الأساسية، ثم اجعل كل خلية تقرأ القيم المحسوبة مسبقًا. لا توجد مكدسة استدعاءات، بل حلقة واضحة فحسب.
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]الإجابة نفسها، والأسلوب مختلف
يحلّ كل من الحفظ المؤقت والجدولة العلاقة التكرارية نفسها. ويختلفان فقط في الاتجاه: من الأعلى إلى الأسفل عند الحاجة، أو من الأسفل إلى الأعلى بالترتيب.
متى تفضّل الحفظ المؤقت
استخدم الحفظ المؤقت عندما تكون العلاقة التكرارية طبيعية في كتابتها، وقد لا تحتاج إلى كل الحالات.
متى تفضّل الجدولة
اختر الجدولة للحلقات المحكمة، ولتجنب أخطاء حدّ الاستدعاء العودي، وعندما ستحسب الجدول بأكمله على أي حال.
import sys; sys.setrecursionlimit(10**6)انتبه إلى حد الاستدعاء العودي
قد يصل الاستدعاء العودي العميق مع الحفظ المؤقت إلى حد الاستدعاء العودي في Python، ويتسبب في فشل البرنامج بخطأ وقت التشغيل عند المدخلات الكبيرة.
التكلفة المشتركة بينهما
في كلتا الحالتين، يأتي تسريع الأداء من حل كل حالة مرة واحدة. ويُحسب الزمن الإجمالي بضرب عدد الحالات في العمل اللازم لكل حالة.
اختبار سريع
أي نهج يملأ جدولًا من الأسفل إلى الأعلى باستخدام حلقة؟
مراجعة: طريقان وDP واحدة
يمكنك الآن تخزين المسائل الفرعية مؤقتًا بطريقتين. يستخدم الحفظ المؤقت الاستدعاء العودي من الأعلى إلى الأسفل، بينما تستخدم الجدولة حلقات من الأسفل إلى الأعلى. اختر الأسلوب الأوضح قراءةً. ✨
الأسئلة الشائعة
هل درس «المذكرة مقابل الجدولة» مجاني؟
نعم — نص درس «المذكرة مقابل الجدولة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «المذكرة مقابل الجدولة»؟
طريقتان لتخزين إجابات المسائل الفرعية مؤقتًا تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «المذكرة مقابل الجدولة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- المذكرة مقابل الجدولة
- تعريف الحالة والانتقال
- تسلّق الدرج وتوليفات العملات
- أطول تتابع متزايد