Espaço-tempo tradeoff - Space–time tradeoff
Um espaço-tempo ou tempo de memória trade-off em ciência da computação é um caso em que um algoritmo ou programa comércios aumentou o uso do espaço com a diminuição do tempo. Aqui, o espaço refere-se ao armazenamento de dados consumido na realização de uma determinada tarefa ( RAM , disco rígido , etc.), e tempo refere-se ao tempo consumido na realização de uma determinada tarefa ( computação tempo ou tempo de resposta ).
A utilidade de uma dada compensação espaço-tempo é afectada por relacionados fixos e custos variáveis (de, por exemplo, CPU velocidade, o espaço de armazenamento), e é sujeito a rendimentos decrescentes .
Conteúdo
História
Uso biológica de compensações de memória tempo pode ser visto nas etapas anteriores do comportamento animal . Usando o conhecimento armazenado ou codificação reações estímulos como "instintos" no DNA evita a necessidade de "cálculo" em situações de tempo crítico. Mais específico para computadores, tabelas look-up foram implementados desde os sistemas operacionais muito mais rapidamente.
Em 1980 Martin Hellman proposto pela primeira vez usando um tradeoff-memory tempo para criptoanálise .
Tipos de troca
tabelas de pesquisa vs. recálculo
A situação mais comum é um algoritmo que envolve uma tabela de pesquisa : uma implementação pode incluir a tabela inteira, o que reduz o tempo de computação, mas aumenta a quantidade de memória necessária, ou pode computar entradas da tabela, conforme necessário, aumentando o tempo de computação, mas reduzindo os requisitos de memória .
Comprimida contra dados não comprimida
Uma desvantagem espaço-tempo pode ser aplicada ao problema de armazenamento de dados. Se os dados são armazenados descompactado, é preciso mais espaço, mas o acesso leva menos tempo do que se os dados foram armazenados compactado (desde comprimir os dados reduz a quantidade de espaço que ocupa, mas isso leva tempo para executar o algoritmo de descompressão ). Dependendo do caso particular do problema, de qualquer forma é prático. Há também casos raros onde é possível trabalhar diretamente com dados compactados, como no caso do comprimido índices bitmap , onde ele é mais rápido para trabalhar com compressão do que sem compressão.
Re-rendering vs. imagens armazenadas
Armazenar apenas o SVG fonte de uma imagem vetorial e tornando-o como uma imagem bitmap cada vez que a página é solicitada estaria trocando tempo para o espaço; mais tempo utilizado, mas menos espaço. Tornando a imagem quando a página é alterado e armazenar as imagens renderizadas seria negociar espaço para tempo; mais espaço utilizado, mas menos tempo. Esta técnica é mais geralmente conhecido como cache .
código menor comparada desdobramento de loop
O tamanho do código maior pode ser trocado por uma velocidade maior programa ao aplicar circuito desenrolar . Esta técnica torna o código mais longo para cada iteração de um loop, mas poupa o tempo de computação necessário para saltar de volta para o início do loop no final de cada iteração.
outros exemplos
Algoritmos que também fazem uso de compensações de espaço-tempo incluem:
- Bebê-passo gigantesco passo algoritmo para calcular logaritmos discretos
- Tabelas do arco-íris em criptografia, onde o adversário está tentando fazer melhor do que o tempo exponencial necessário para um ataque de força bruta . Rainbow tables usar valores parcialmente pré-computadas no espaço de hash de uma função hash de criptografia para quebrar senhas em minutos em vez de semanas. Diminuir o tamanho da tabela de arco-íris aumenta o tempo necessário para iterar sobre o espaço hash.
- O ataque meet-in-the-middle usa uma troca de espaço-tempo para encontrar a chave criptográfica em apenas criptografias (e espaço) versus os esperados criptografias (mas só espaço) do ataque ingênuo.
- Programação dinâmica , onde a complexidade de tempo de um problema pode ser reduzido significativamente usando mais memória.
