Reduzir buscas repetidas com índices em memória

Imagine um catálogo com n registros de produtos. Seu programa recebe m consultas: algumas procuram um código, outras uma categoria.

Uma busca sequencial pode parecer barata isoladamente. Mas, se cada consulta percorre novamente o catálogo, a mesma coleção é lida muitas vezes. Como visto no perfilamento, uma operação pouco cara por chamada pode concentrar tempo quando é chamada em grande quantidade.

Cada seta representa uma consulta que começa novamente no catálogo.

Cada chamada pode examinar o catálogo inteiro.

Aqui, n é a quantidade de produtos no catálogo e m é a quantidade de códigos consultados. No pior caso, cada uma das m consultas examina n registros: O(mn).

O trabalho efetivo varia: um produto no início encerra a busca cedo; um produto no fim exige mais comparações; uma ausência percorre toda a fonte. Ainda assim, repetir varreduras é a hipótese importante a investigar.

Quando muitas consultas usam a mesma fonte durante um período, vale considerar uma organização auxiliar por chave criada uma vez e reutilizada nas consultas.

A intenção não é eliminar o custo: a preparação percorre a fonte e ocupa memória adicional. A possível vantagem é evitar que cada nova consulta recomece a varredura completa. Nos próximos passos, você construirá as estruturas adequadas para cada tipo de pergunta.

Quando cada consulta só precisa responder “este código existe?”, extraia os códigos do catálogo para um set antes do laço de consultas. Assim, a coleção original não precisa ser percorrida novamente para cada código perguntado.

O conjunto guarda somente as chaves distintas necessárias para responder à pergunta de presença.

Cada consulta usa in no mesmo conjunto já preparado.

O conjunto responde se uma chave está presente. Ele não informa quantas vezes o código apareceu nem qual produto estava associado a ele. Para este uso, a chave extraída ao construir o conjunto deve seguir o mesmo critério usado na consulta — por exemplo, o mesmo código normalizado.

Quando cada produto tem um código único, construa um dicionário que associe cada código ao seu registro. A construção percorre o catálogo uma vez; depois, várias consultas reutilizam o mesmo índice.

A chave do índice deve representar o mesmo critério da busca original. Se a busca comparava produto["codigo"] == codigo_consultado, use exatamente produto["codigo"] como chave.

A compreensão cria o índice fora do laço de consultas. A hipótese de códigos únicos faz parte do contrato deste exemplo.

Uma consulta pode exigir comportamentos diferentes para um código que não está no catálogo:

• usar por_codigo.get(codigo) para retornar um padrão, como None;
• testar if codigo in por_codigo quando for preciso distinguir presença;
• acessar por_codigo[codigo] quando o contrato determina que a ausência deve sinalizar KeyError.

Escolha o comportamento que a busca anterior já prometia ao restante do programa.

Aqui, None é um valor válido do campo preco_promocional. Por isso, get sozinho não permite saber se o código existe.

Um índice chave → registro funciona quando a chave é única. Se ela puder se repetir, a atribuição posterior substitui a anterior. Portanto, o índice pode mudar o resultado da busca, mesmo que a consulta pareça mais rápida.

Compare o efeito de indexar produtos que compartilham a mesma categoria.

Quando a busca original retorna todos os produtos de uma categoria, construa um dicionário de listas. Ao percorrer a fonte sequencialmente e usar append, cada lista preserva a ordem em que aqueles registros apareciam na fonte.

Cada categoria aponta para todos os produtos correspondentes.

Localizar a lista de uma categoria no dicionário tem custo médio esperado constante. Porém, se a aplicação precisar percorrer, copiar ou exibir os itens encontrados, esse trabalho cresce com a quantidade de registros do grupo. Uma consulta que retorna 500 produtos ainda precisa lidar com 500 resultados.

Um dicionário usado como índice é uma estrutura auxiliar: ele não acompanha automaticamente inserções, remoções ou substituições feitas na lista de produtos.

Se você construiu por_codigo e depois alterou a fonte, faça uma pergunta antes de consultar: o índice ainda representa o estado que deve ser pesquisado?

