Inicialize a matriz em tempo constante amortizado - como é chamado esse truque?

Existe essa estrutura de dados que negocia o desempenho do acesso ao array contra a necessidade de iterar sobre ele ao limpá-lo. Você mantém um contador de geração em cada entrada e também um contador de geração global. A operação "limpa" aumenta o contador de geração. Em cada acesso, você compara os contadores de geração local versus global; se eles diferem, o valor é tratado como "limpo".

Isso apareceu nesta resposta recentemente no Stack Overflow , mas não me lembro se esse truque tem um nome oficial. Faz isso?

Um caso de uso é o algoritmo de Dijkstra, se apenas um pequeno subconjunto dos nós precisar ser relaxado e se for necessário repetidamente.

algorithms terminology krlmlr
fonte

Truque interessante, mas tem uma sobrecarga. Então, eu me pergunto quais usos limpar a matriz como uma operação tão comum que o preço paga? (Pergunta sincera!)

Joachim Sauer

@JoachimSauer: Editado.

krlmlr

Parece muito caro, no caso geral, tanto para uso de memória quanto para custos de acesso. O caso de uso para esta técnica deve ser muito específico.

Martin York

@ Joachim: É usado para limpar rapidamente os buffers para renderização - aproximadamente. Eles só têm um "bit claro" por 64kb ou algo assim.

DeadMG

@ user946850 "amortizado" significa que você pode provar que uma operação cara acontece raramente suficiente no quadro geral que não contribuem com mais de eg O (1)

Respostas:

A abordagem mencionada acima exige que cada célula seja capaz de manter um número grande o suficiente para manter o número de vezes que a matriz pode precisar ser reinicializada, o que é uma penalidade de espaço substancial. Se um slot é capaz de armazenar pelo menos um valor que nunca será legitimamente gravado, é possível evitar qualquer outra penalidade de espaço (não constante) às custas da adição de uma O(Wlg(N))penalidade de tempo, onde Wé o número de slots de matriz distintos gravados entre operações de limpeza e Né o tamanho da matriz. Por exemplo, suponha que alguém armazene números inteiros de -2.147.483.647 a 2.147.483.647 (mas nunca -2.147.483.648) e deseje que os itens da matriz em branco sejam lidos como zero. Comece preenchendo a matriz com -2.147.483.648 (chame esse valorB) Ao ler um slot de matriz para o aplicativo, relate um valor Bigual a zero. Antes de escrever slot de gama I, verifique se realizou Be se assim e Ié maior que um, armazenar um zero a ranhura I/4após a realização de uma verificação semelhante para esse local (e, se realizada B, I/16, etc).

Para limpar a matriz, comece com Iigual a 0 ou 1, dependendo da base da matriz (o algoritmo conforme descrito funcionará para ambos). Repita o procedimento a seguir: Se item Ifor B, incremente Ie, se isso resultar em um múltiplo de quatro, divida por quatro (termine se a divisão gerar um valor de 1); se o item Inão estiver B, armazene B-o e multiplique-o Ipor quatro (se Icomeçar em zero, multiplicar por quatro deixará zero, mas como o item 0 ficará em branco, Iserá incrementado).

Observe que é possível substituir a constante "quatro" acima por outros números, com valores maiores geralmente exigindo menos marcação de trabalho, mas valores menores geralmente exigindo menos compensação de trabalho; como os slots de matriz marcados precisam ser limpos, um valor de três ou quatro é quase certamente ideal; como o valor quatro certamente está próximo do ideal, é melhor que dois ou oito e é mais conveniente do que qualquer outro número, parece a escolha mais razoável.

supercat
fonte

É suficiente ter um contador de versão capaz de acomodar redefinições sequenciais suficientes antes que todas as células sejam atualizadas com novos valores. Na prática, um byte pode ser suficiente ou até menos em loops mais apertados.

9000

@ 9000: O código que se baseia em tal comportamento pode ser frágil, especialmente porque a única razão para usar uma abordagem 'pseudo-clara' (em vez de simplesmente limpar a matriz) seria se o conjunto de itens que seria necessário ser limpo normalmente era pequeno e variável - um par de condições que conspiram para aumentar a probabilidade de um item ser usado, "limpo" e depois permanecer intocado por um período arbitrariamente longo. Pode-se considerar a varredura da matriz e a limpeza física de todos os slots antigos quando o contador for encapsulado, mas ... #

307

... se o valor de quebra automática do contador for constante, a quantidade média de trabalho para cada operação de limpeza da matriz seria O (N), com N sendo o tamanho da matriz. Não que tal coisa possa não ser útil na prática, pois uma implementação de O (N) acelerada por um fator de 65.536 ainda seria O (N), mas também seria 65.536 vezes mais rápida que a não aprimorada . Aliás, os casos em que essas abordagens seriam úteis também podem se beneficiar do uso de uma estrutura de dados de matriz esparsa, que poderia usar o espaço O (AlgN) para armazenar uma matriz com uma matriz do tamanho N com elementos A não vazios.

22712

Eu chamaria isso de "reinicialização de célula de matriz lenta", mas parece não ter nenhum nome estabelecido (ou seja, o nome está sendo amplamente utilizado).

O algoritmo é inteligente, mas muito especializado e aplicável em uma área muito estreita.

Aleksander Adamowski
fonte

Eu acredito que é um caso especial de memorização , exceto neste caso, os "memorandos" implicitamente "envelhecem" a cada incremento do contador global. Eu acho que uma espécie de "memorização reversa".

descongelar
fonte