Procurando uma implementação definida com pouco espaço na memória

Estou procurando a implementação do tipo de dados definido. Ou seja, temos que

• mantenha um subconjunto dinâmico $S$ (de tamanho $n$ ) do universo $U = \{0, 1, 2, 3, \dots , u – 1\}$ de tamanho $u$ com
• operações insert(x)(adicione um elemento xa $S$ ) e find(x)(verifica se o elemento xé um membro de $S$ ).

Eu não me importo com outras operações. Para orientação, em aplicações estou trabalhando com temos $u \approx 10^{10}$ .

Conheço implementações que fornecem ambas as operações no tempo $O(1)$ , então me preocupo principalmente com o tamanho da estrutura de dados. Espero bilhões de entradas, mas quero evitar trocar o máximo possível.

Estou disposto a sacrificar o tempo de execução, se necessário. Tempo de execução amortizado de $O(\log n)$ é o que posso admitir; os tempos de execução esperados ou em não são admissíveis.$\omega(\log n)$

Uma idéia que tenho é que, se puder ser representado como uma união de intervalos , poderemos economizar no tamanho do armazenamento com o preço de alguma diminuição no desempenho. Além disso, alguns outros padrões de dados são possíveis, como .$S$[xmin, xmax][0, 2, 4, 6]

Você poderia me indicar estruturas de dados que podem fazer algo assim?

A resposta de Joe é extremamente boa e fornece todas as palavras-chave importantes.

Você deve estar ciente de que a pesquisa sucinta da estrutura de dados ainda está em um estágio inicial e muitos dos resultados são amplamente teóricos. Muitas das estruturas de dados propostas são bastante complexas de implementar, mas a maior parte da complexidade se deve ao fato de que você precisa manter a complexidade assintótica tanto no tamanho do universo quanto no número de elementos armazenados. Se um deles for relativamente constante, grande parte da complexidade desaparece.

Se a coleção for semi-estática (ou seja, as inserções são raras ou, pelo menos, de baixo volume), certamente vale a pena considerar uma estrutura de dados estática fácil de implementar (o sdarray de Sadakane é uma ótima opção) em conjunto com uma atualização cache. Basicamente, você registra atualizações em uma estrutura de dados tradicional (por exemplo, árvore B, árvore, tabela de hash) e atualiza periodicamente em massa a estrutura de dados "principal". Essa é uma técnica muito popular na recuperação de informações, pois os índices invertidos têm muitas vantagens na pesquisa, mas são difíceis de atualizar no local. Se for esse o caso, informe-me em um comentário e alterarei esta resposta para fornecer algumas dicas.

Se as inserções são mais frequentes, sugiro hash sucinto. A idéia básica é direta o suficiente para explicar aqui, então farei isso.

