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

احسب مسبقا مرة واحدة

لماذا هذا مهم "إجمالي X بين نقطتين" هو أحد أكثر الأسئلة شيوعا في أكواد التقارير. الإجابة على كل سؤال عن طريق جمع النطاق عملية بطيئة؛ والاحتفاظ بإجمالي لكل نقطة قد يكون كبيرا جدا. هناك طريق بين الاثنين.

يحتفظ متجر

A ببيانات مبيعات لمدة 60,000 يوم في مخزن مقيد، يتم تسليمها إليك كـ Tape. يرسل قسم المالية دفعة من 50 سؤالا دفعة واحدة: "إجمالي المبيعات من اليوم a حتى اليوم b". أنت تعمل على عامل صغير بذاكرة احتياطية قليلة جدا.

المجموع التراكمي (prefix sum): هو مجموع كل العناصر قبل موضع معين. مجموع النافذة هو المجموع التراكمي عند نهايتها ناقص المجموع التراكمي عند بدايتها.

sales = [5, 1, 4, 2, 8]
# running totals before each position: 0, 5, 6, 10, 12, 20
# window (1, 4) = 12 - 5 = 7
دورك

اكتب range_totals(tape, queries). tape هي Tape للمبيعات اليومية (أعداد صحيحة). queries هي قائمة من أزواج (start, end) مع 0 <= start <= end <= len(tape). أعد قائمة بمجموع tape[start:end] لكل استعلام، بالترتيب المعطى. Budgets: اقرأ الشريط مرة واحدة كحد أقصى (60,100 قراءة لـ 60,000 يوم و50 استعلام)، واستخدم 100,000 بايت كحد أقصى من ذاكرة العمل أثناء تشغيل وظيفتك (مقاسة بواسطة tracemalloc؛ المجموع التراكمي لكل يوم، أو حتى قائمة بسيطة للقيم الـ 60,000، تتجاوز 100,000 بايت بكثير). تصل الأسئلة جميعها معاً، قبل أن تقرأ البيانات.

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

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

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