شيفرتي كانت تعيد نفس الحسابات ألف مرة: كيف أنقذتني ‘البرمجة الديناميكية’ من جحيم التكرار

يا هلا بيكم يا جماعة الخير، معكم أخوكم أبو عمر.

بتذكر مرة، قبل كم سنة، كنت شغال على مشروع تحليل بيانات جينية. كان مشروع ضخم ومعقد، وفي قلبه خوارزمية بتحاول تلاقي أطول سلسلة مشتركة بين حمضين نوويين (DNA). كتبت الخوارزمية بشكل استدعاء ذاتي (Recursion)، وعلى جهازي، لما جربتها على سلاسل قصيرة، كانت تشتغل زي الحلاوة. “خلص، فرطت”، قلت لحالي بكل ثقة.

لكن لما إجا وقت الجد، وجربت الخوارزمية على بيانات حقيقية – سلاسل طويلة بآلاف الأحرف – كانت الصدمة. البرنامج “علّق”، أو بالأحرى، صار أبطأ من سلحفاة مصابة بالزكام. تركته شغال طول الليل ورجعت الصبح لقيته لسا ما خلص! يا زلمة، شو هالحكي؟ حسيت بإحباط شديد وكنت على وشك أرمي كل الشغل وأبدأ من الصفر. بعد فنجان قهوة ثقيل وجلسة “تصفين” مع الكود، لاحظت شي غريب: البرنامج كان غبي! كان بعيد نفس الحسابات للمشاكل الفرعية الصغيرة آلاف، بل ملايين المرات. كل مرة بستدعي فيها الدالة (Function) لنفس المدخلات، كانت بترجع تحسب كل شي من أول وجديد. هُنا كانت لحظة “وجدتها!” بالنسبة لي، وتذكرت مفهوماً درسته في الجامعة وكنت أظنه مجرد حكي نظري: البرمجة الديناميكية.

ما هي مشكلة “الحسابات المتكررة”؟

قبل ما نغوص في الحل، خلينا نفهم أصل المشكلة. تخيل أنك طلبت من عامل بناء يبني لك حائطاً من 10 طوابق. لكن هذا العامل يعاني من ذاكرة ضعيفة جداً. كلما أراد أن يضع طوبة في الطابق الخامس، ينسى كيف بنى الطوابق الأربعة التي تحته، فيعود ويهدمها ثم يبنيها من جديد ليصل إلى الطابق الخامس! هذا بالضبط ما تفعله بعض الخوارزميات الساذجة.

أشهر مثال لشرح هذه المشكلة هو “متتالية فيبوناتشي”. القاعدة بسيطة: كل رقم هو مجموع الرقمين الذين يسبقانه (…,1, 1, 2, 3, 5, 8). الحل المباشر باستخدام الاستدعاء الذاتي يبدو هكذا:

# Python code
# الحل الساذج باستخدام الاستدعاء الذاتي
def fibonacci(n):
    # الحالة الأساسية: أول رقمين في المتتالية
    if n <= 1:
        return n
    # المشكلة: هنا نعيد حساب نفس القيم مراراً وتكراراً
    return fibonacci(n - 1) + fibonacci(n - 2)

# استدعاء الدالة لحساب الرقم الخامس في المتتالية
print(fibonacci(5))

لو تتبعنا عملية حساب fibonacci(5)، سنجد أننا نحسب fibonacci(3) مرتين، وfibonacci(2) ثلاث مرات، وهكذا. كلما زاد الرقم `n`، زاد هذا التكرار بشكل أُسّي، وهذا هو “جحيم التكرار” الذي أتحدث عنه.

البرمجة الديناميكية: الساحر الذي لا ينسى

البرمجة الديناميكية (Dynamic Programming أو DP اختصاراً) هي تقنية لتحسين أداء الخوارزميات عن طريق حل المشاكل الفرعية مرة واحدة فقط وتخزين نتائجها لاستخدامها لاحقاً عند الحاجة. بالبلدي، هي طريقة لتعليم برنامجك أن “لا ينسى” ما قام بحسابه بالفعل.

لكي تتمكن من تطبيق البرمجة الديناميكية، يجب أن تتوافر في مشكلتك خاصيتان أساسيتان:

1. التداخل في المسائل الفرعية (Overlapping Subproblems)

هذا يعني أن الخوارزمية تقوم بحل نفس المشاكل الفرعية مراراً وتكراراً. مثلما رأينا في مثال فيبوناتشي، حساب fib(5) يتطلب حساب fib(3)، وحساب fib(4) يتطلب أيضاً حساب fib(3). هذا التداخل هو ما يسبب البطء، وهو أيضاً ما يمكننا من التحسين.

2. البنية المثلى (Optimal Substructure)

هذا يعني أن الحل الأمثل للمشكلة الكلية يمكن بناؤه من الحلول المثلى لمشاكلها الفرعية. في مثال فيبوناتشي، الحل لـ fib(n) هو ببساطة مجموع الحلين لـ fib(n-1) و fib(n-2). هذه الخاصية تضمن أننا عندما نحل المشاكل الصغيرة، فإننا نسير في الطريق الصحيح نحو حل المشكلة الكبيرة.

كيف نطبق البرمجة الديناميكية؟ طريقتان لا ثالث لهما

هناك طريقتان رئيسيتان لتطبيق البرمجة الديناميكية، وكلاهما يهدف إلى نفس الشيء: تخزين النتائج لتجنب إعادة الحساب.

الطريقة الأولى: التخزين المؤقت (Memoization – Top-Down)

