É possível uma memória de todas as permutações possíveis de um bloco de kilobytes e ponteiros?

23

Essa é uma idéia bastante difícil de entender, e eu apreciaria muito qualquer edição / ajuda para torná-la mais legível para aqueles que conhecem.

É teoricamente possível ter um disco rígido que tenha salvo uma cópia de cada permutação binária possível de um kilobyte e, em seguida, o restante do sistema simplesmente crie ponteiros para esses locais?

Um sistema criado dessa maneira seria mais rápido do que simplesmente ter informações armazenadas diretamente?

Para explicar outra maneira, diga em vez de ter frases:

"Olá, eu sou Bob." e "Esse sanduíche parece delicioso".

... armazenados no disco rígido, teríamos todas as permutações do alfabeto e de outros caracteres com um certo número (digamos, 1.000 caracteres ou mais) e, em seguida, armazenamos nossas frases como algo como:

[Ponteiro # 21381723]

theory pointers storage information-theory Amagii Discordus Penndragon
fonte
21
Você pode considerar quantos tweets únicos em inglês são possíveis? Quanto tempo levaria para a população do mundo ler todos em voz alta? . Você está lidando com números muito grandes.
Você pode achar interessante como o git funciona, chamado de conteúdo endereçável .
JDługosz 15/09/2015
5
github.com/philipl/pifs É baseado no mesmo princípio da sua ideia, exceto que, em vez de ter todas as permutações de um kb, ele usa pi.
Waxen 15/09/15
12
Seus ponteiros teriam que ter 1 kilobyte de comprimento. Você pode optar por não armazenar os blocos que não fazem sentido em inglês - nesse caso, você reinventou independentemente a idéia de compactação!
user253751
A resposta básica é NÃO - é impossível devido ao número e tamanho das permutações. Mas para qual aplicação possível você estava pensando que seria útil se fosse possível?
Arcanjo

Respostas:

91

Existem 2 8192 possíveis blocos 1K diferentes. Armazená-los todos levaria 2 8202 bits de armazenamento. Como o universo contém apenas cerca de 10 80 (ou ~ 2 266 ) partículas, é uma aposta segura que não é possível armazenar todas, e você não precisa se perguntar se isso pouparia tempo ou não.

Mas existe, de fato, uma maneira mais interessante de responder a isso. Você está sugerindo a criação de um índice em um enorme conjunto de constantes. Mas como você saberia qual índice desreferenciar? Imagine por causa de um argumento que você deseja armazenar apenas 1 caracteres blocos: a, b, c... Presumivelmente seus índices seria 0, 1, 2, etc., já que é o layout mais eficiente de armazenar esses blocos.

Você percebe algo sobre o arranjo? Seu índice é, de fato, uma representação codificada dos dados armazenados ! Em outras palavras, você não precisa desreferenciar, basta transformar o índice nos dados que deseja.

Quando você armazena todos os valores possíveis de algo em uma tabela, isso sempre acontece: seu índice se torna apenas uma versão codificada dos próprios dados; portanto, o armazenamento dos dados se torna desnecessário em primeiro lugar. Isso porque no mundo real, os índices são úteis apenas para dados escassos (por exemplo, todas as páginas da web que você visitou, nem todas as páginas da web que poderia existir , ou mesmo tudo o que fazer existem).

Kilian Foth
fonte
17
Então, de certa forma, já estamos usando este sistema - mas estamos fazendo isso com avaliação preguiçosa dos padrões de bits tamanho kilobyte-, o que nos permite economizar toneladas de espaço de armazenamento!
Theodoros Chatzigiannakis
3
O armazenamento é ligeiramente reduzido, devido à sobreposição (1024 zeros seguidos por 1024 uns contém 1025 padrões únicos) ... reduzido, mas ainda impossivelmente grande. Além disso, um bloco de 1 KB é de 2 <sup> 13 </sup> bits, não 2 <sup> 10 </sup>.
Ben Voigt
2
Observe que o limite de 10 ^ 80 para partículas no universo não significa diretamente que você não pode armazenar mais do que, digamos, 10 ^ 80 bits no universo - porque com cada partícula você pode potencialmente armazenar mais de um bit de informação ( com base em sua posição dentro do universo, e possivelmente em sua velocidade etc). Isso não significa que você pode armazenar todos os blocos de 1K - o número deles excede o número de partículas por um fator surpreendentemente grande, por isso ainda é uma aposta muito segura que você não pode armazenar todos eles!
Psmears 15/09/2015
2
@ Neil Se você possui um sistema de codificação que permite armazenar 10 ^ 80, codificando-o como "10 ^ 80", como você armazena "10 ^ 80"? Se algumas partes dos dados são codificadas mais curtas que os dados reais, outras precisam ser codificadas por mais tempo. Ou, se todos os seus dados forem números, você estará armazenando cada dígito decimal como um byte inteiro.
usar o seguinte código
3
Com as seqüências de De Bruijn, 2 ^ 1024 bits seriam suficientes.
gronostaj
20

Como outros já apontaram, você tem 2 ^ 8192 possibilidades para um bloco de 1k. Isso significa que você precisaria de 8192 bits para codificar o endereço de um bloco se todos os endereços de blocos forem codificados com a mesma quantidade de bits, para que seus endereços tenham 1k de comprimento. Você não teria ganho nada além de adicionar uma camada de indireção para não obter nenhum desempenho.

Se você quisesse ter endereços mais curtos, teria que codificar alguns blocos com um endereço curto e outros com endereços mais longos e torná-lo para que os longos não apareçam com tanta frequência, e agora você está simplesmente compactando dados (provavelmente com algo como um código Huffman ). Isso exigiria o conhecimento dos dados que você está armazenando antes de armazená-los ou alterações regulares na codificação. Provavelmente também seria menos eficiente do que outros algoritmos de compactação que usam blocos de comprimento variável.

user2313067
fonte
1

Existem dois problemas com isso.

Primeiro, "todas as permutações binárias possíveis de um kilobyte" são uma enorme quantidade de dados. 1024 bytes * 8 bits por byte = 8192 bits em um kilobyte. Todas as permutações possíveis seriam 2 ^ 8192. Isso é em torno de 1.09e+2466kilobytes! (Para fins de comparação, uma unidade de 1 TB é de 1e09kilobytes.)

Segundo, mesmo se você tivesse uma tabela tão grande e indexasse nela com ponteiros, o que faria se quisesse referenciar alguns dados menores que exatamente 1 KB?

Mason Wheeler
fonte
2
Armazenar todos os blocos menores que 1 KB, além disso, não ocupará muito mais espaço. Assumindo apenas blocos do tamanho de bytes, o tamanho dos blocos menores juntos é um pouco acima de 1/256 do tamanho dos blocos de 1 KB. Supondo blocos de tamanho de bits, você adiciona mais ou menos o mesmo tamanho.
Pa Elo Ebermann
-1

Como outros pôsteres apontaram, em algum momento, o tamanho do ponteiro necessário para indexar em sua lista todos os valores possíveis anula seu ganho.

No entanto, alguns idiomas usam uma versão limitada do que você sugere para otimizar o uso da memória. O Python usa a string 'interning' para diminuir o número de strings duplicadas na memória. Você pode encontrar mais informações pesquisando 'python string intern'.

JS.
fonte
1
O OP está perguntando sobre um conjunto denso, contendo todas as permutações. Os ponteiros são úteis apenas para dados esparsos, onde os bits necessários para armazenar um ponteiro são menores que os bits apontados. A internação pode tornar o espaço mais escasso se houver duplicatas; portanto, há uma conexão lá, mas sua resposta não é muito boa.
Peter Cordes