تعليقات توضيحية للتعقيد

  • 10 دقائق

يمكن استخدام التعليقات التوضيحية المعقدة لتأكيد أن كتلة من التعليمات البرمجية للطلاب تعمل ضمن مستوى معين من التعقيد. يحدد PyBryt تعقيد كتلة من التعليمات البرمجية للطالب من خلال مقارنة عدد خطوات التنفيذ لأطوال الإدخال المختلفة. ثم يستخدم المربعات الأقل لتحديد فئة التعقيد التي تمثل العلاقة على أفضل نحو.

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

يعد إنشاء التعليق التوضيحي أمرًا بسيطًا: ما عليك سوى إنشاء مثيل للفئة pybryt.TimeComplexity. يأخذ هذا التعليق التوضيحي كوسيطة له فئة التعقيد التي توفرها الوحدة pybryt.complexities:

>>> import pybryt.complexities as cplx
>>> cplx.complexity_classes
[pybryt.annotations.complexity.complexities.constant,
 pybryt.annotations.complexity.complexities.logarithmic,
 pybryt.annotations.complexity.complexities.linear,
 pybryt.annotations.complexity.complexities.linearithmic,
 pybryt.annotations.complexity.complexities.quadratic,
 pybryt.annotations.complexity.complexities.cubic]

TimeComplexity تتطلب الدالة name الإنشائية أيضا توفير الخيار، لأن هذا الخيار هو كيفية ربط البيانات من إرسال الطالب بالتعليز التوضيحي.

>>> pybryt.TimeComplexity(cplx.linear, name="foo")
pybryt.TimeComplexity

وهذا كل ما هو مطلوب في نهاية التطبيق المرجعي. يأتي العمل الحقيقي المتمثل في التحقق من التعقيد الزمني لتعليمات الطلاب البرمجية في كتابة الدعم المقدم للطلاب، والتي يجب أن تستخدم مدير سياق PyBryt check_time_complexity لتمييز كتلة من التعليمات البرمجية على أنها كتلة يجب التحقق منها لمعرفة مدى تعقيد الوقت. يقبل مدير السياق هذا اسم الكتلة (والذي يجب أن يكون هو نفسه name الذي تم توفيره في التعليق التوضيحي) كوسيطات وحجم المدخلات التي يتم تشغيلها في ذلك السياق.

على سبيل المثال، ضع في اعتبارك خوارزمية الأس الأساسية حيث يكون حجم الإدخال هو القوة التي يتم رفع القاعدة إليها.

def power(b, p):
    if p == 0:
        return 1
    return b * power(b, p - 1)

with pybryt.check_time_complexity("foo", 10):
    assert power(2, 10) == 2 ** 10

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

for p in [2, 5, 10, 15, 20]:
    with pybryt.check_time_complexity("foo", p):
        assert power(2, p) == 2 ** p

للتبسيط، إذا كان الإدخال الذي تقوم بتشغيله عنصرًا يدعم len لتحديد حجمه، يمكنك أيضًا تمرير الإدخال نفسه باعتباره الوسيطة الثانية:

l = [1, 2, 3]
with pybryt.check_time_complexity("bar", l):
    sort(l)

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

‏‫اختبر معلوماتك

1.

لنفترض أن لدينا كتلة تعقيد الوقت التالية:

with pybryt.check_time_complexity("fib", 100):
    fib(100)

أي من التعبيرات التالية تنشئ تعليقًا توضيحيًا يمكن استخدام الكتلة أعلاه معه؟

2.

أي من التعبيرات التالية ينشئ تعليقًا توضيحيًا يؤكد أن كتلة من التعليمات البرمجية تعمل في الوقت اللوغاريتمي أو الخطي؟