هذه الطريقة هي الأقرب للتفكير البشري الطبيعي. إنها في الأساس نفس الحل الاستدعائي الذاتي، ولكن مع إضافة “ذاكرة تخزين مؤقت” (Cache). قبل أن تقوم الدالة بأي عملية حسابية، تتحقق أولاً: “هل حسبت هذه القيمة من قبل؟”. إذا كانت الإجابة “نعم”، فإنها تعيد القيمة المخزنة مباشرة. إذا كانت “لا”، فإنها تحسب القيمة، تخزنها في الذاكرة، ثم تعيدها.

دعنا نعدل كود فيبوناتشي ليستخدم هذه الطريقة:

# Python code
# ذاكرة لتخزين النتائج التي تم حسابها
memo = {}

def fib_memo(n):
    # إذا كانت القيمة موجودة في الذاكرة، أعدها مباشرة
    if n in memo:
        return memo[n]
    
    # الحالة الأساسية
    if n <= 1:
        return n
    
    # إذا لم تكن موجودة، احسبها
    result = fib_memo(n - 1) + fib_memo(n - 2)
    
    # خزّن النتيجة في الذاكرة قبل إعادتها
    memo[n] = result
    return result

# الآن، حتى لو طلبت حساب رقم كبير، ستكون العملية سريعة جداً
print(fib_memo(50))

هذه الطريقة، التي أحب أن أسميها “اسأل أول، بعدين احسب”، حولت خوارزمية بطيئة جداً إلى خوارزمية خطية وسريعة بشكل لا يصدق.

الطريقة الثانية: الجدولة (Tabulation – Bottom-Up)

هذه الطريقة تتبع نهجاً مختلفاً. بدلاً من البدء من المشكلة الكبيرة والنزول إلى المشاكل الصغيرة (Top-Down)، تبدأ هذه الطريقة من أصغر مشكلة فرعية وتبني الحل “حبة حبة” حتى تصل إلى الحل النهائي للمشكلة الكبيرة. عادة ما يتم ذلك باستخدام حلقة تكرار (loop) وجدول (أو مصفوفة) لتخزين النتائج.

بالنسبة لفيبوناتشي، سنقوم بإنشاء مصفوفة ونملؤها بالقيم بدءاً من fib(0) و fib(1) وصولاً إلى الرقم `n` المطلوب.

# Python code
def fib_tab(n):
    if n <= 1:
        return n
    
    # إنشاء جدول بحجم n+1 لتخزين النتائج
    dp_table = [0] * (n + 1)
    dp_table[1] = 1 # الحالة الأساسية
    
    # بناء الحل من الأسفل إلى الأعلى
    for i in range(2, n + 1):
        dp_table[i] = dp_table[i-1] + dp_table[i-2]
        
    return dp_table[n]

# سريعة وفعالة أيضاً، ولا تستخدم الاستدعاء الذاتي
print(fib_tab(50))

هذه الطريقة، أو “ابنيها حبة حبة”، غالباً ما تكون أكثر كفاءة من حيث استخدام الذاكرة وتتجنب مشاكل عمق الاستدعاء الذاتي (recursion depth limit) التي قد تحدث في الطريقة الأولى.

نصائح أبو عمر الذهبية للتعامل مع البرمجة الديناميكية

من خلال معاركي الكثيرة مع الخوارزميات، تعلمت بعض الدروس التي أود أن أشارككم إياها.

• حدد المشكلة أولاً: قبل أن تقفز إلى كتابة الكود، اسأل نفسك: هل هناك تداخل في المسائل الفرعية؟ هل يمكن بناء الحل الأمثل من حلول فرعية مثلى؟ إذا كانت الإجابة “نعم” لكليهما، فالبرمجة الديناميكية هي صديقك.
• ابدأ بالحل الساذج (الاستدعائي): من الأسهل غالباً أن تفكر في الحل الاستدعائي أولاً. اكتبه، تأكد من أنه يعمل (حتى لو كان بطيئاً)، ثم قم بتحويله بسهولة إلى حل يستخدم التخزين المؤقت (Memoization). هذه خطوة انتقالية ممتازة.
• فكّر “من تحت لفوق”: بعد أن تعتاد على التفكير الديناميكي، حاول حل المشكلة مباشرة باستخدام الجدولة (Tabulation). هذا النهج يجبرك على فهم ترتيب الحسابات بشكل أعمق وقد ينتج عنه كود أكثر كفاءة.
• لا تخف من استهلاك الذاكرة: البرمجة الديناميكية هي مقايضة كلاسيكية: نستهلك المزيد من الذاكرة (لتخزين النتائج) لنكسب وقتاً هائلاً في التنفيذ. في معظم الحالات، هذه مقايضة رابحة جداً.

الخلاصة: لا تُعِد اختراع العجلة… ولا حسابها! 💡

البرمجة الديناميكية ليست مجرد مفهوم أكاديمي معقد، بل هي أداة عملية قوية جداً في جعبة كل مبرمج. في قصتي، حولت هذه التقنية إحباطي إلى نجاح، وأنقذت مشروعي من الفشل. المبدأ بسيط للغاية: “إذا حسبت شيئاً، لا تنسَه!”.

سواء اخترت طريقة التخزين المؤقت (Top-Down) أو الجدولة (Bottom-Up)، فإنك تتبنى عقلية الكفاءة وتتجنب إضاعة موارد جهازك الثمينة في عمل متكرر لا طائل منه. في المرة القادمة التي تجد فيها أن برنامجك بطيء بشكل غير مبرر، توقف لحظة واسأل نفسك: “هل أنا مثل ذلك العامل الذي يهدم ويبني نفس الحائط مراراً وتكراراً؟”. إذا كانت الإجابة نعم، فقد حان الوقت لتدخل البرمجة الديناميكية وتنقذ الموقف.

أتمنى لكم كل التوفيق في رحلتكم البرمجية، ويعطيكم ألف عافية.