Armazenando um vetor de bits na memória não inicializada e espaço mínimo

Um truque conhecido para armazenar vetores de bits usando memória não inicializada pode alocar um vetor de bits de tamanho no qual todos os bits são definidos como , alocando bits de memória e inicializando apenas deles. Essa representação suporta a configuração e a desabilitação de qualquer bit em tempo constante. $n$ $0$ $(2 n + 1)\lceil \lg n \rceil$ $\lceil \lg n \rceil$

Isso remonta a "O livro de 1974 de Alfred Aho, John Hopcroft e Jeffrey Ullman, The Design and Analysis of Computer Algorithms ... Capítulo 2, exercício 2.12", "O livro de Jon Bentley, 1986, Programming Pearls ... .Coluna 1, exercício 8; exercício 9 na segunda edição "e " artigo de Preston Briggs e Linda Torczon de 1993, 'Uma representação eficiente para conjuntos esparsos' " .

"Mudando a base sem perder espaço", de Dodis et al., um pouco o requisito de espaço para bits, embora esse algoritmo exija a pré-computação de constantes com bits cada. $\lceil (2 n + 1) \lg n \rceil + 1$ $\Theta(\lg n)$ $\Theta(\lg n)$

Quanto espaço pode ser economizado? Existe uma representação de vetores de bits em que

Os bits pode ser activado ou desactivado em hora $O(1)$
A inicialização de um novo vetor de bits de s usa bits de memória não inicializada e memória inicializada $0$ $o(n \lg n)$ $O(\lg n)$

ds.data-structures space-bounded space-time-tradeoff space-complexity jbapple
fonte

Respostas:

Sim, isso pode ser feito através do balde . A representação em Briggs e Torczon pode ser usada para armazenar não apenas bits, mas valores associados a qualquer conjunto de bits, armazenando-os próximos aos valores na matriz densa. Para valores de bits , isso leva a um custo total de armazenamento de . $k$ $(2n+1)\lceil \lg n \rceil + kn$

Agora escolha . Cada valor bit irá representar um conjunto de bits contíguos na matriz de bits. Portanto, precisamos apenas rastrear deles com as matrizes densas e esparsas. Isso leva a um custo total de bits de armazenamento, com bits inicializados. $k=\lceil \lg n \rceil$ $k$ $\lceil \lg n \rceil$ $\lceil n/\lceil \lg n \rceil \rceil$ $\Theta(n)$ $\Theta(\lg n)$

Como a solução básica, isso requer operações com palavras de comprimento para definir um único bit. $O(1)$ $\Theta(\lg n)$

jbapple
fonte