سرفصل‌ها درس 54 از 148 · سرعت بدون کش
سرعت بدون کش

یک‌بار پیش‌محاسبه کنید

چرا اهمیت دارد: «مجموع X بین دو نقطه» یکی از رایج‌ترین پرسش‌ها در کد گزارش‌گیری است. پاسخ دادن به هر یک با جمع کردن بازه کند است؛ نگهداری مجموع برای هر نقطه می‌تواند حجم زیادی بگیرد. راهی میان این دو وجود دارد.

یک فروشگاه ۶۰٬۰۰۰ روز فروش را در یک فروشگاه دارای کنتور نگهداری می‌کند که به شما به‌عنوان یک Tape. بخش مالی یک دسته ۵۰ تایی از سوالات را یکجا ارسال می‌کند: «مجموع فروش از روز a تا روز b». شما روی یک کارگر کوچک با حافظهٔ آزاد بسیار کم اجرا می‌کنید.

جمع جاری (جمع پیش‌رونده): مجموع همه چیزها قبل از یک موقعیت. مجموع یک پنجره، برابر است با جمع جاری در انتهای آن منهای جمع جاری در شروع آن.

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] برای هر پرس‌وجو، به ترتیبی که داده شده است. بودجه‌ها: حداکثر یک‌بار نوار را بخوانید (۶۰٬۱۰۰ بار خواندن برای ۶۰٬۰۰۰ روز و ۵۰ پرس‌وجو)، و در حین اجرای تابع خود حداکثر از ۱۰۰٬۰۰۰ بایت حافظهٔ کاری استفاده کنید (اندازه‌گیری شده با tracemalloc؛ یک مجموع جاری برای هر روز، یا حتی یک لیست ساده از ۶۰٬۰۰۰ مقدار، به مراتب بیش از ۱۰۰٬۰۰۰ بایت است). تمام سوالات قبل از خواندن داده‌ها به طور همزمان دریافت می‌شوند.

مشکلی در این درس دیدید؟ گزارشش کنید · دربارهٔ این درس بپرسید

این تمرین به‌زودی باز می‌شود

درس پیش از آن را تمام کنید تا این یکی باز شود. کل دوره رایگان است، حساب کاربری لازم نیست، و می‌توانید همین الان این درس را بخوانید.