Conteúdo do curso Lição 54 de 148 · Velocidade sem o cache
Velocidade sem o cache

Pré-computar uma vez

Por que isso importa "Total de X entre dois pontos" é uma das perguntas mais comuns em códigos de relatórios. Responder cada uma somando o intervalo é lento; manter um total para cada ponto pode ser grande demais. Existe um caminho entre os dois.

A loja

A mantém 60.000 dias de vendas em uma loja medida, entregue a você como um Tape. O Finance envia um lote de 50 perguntas de uma vez: "vendas totais do dia a até o dia b". Você roda em um worker pequeno com pouquíssima memória livre.

Total acumulado (soma prefixada): a soma de tudo antes de uma posição. O total de uma janela é o total acumulado no seu fim menos o total acumulado no seu início.

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

Escreva range_totals(tape, queries). tape é um Tape de vendas diárias (números inteiros). queries é uma lista de pares (start, end) com 0 <= start <= end <= len(tape). Retorne uma lista com o total de tape[start:end] para cada consulta, na ordem dada. Budgets: leia a fita no máximo uma vez (60,100 leituras para 60,000 dias e 50 consultas), e use no máximo 100,000 bytes de memória de trabalho enquanto sua função roda (medido com tracemalloc; um total acumulado para cada dia, ou até mesmo uma lista simples dos 60,000 valores, passa bem de 100,000 bytes). Todas as perguntas chegam juntas, antes de você ler os dados.

Viu um problema nesta lição? Reporte-o · Pergunte sobre esta lição

Este exercício abre em breve

Termine a lição anterior para que esta seja desbloqueada. O curso inteiro é gratuito, não precisa de conta, e você pode ler esta lição agora mesmo.