هياكل البيانات والخوارزميات / العقود والتسلسلات والبحث / الدرس 1
العقود والثوابت ونماذج الكلفة
أثبت ما تحسبه الحلقة، واحسب مقدار العمل الذي تنفذه، واذكر الافتراضات التي تقوم عليها ادعاءات التعقيد التقاربي.
في هذه الصفحة
أهداف الدرس
- صِف المشكلة قبل اختيار حاوية البيانات
- يربط ثابت الحلقة العمل الجزئي بالهدف
- احسب العمل من الحدود الفعلية للحلقات
صِف المشكلة قبل اختيار حاوية البيانات
تحتاج الخوارزمية إلى عقد للمدخلات، وعقد للنتيجة، ونموذج للموارد المستخدمة. فإيجاد أي زوج يحقق شرط المطابقة يختلف عن عد جميع الأزواج المطابقة، كما أن إرجاع مواضع العناصر يختلف عن إرجاع قيمها. حدّد هل تمثل القيم المتكررة سجلات مستقلة، وهل يُسمح بتعديل المدخلات. تؤثر هذه القرارات في صحة الحل وفي هياكل البيانات المناسبة له معا. تستخدم أمثلة هذه الدورة تسلسلات صغيرة مصطنعة بلغة Python 3، ونتائج محددة، دون خدمات خارجية. وتعد شروح التعقيد عادة المقارنات الأولية أو عمليات الوصول وفقا لنموذج كلفة الوحدة؛ أما حساب الأعداد الصحيحة الكبيرة والمقارنات المكلفة التي يعرّفها المستخدم فتحتاج إلى احتساب كلفتها الإضافية.
يربط ثابت الحلقة العمل الجزئي بالهدف
ثابت الحلقة خاصية تكون صحيحة قبل التكرار الأول، ويحافظ كل تكرار على صحتها. وينبغي أن تستلزم عند انتهاء الحلقة النتيجة الموعودة. يحافظ المثال الأول على أن total يساوي مجموع العناصر التي زارتها الحلقة بالفعل، دون غيرها، وأن visits يساوي عدد تلك العناصر. تعالج التهيئة السابقة الفارغة، وتمدد كل عملية جمع هذه السابقة بقيمة واحدة، وعند الانتهاء تشمل السابقة التسلسل كاملا. يفيد هذا الثابت أكثر من تعليق يقول «اجمع الأعداد»، لأنه يشرح لماذا لا يُهمل أي عنصر ولا يُعد مرتين، ويجعل نتيجة المدخل الفارغ واضحة صراحة.
def measured_sum(values):
total = 0
visits = 0
for value in values:
total += value
visits += 1
return total, visits
print(measured_sum([1, 2, 3, 4]))
print(measured_sum([]))
(10, 4)
(0, 0)
يعالج التكرار الواحد قيمة واحدة. ويساوي عدد الزيارات المحسوب طول المدخل؛ فهذا مثال لعد العمليات، وليس اختبارا معياريا لزمن التنفيذ.
احسب العمل من الحدود الفعلية للحلقات
يزور المثال الثاني كل زوج غير مرتب من موضعين مختلفين مرة واحدة. فإذا كان طول التسلسل n، كانت أعداد تكرارات الحلقة الداخلية n-1 ثم n-2 وصولا إلى الصفر، ومجموعها n(n-1)/2. وهذا نمو تربيعي، رغم عدم وجود عملية ضرب صريحة في البرنامج. يمنع الحد j > i اقتران العنصر بنفسه، ويمنع عد الزوج نفسه من المواضع بالترتيبين الممكنين. ومع ذلك تستطيع القيم المتكررة المشاركة في أزواج موضعية مختلفة. لذلك يتبع عدد المطابقات المعاد العقد المعلن القائم على المواضع؛ أما حذف التكرارات باستخدام مجموعة فيغير ذلك العقد.
def pair_counts(values, target):
checks = matches = 0
for i in range(len(values)):
for j in range(i + 1, len(values)):
checks += 1
if values[i] + values[j] == target:
matches += 1
return checks, matches
print(pair_counts([2, 4, 7, 9], 11))
print(pair_counts([5], 10))
(6, 2)
(0, 0)
الزوجان المطابقان هما زوج المواضع (0,3) وزوج المواضع (1,2). ولا تستطيع قيمة 5 منفردة أن تقترن بنفسها.
ميّز الحدود العليا والحدود المحكمة وحالات التحليل
يعطي الترميز Big O حدا أعلى تقاربيا، بينما تعبر Theta عن رتبة نمو يتطابق فيها الحدان الأعلى والأدنى وفقا للنموذج المختار. والخوارزمية الخطية هي أيضا O(n squared)، لذلك قد يكون الحد الأعلى الأوسع من اللازم صحيحا ولكنه غير مفيد. حدّد هل تقصد الحالة الأسوأ، أم الأفضل، أم المتوقعة، أم الكلفة المستهلكة، بدلا من استعمال هذه المفاهيم بالتبادل. قد يجعل الخروج المبكر أفضل حالة ثابتة الكلفة، مع بقاء أسوأ حالة خطية. ويعتمد السلوك المتوقع للتجزئة على افتراضات، ويختلف عن الكلفة المستهلكة لتغيير سعة المصفوفة الديناميكية. وسم دائما كمية المدخل التي تحللها: فعدد الرؤوس وعدد الحواف ليسا المتغير نفسه.
احسب الذاكرة والعمل الذي تخفيه عمليات اللغة
تحتاج قائمة نتيجة تحوي n قيمة إلى مساحة متناسبة مع n، حتى لو لم تستخدم الحلقة سوى متغيرين محليين. وتنشئ الشريحة عادة قائمة Python جديدة؛ ولذلك قد يضيف تكرار إنشاء الشرائح داخل العودية عملا للنسخ لا يظهر في علاقة عودية تعد المقارنات وحدها. كما أن استدعاء دالة مساعدة مرة واحدة في كل تكرار لا يجعل كلفة تلك الدالة ثابتة. احسب تمثيل المدخل وحجم الناتج والتخزين المساعد كلّا على حدة. ويمكن أن يزداد طول أعداد Python الصحيحة بالبتات، فتكون لجمع القيم الهائلة كلفة حسابية تتجاوز نموذج الكلمة ثابتة الحجم المبسط. اذكر النموذج المبسط الذي تستخدمه قبل تطبيقه.
استخدم الاختبارات للبحث عن أمثلة مضادة، مع بقاء البرهان لازما
اختبر المدخل الفارغ، والعنصر الواحد، والقيم المتكررة، والمواضع الحدية، ومثالا عاديا تختاره ليكشف عقد الحل. وحين يكون ذلك عمليا، قارن الخوارزمية الأسرع بتنفيذ مرجعي بسيط على جميع المدخلات ضمن نطاق صغير. توفر هذه المقارنة دليلا تفاضليا مفيدا، لكن مجموعة اختبارات محدودة لا تثبت الصحة لكل مدخل ممكن. اجمع الثوابت وحجج الانتهاء مع اختبارات تستطيع تمييز الأخطاء المحتملة. ولدرس النمو، عد العمليات قبل قياس فترات زمنية فعلية صغيرة قد تطغى عليها كلفة المفسر والجدولة. تتحقق الدورة من برامج محلية آمنة دون اختبارات تحميل أو موارد خارجية.
الأخطاء الشائعة وإصلاحها
وصف الحلقات المتداخلة بأنها خطية لأن كل سطر فيها بسيط
- لماذا يحدث؟
- لم يُجمع العدد الكلي للتكرارات.
- كيف تصلحه؟
- اشتق مجموع التكرارات من الحدود الفعلية للحلقات.
- كيف تتجنب تكراره؟
- عد العمليات لقيم صغيرة من n، وقارن العدد بالصيغة المشتقة.
استخدام الموضع نفسه مرتين في الزوج
- لماذا يحدث؟
- لم تُعبّر حدود الحلقات عن اشتراط اختلاف الموضعين.
- كيف تصلحه؟
- اشترط أن يكون j أكبر من i، أو استخدم قاعدة أخرى مبرهنة تضمن اختلاف الفهرسين.
- كيف تتجنب تكراره؟
- اختبر وجود قيمة واحدة تساوي نصف الهدف، بحيث تبدو مطابقة إذا استُخدمت مرتين.
إخفاء دالة مساعدة لعمليات نسخ خطية إضافية
- لماذا يحدث؟
- اقتصر حساب العمل على جسم الحلقة الظاهر.
- كيف تصلحه؟
- افحص كلف الدوال المساعدة وإنشاء الشرائح وتخصيص الذاكرة.
- كيف تتجنب تكراره؟
- اذكر نموذج الكلفة المصاحب للخوارزمية.
اختبر فهمك
1. ما الثابت الذي يثبت صحة measured_sum عندما تكون القائمة فارغة؟
اعرض الحل المشروح
قبل معالجة أي عنصر، يكون total مجموع السابقة الفارغة، أي صفرا، ويكون visits صفرا أيضا. لا تنفذ الحلقة أي تكرار، ولذلك يغطي ذلك الثابت المدخل كاملا بالفعل. وتنتج الإجابة (0,0) دون الحاجة إلى حالة خاصة استثنائية.
2. كم عملية فحص للأزواج تنفذها pair_counts لمدخل يحوي خمسة عناصر؟
اعرض الحل المشروح
تُنفذ 4+3+2+1+0=10 فحوص، بصرف النظر عن قيم الهدف، لأن الدالة لا تخرج مبكرا. وتعطي الصيغة خمسة في أربعة مقسومة على اثنين النتيجة نفسها. ويجب تمييز عدد الأزواج المطابقة من عدد العمليات المنفذة.
أهم ما تعلمته
- صِف المشكلة قبل اختيار حاوية البيانات
- استخدم الاختبارات للبحث عن أمثلة مضادة، مع بقاء البرهان لازما