Программа курса Урок 54 из 148 · Скорость без кэша
Скорость без кэша

Предвычислите один раз

Почему это важно "Сумма X между двумя точками" - один из самых частых вопросов в коде отчётов. Отвечать на каждый, складывая диапазон, медленно; хранить сумму для каждой точки может оказаться слишком объёмно. Между этими двумя есть путь.

Магазин хранит 60 000 дней продаж в хранилище с учётом чтений, и они даются вам как Tape. Финансовый отдел присылает пакет из 50 вопросов сразу: "сумма продаж с дня 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] для каждого запроса в данном порядке. Бюджеты: прочитать ленту не больше одного раза (60 100 чтений для 60 000 дней и 50 запросов) и использовать не больше 100 000 байт рабочей памяти, пока работает функция (измеряется через tracemalloc; накопленная сумма для каждого дня или даже простой список из 60 000 значений - намного больше 100 000 байт). Все вопросы приходят вместе, до того как вы читаете данные.

Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке

Это упражнение откроется скоро

Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.