Portanto, o resultado teórico da informação básica é que, se você estiver armazenando elementos de um universo de u itens, e não houver outras informações (por exemplo, nenhuma correlação entre os elementos), precisará logar ($n$$u$bits para armazená-lo. (Todos os logaritmos são de base 2, a menos que especificado de outra forma.) Vocêprecisa detantos bits. Não há maneira de contornar isso.$\log {u \choose n} + O(1)$

Agora, alguma terminologia:

• Se você possui uma estrutura de dados que pode armazenar os dados e apoiar suas operações no bits de espaço, chamamos isso deestrutura de dadosimplícita.$\log {u \choose n} + O(1)$
• Se você possui uma estrutura de dados que pode armazenar os dados e apoiar suas operações no bits de espaço, chamamos isso de umaestrutura de dadoscompacta. Observe que, na prática, isso significa que a sobrecarga relativa (relativa ao mínimo teórico) está dentro de uma constante. Pode ser 5% de sobrecarga, 10% de sobrecarga ou 10 vezes de sobrecarga.$\log {u \choose n} + O(\log {u \choose n}) = (1 + O(1)) \log {u \choose n}$
• Se você possui uma estrutura de dados que pode armazenar os dados e apoiar suas operações no bits de espaço, chamamos isso deestrutura de dadossucinta.$\log {u \choose n} + o(\log {u \choose n}) = (1 + o(1)) \log {u \choose n}$

A diferença entre sucinto e compacto é a diferença entre pequeno-oh e grande-oh. Ignorando o valor absoluto por um momento ...

• significa que existe uma constante c e um número n 0 tal que para todos n > n 0 , g ( n ) < c ⋅ f ( n ) .$g(n) = O(f(n))$$c$$n_0$$n > n_0$$g(n) < c \cdot f(n)$
• significa que para todas as constantes c existe um número n 0 tal que para todas as n > n 0 , g ( n ) < c ⋅ f ( n ) .$g(n) = o(f(n))$$c$$n_0$$n > n_0$$g(n) < c \cdot f(n)$

Informalmente, big-oh e little-oh estão "dentro de um fator constante", mas com big-oh a constante é escolhida para você (pelo criador do algoritmo, pelo fabricante da CPU, pelas leis da física ou o que for), mas com pouco -oh, você mesmo escolhe a constante e pode ser tão pequena quanto quiser . Em outras palavras, com estruturas de dados sucintas, a sobrecarga relativa fica arbitrariamente pequena à medida que o tamanho do problema aumenta.

Obviamente, o tamanho do problema pode ter que ser enorme para perceber a sobrecarga relativa que você deseja, mas não pode ter tudo.

OK, com isso em nossos cintos, vamos colocar alguns números sobre o problema. Vamos supor que as chaves sejam números inteiros de bits (portanto, o tamanho do universo é 2 n ) e queremos armazenar 2 m desses números inteiros. Suponhamos que possamos organizar magicamente uma tabela de hash idealizada com ocupação total e sem desperdício, para que precisemos de exatamente 2 m de slots de hash.$n$$2^n$$2^m$$2^m$

Uma operação de pesquisa faria o hash da chave bits, mascararia m bits para encontrar os slots de hash e depois verificaria se o valor na tabela correspondia à chave. Por enquanto, tudo bem.$n$$m$

Essa tabela de hash usa bits. Podemos fazer melhor que isso?$n 2^m$

Suponha que a função hash seja invertível. Então não precisamos armazenar a chave inteira em cada slot de hash. A localização do slot de hash fornece m bits do valor de hash; portanto, se você armazenou apenas os n - m bits restantes, poderá reconstruir a chave a partir dessas duas informações (a localização do slot de hash e o valor armazenado lá). Então você precisaria apenas ( n - m ) de 2 m de bits de armazenamento.$h$$m$$n-m$$(n - m) 2^m$

Se é pequeno em comparação com 2 n , a aproximação de Stirling e um pouco de aritmética (a prova é um exercício!) Revela que:$2^m$$2^n$

Portanto, essa estrutura de dados é sucinta.

No entanto, existem duas capturas.

O primeiro problema é a construção de funções hash invertíveis "boas". Felizmente, isso é muito mais fácil do que parece; os criptografadores fazem funções invertíveis o tempo todo, apenas eles os chamam de "cifras". Você pode, por exemplo, basear uma função hash em uma rede Feistel, que é uma maneira direta de construir funções hash invertíveis a partir de funções hash não invertíveis.

O segundo problema é que tabelas de hash reais não são ideais, graças ao paradoxo do aniversário. Portanto, você deseja usar um tipo mais sofisticado de tabela de hash que o aproxima da ocupação total sem derramar. O hash do cuco é perfeito para isso, pois permite que você se aproxime arbitrariamente do ideal na teoria e na prática.

O hash do cuco exige várias funções de hash e exige que os valores nos slots de hash sejam marcados com a qual a função de hash foi usada. Portanto, se você usar quatro funções de hash, por exemplo, precisará armazenar mais dois bits em cada slot de hash. Isso ainda é sucinto à medida que cresce, por isso não é um problema na prática e ainda é melhor do que armazenar chaves inteiras.$m$

Ah, você também pode querer olhar para as árvores de van Emde Boas.

MAIS PENSAMENTOS

Se estiver em algum lugar perto de $n$ , depoisfaça logon ($\frac{u}{2}$ é aproximadamenteu, então (mais uma vez) assumindo que não há mais correlação entre os valores, você basicamente não pode fazer nada melhor do que um vetor de bits. Você observará que a solução de hash acima se degenera efetivamente nesse caso (você acaba armazenando um bit por slot de hash), mas é mais barato usar a chave como endereço do que usar uma função de hash.$\log {u \choose n }$$u$

Se estiver muito próximo de u , toda a literatura sucinta das estruturas de dados recomenda que você inverta o sentido do dicionário. Armazene os valores que não ocorrem no conjunto. No entanto, agora você precisa efetivamente oferecer suporte à operação de exclusão e, para manter um comportamento sucinto, também precisa reduzir a estrutura de dados à medida que mais elementos são "adicionados". Expandir uma tabela de hash é uma operação bem compreendida, mas contratá-la não é.$n$$u$

Parece que você deseja uma estrutura de dados sucinta para o problema de associação dinâmica .

Lembre-se de que uma estrutura de dados sucinta é aquela para a qual o requisito de espaço é "próximo" ao limite inferior da teoria da informação, mas, diferentemente de uma estrutura de dados compactada, ainda permite consultas eficientes.

O problema da associação é exatamente o que você descreve na sua pergunta:

$S$$n$$U = \{0, 1, 2, 3, \dots , u – 1\}$$u$

• find(x)x$S$
• insert(x)x$S$
• delete(x)x$S$

Se apenas a findoperação for suportada, esse é o problema estático da associação. Se um insertou deletefor suportado, mas não ambos, será chamado semi-dinâmico e, se todas as três operações forem suportadas, será chamado de problema de associação dinâmica .

Tecnicamente, acho que você pediu apenas uma estrutura de dados para o problema de associação semi-dinâmica, mas não conheço nenhuma estrutura de dados que tire proveito dessa restrição e também atenda a seus outros requisitos. No entanto, tenho a seguinte referência:

No Teorema 5.1 do artigo Associação em Tempo Constante e Espaço Quase Mínimo , Brodnik e Munro fornecem o seguinte resultado:

$O(B)$

$B = \lceil \log {u \choose n} \rceil$

A idéia básica é que eles dividam recursivamente o universo em faixas de tamanhos cuidadosamente escolhidos, de modo que isso soa até como as técnicas podem estar na mesma linha em que você está pensando.

$u$$n$