Quando o índice guarda referências aos mesmos dicionários da fonte, alterar um campo não indexado é visível pela consulta: a referência continua sendo a mesma.

Já substituir um item da lista por outro dicionário não troca a referência guardada no índice. E alterar a própria chave exige atualizar o mapeamento, mesmo que o objeto seja compartilhado.

Execute este exemplo localmente para observar o índice antes e depois da alteração.

Atualize incrementalmente quando cada alteração é conhecida, pequena e simples de refletir no índice. Reconstrua quando houve um lote de mudanças, remoções e substituições, ou quando conferir todos os vínculos seria mais complexo e arriscado.

Defina um período de validade: construa ou atualize o índice antes do conjunto de consultas que precisa enxergar dados atuais. Um índice pode ser reutilizado apenas enquanto sua fonte permanecer compatível com ele.

Considere n registros na fonte e m consultas exatas.

• Sem índice, cada consulta pode varrer até n registros: O(mn).
• Com conjunto ou dicionário, construa o índice uma vez: O(n) esperado; depois faça m consultas: O(m) esperado. Total: O(n + m) esperado.

Isso pressupõe chaves com hashing e igualdade de custo limitado, além de uma tabela hash com comportamento médio esperado. O índice não elimina o custo de produzir a resposta.

A construção só é amortizada pelas consultas feitas enquanto o índice continua válido. Em um uso único, o custo de construir — e talvez manter — o índice pode não compensar uma varredura simples. Em muitas consultas sobre a mesma fonte estável, esse custo inicial é dividido entre elas.

Não existe um número universal de consultas a partir do qual o índice vence: depende de n, m, distribuição das buscas, tamanho das respostas, custo das chaves, manutenção e memória disponível.

Se u é o número de chaves distintas:

• Um conjunto de chaves ou um dicionário com um registro por chave usa memória auxiliar estrutural O(u).
• Um dicionário de listas que agrupa todos os n registros usa O(u + n): há chaves/grupos e referências para os registros em cada grupo.

A fonte e o índice coexistem. Guardar uma referência ao registro não cria uma cópia integral dele, mas a tabela, as listas e as próprias referências ainda ocupam memória. Essas ordens e contagens não informam, sozinhas, o total real em bytes.

Use uma carga sintética determinística: o catálogo contém produtos repetidos por categoria, e as consultas incluem categorias presentes, ausentes e repetidas. Primeiro, confirme que as duas estratégias produzem exatamente o mesmo resultado.

Depois, compare quatro medidas: varrer o lote inteiro; construir e consultar no mesmo lote; consultar um índice já pronto; e construir isoladamente. A terceira medida representa reutilização. Sozinha, ela não responde se o investimento de construir o índice compensou para um único lote.

Crie um arquivo chamado comparar_indices.py, copie o código abaixo e execute python comparar_indices.py. Ele usa somente a biblioteca padrão. O assert vem antes das medições porque tempo menor não serve se o contrato de resultado mudou.

Não troque a carga de consultas entre versões para favorecer uma estratégia. Ambas precisam processar as mesmas ausências, repetir as mesmas consultas e consumir todos os registros de cada grupo retornado. Se você alterar a fonte, reconstrua ou atualize o índice antes de reutilizá-lo.

A estrutura deve reproduzir o contrato da consulta antes de buscar velocidade:

• Varredura: adequada para poucas consultas, fonte pequena ou quando a preparação não se paga.
• Conjunto (set): responde apenas se uma chave existe.
• Dicionário simples (dict): recupera um registro por chave, quando a política para chaves repetidas está definida.
• Dicionário de listas: recupera todos os registros de uma chave repetida, preservando a ordem de inserção da fonte em cada grupo.

A decisão final inclui o tempo de construção, as consultas durante a validade do índice, a memória auxiliar e o comportamento para duplicatas, ausências e ordem.

Compare o que cada estrutura consegue responder sem perder informação necessária.

No seu script local do step anterior, escolha uma configuração de carga que você mediu. Em seguida, altere a fonte e atualize ou reconstrua o índice antes de repetir a consulta. O exemplo abaixo usa reconstrução: uma opção simples e segura após um lote de alterações.

Adapte os nomes das chaves ao seu catálogo local.