المنهج الدراسي الدرس 134 من 148 · اهزم شبحك
اهزم شبحك

بدون ذاكرة تخزين مؤقت: خصومات موروثة

لماذا هذا مهم "إنه يكرر العمل، لذا تذكر الإجابات" هي واحدة من أقوى العادات في البرمجة، سواء للبشر أو للذكاء الاصطناعي. أحيانا لا يحتاج العمل إلى التكرار على الإطلاق.

تشكل فئات متجر

A شجرة: تقع Garden تحت Home، وتتبع Tools تحت Garden، وهكذا. يمكن لمدير التسويق تحديد خصم على أي فئة، ويطبق الخصم على كل ما تحتها ما لم تحدد فئة أقرب خصما خاصا بها. يقوم checkout بالبحث عن الخصم الفعال لآلاف الفئات في وقت واحد.

البيانات

parents = {"home": None, "garden": "home", "tools": "garden", "seeds": "garden"}
own = {"garden": 10, "seeds": 25}           # discounts set directly, in percent
queries = ["tools", "seeds", "home"]
# effective_discounts(parents, own, queries) -> [10, 25, 0]

الحل البديهي للمشي المتكرر في الشجرة هو cache. في هذه المشكلة، يمنع استخدام caches. ابحث عن طريقة لا تكرر العمل من الأساس.

دورك

اكتب effective_discounts(parents, own, queries). تقوم parents بربط كل فئة بوالدها، أو None للفئة ذات المستوى الأعلى (قد يكون هناك عدة فئات، والقاموس ليس بترتيب معين). تقوم own بربط بعض الفئات بخصمها الخاص. لكل فئة في queries، أعد قيمة الخصم لأقرب فئة في مسارها نحو الأعلى، بدءا من الفئة نفسها، والتي تمتلك خصما في own؛ أو 0 إذا لم يوجد أي منها. قاعدة : لا يوجد تخزين مؤقت أو memo: لا تستخدم functools cache decorators، ولا أسماء تحتوي على "cache" أو "memo"، ولا تخرج الإجابات الصحيحة كما تطلبها الاستعلامات وتحتفظ بها (memo باسم آخر). قم بالمرور على الشجرة كاملة أولا، ثم اقرأ الاستعلامات. الميزانية: بحد أقصى 500,000 خطوة (steps()) لـ 3,000 فئة، وأشجار تصل إلى بضع مئات من المستويات، و20,000 عملية بحث.

هل لاحظت مشكلة في هذا الدرس؟ أبلغ عنها · اسأل عن هذا الدرس

سيفتح هذا التمرين قريبا

أنهِ الدرس السابق ليفتح هذا الدرس. الدورة كاملة مجانية، ولا تحتاج إلى حساب، ويمكنك قراءة هذا الدرس الآن.