المنهج الدراسي الدرس 55 من 148 · السرعة بدون cache
السرعة بدون cache

مؤشران، بدون جدول

لماذا هذا مهم "ابحث عن شيئين مجموعهما تساوي X" لها إجابة شهيرة: ضع كل شيء في set وابحث عن الشريك. هي سريعة، وتحتاج إلى نسخة من كل البيانات. عندما تكون البيانات مرتبة، لا تحتاج إلى ذاكرة تقريبًا على الإطلاق.

تبيع خدمة

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

prices = [1, 2, 3, 4, 5, 6]   # sorted, no repeats
count_pairs(Tape(prices), 7)    # 3: (1, 6), (2, 5), (3, 4)
دورك

اكتب count_pairs(tape, target). tape هي Tape لأسعار أعداد صحيحة، مرتبة تصاعديا، بدون تكرار. أعد عدد أزواج من عنصرين مختلفين مجموعهما يساوي target بالضبط (يتم حساب كل زوج مرة واحدة). Budgets: لـ 20,000 عنصر يقرأ بحد أقصى 60,000 قيمة، ويستخدم بحد أقصى 16,000 بايت من ذاكرة العمل أثناء تشغيل الدالة (يتم القياس باستخدام tracemalloc؛ مجموعة أو قائمة من الـ 20,000 سعر تتجاوز 150,000 بايت). len(tape) مجاني.

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

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

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