Trade-off Espaço-Tempo

Em ciência da computação, especificamente em informática teórica, se estuda o quanto de espaço em memória e tempo determinados algoritmos utilizam. Para fins didáticos e teóricos, muitos problemas são considerados solúveis, mas na prática tomariam bastante tempo para serem solucionados. Utiliza-se análise assintótica, que "estipula" o quão rápido a quantidade de uso daquele recurso (tempo ou espaço, no contexto de computação) cresce em proporção ao crescimento do tamanho da entrada, para, dessa forma, comparar as soluções de um dado problema pelo potencial de complexidade, e não apenas casos isolados do uso destas soluções. O problema é que, na teoria, as máquinas de Turing têm memória infinita, e consideramos que alguns processos genéricos são rápidos se durassem até um polinômio no tamanho da entrada, mas polinômio podem representar quantidades realmente grandes, e nossos recursos de memória em computadores são finitos. Daí a importância de se dosar a relação "espaço-tempo" de forma a se ter um trade-off entre essas duas grandezas e otimizar execução e resultado.

• Espaço se refere ao armazenamento de dados consumido na execução de um dado algoritmo, seja no armazenamento primário (e.g., na memória RAM) ou no armazenamento secundário (e.g., em um disco rígido). Em informática teórica, isto é analisado pelo ponto de visto de consumo (escrita, e não leitura) das células na(s) fita(s) de uma máquina de Turing. Um exemplo de conceito proveniente deste estudo é a definição de PSPACE.
• Tempo se refere à quantidade de passos ao executar um algoritmo, tema estudado em complexidade de tempo. Esta análise se dá na observação do aumento do tempo para execução de um algoritmo de acordo com o tamanho da sua entrada, i.e., quanto maior sua entrada como se comporta em função do tempo o algoritmo.

Tanto na análise de complexidade de tempo e espaço existem métricas para se estudar vários casos. Essas métricas se dão pelo uso de notações como Grande-O e Complexidade do caso médio.

Trade-off espaço-tempo é um caso onde um algoritmo ou software compensa o aumento no consumo de memória levando menos tempo. A utilidade de um balanço entre espaço e tempo é afetado por custos fixos e variáveis, como velocidade da unidade de processamento, espaço na memória primária e secundária. Numa analogia, é sujeito a Lei dos rendimentos decrescentes (em inglês, diminishing returns).

História

Na natureza, o uso do trade-off espaço-tempo pode ser encontrado nos primeiros estágios do comportamento animal. O conhecimento adquirido e reações codificadas geneticamente evitam a necessidade de se "calcular" analiticamente este balanço em situações críticas. Mais especificamente para computadores, memorização tem sido implementada desde os mais antigos sistemas operacionais.

Em 1980 Martin Hellman propôs o uso de um trade-off espaço-tempo para Criptoanálise.

Tipos de tradeoff

Tabelas de busca vs. re-calculação

A situação mais comum é um algoritmo envolvendo um Look-up-table, que é uma técnica utilizada no tratamento de imagens. Uma imagem pode ser representada por uma tabela de valores, e, a técnica de LUT é responsável pela tabela da imagem após o tratamento. Uma implementação pode incluir uma tabela inteira, que reduz o tempo computacional, mas aumenta a quantidade de memória necessária, ou pode-se computar partes das tabelas, aumentando o tempo, mas reduzindo o custo em memória.

Dados compactados vs. Dados descompactados

Um trade-off espaço-tempo pode ser aplicado ao problema de armazenamento de dados. Se dados são armazenados descompactados, utiliza-se mais espaço, porém menos tempo para ser utilizado do que se estiverem compactados. Pois a compactação de dados reduz o seu tamanho armazenado mas temos o custo adicional, over-head, de rodar o algoritmo de descompactação de dados. Essa escolha depende de vários fatores, indo na raiz, no problema, pode depender das instancias, por exemplo, alguns algoritmos trabalham com dados compactados. Um exemplo deste caso é dos índices bitmap, onde é mais rápido se trabalhar com dados compactados.

Re-renderização vs. imagens armazenadas

Armazenando apenas o código LaTex e renderizando isso como uma imagem várias vezes a página requisitada estaria trocando tempo for espaço; mais tempo usado, porém, menos espaço. Renderizando uma imagem quando a página é modificada e armazenando as imagens renderizadas seria uma troca de espaço por tempo; mais espaço usado, porém, menos tempo. Essa técnica é comumente conhecida como cache.

Código menor vs. relaxamento de loop

Códigos grandes podem ser trocados por programas mais velozes quando aplicada a técnica de desaninhamento de loopsrelaxamento de ''loop''. Essa técnica faz o código ficar mais para longo cada iteração de um dado loop, mas salva o tempo computacional que seria utilizado em um controle de loop em cada iteração, i.e., reduzindo uma tarefa de cada iteração, a tarefa de verificar se aquele loop deve parar ou continuar. Claramente, esta técnica só pode ser utilizada em casos específicos, e há um trade-off entre espaço e tempo. Onde, neste caso, o espaço talvez não seja tão importante pelo fato de que normalmente os programas não ocuparem tanto espaço, mas compromete outros aspectos como a legibilidade.

Outros exemplos

Algoritmos que também fazem uso de trade-off espaço-tempo inclui:

• Passo-de-bebê passo-gigante Baby-step giant-step, um algoritmo para calcular logaritmos discretos.
• Tabelas arco-ires Rainbow table, em criptografia, numa situação onde o hacker quer fazer um ataque que seja mais rápido, menos custo de tempo computacional, que um ataque de força bruta. Rainbow Tables usam valores parcialmente pré-computados de hashes de uma função de criptografia hash para recuperar senhas, por exemplo. Decrescendo o tamanho da Rainbow table o tempo necessário para iterar sobre as alternativas aumenta.
• O ataque do homem no meio, usa um trade-off espaço-tempo para encontrar a chave criptográfica em apenas

$2^{n+1}$ encriptações (e $O(2^{n})$ de custo computacional de espaço) contra o esperado $2^{2n}$ encriptações (mas apenas $O(1)$ de custo computacional de espaço) de um ataque ingênuo.

• Programação dinâmica, onde a complexidade de tempo de um problema pode ser reduzido significantemente usando mais memória.

Ver também

• Teorema da aceleração de Blum
• Teorema de Savitch

Ligações externas

• Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off.
• Once Upon a Time-Memory Tradeoff.