Une mémoire de toutes les permutations possibles d'un bloc de kilo-octets et de pointeurs est-elle possible?

23

C'est une idée assez difficile à comprendre et j'apprécierais grandement toute modification / aide pour la rendre plus lisible pour ceux qui connaissent.

Est-il théoriquement possible d'avoir un disque dur qui a enregistré une copie de chaque permutation binaire possible d'un kilo-octet et que le reste du système crée simplement des pointeurs vers ces emplacements?

Un système conçu de cette manière serait-il plus rapide que de simplement stocker directement des informations?

Pour expliquer une autre façon, dites au lieu d'avoir des phrases:

"Bonjour, je m'appelle Bob." et "Ce sandwich a l'air délicieux."

... stockés sur le disque dur, nous aurions toutes les permutations de l'alphabet et d'autres caractères jusqu'à un certain nombre (disons, 1000 caractères environ), puis nous aurions stocké nos phrases comme quelque chose comme:

[Pointeur # 21381723]

theory pointers storage information-theory Amagii Discordus Penndragon
la source
21
Vous voudrez peut-être considérer combien de tweets anglais uniques sont possibles? Combien de temps faudrait-il à la population mondiale pour les lire à haute voix? . Vous avez affaire à de très gros chiffres.
Vous pourriez trouver intéressant le fonctionnement de git , appelé contenu adressable .
JDługosz
5
github.com/philipl/pifs Est basé sur le même principe que votre idée, sauf qu'au lieu d'avoir toutes les permutations d'un ko, il utilise pi.
Waxen du
12
Vos pointeurs devraient être longs de 1 kilo-octet. Vous pouvez choisir de ne pas stocker les blocs qui n'ont pas de sens en anglais - auquel cas vous avez indépendamment réinventé l'idée de la compression!
user253751
La réponse de base est NON - c'est impossible en raison du nombre et de la taille des permutations Mais quelle application possible pensiez-vous que ce serait utile si c'était possible ??
Archange

Réponses:

91

Il y a 2 8192 blocs 1K différents possibles. Les stocker tous nécessiterait 2 8202 bits de stockage. Étant donné que l'univers ne contient qu'environ 10 80 (ou ~ 2 266 ) particules, il y a fort à parier qu'il n'est pas possible de toutes les stocker, et vous n'avez pas à vous demander si cela gagnerait du temps ou non.

Mais il y a, en fait, une façon plus intéressante de répondre à cela. Vous proposez de créer un index dans un énorme pool de constantes. Mais comment sauriez-vous quel indice déréférencer? Imaginez l'intérêt d'un argument que vous souhaitez stocker uniquement des blocs 1 caractères: a, b, c... On peut supposer que vos indices seraient 0, 1, 2 , etc., puisque c'est la disposition la plus efficace de stocker ces blocs.

Avez-vous remarqué quelque chose au sujet de l'arrangement? Votre index est, en fait, une représentation codée des données stockées ! En d'autres termes, vous n'avez pas du tout à déréférencer, il vous suffit de transformer l'index en données que vous souhaitez.

Lorsque vous stockez toutes les valeurs possibles de quelque chose dans une table, cela se produit toujours: votre index devient simplement une version codée des données elles-mêmes, donc le stockage des données devient inutile en premier lieu. Ce pourquoi , dans le monde réel, les indices ne sont utiles que pour les données rares (par exemple , toutes les pages Web que vous avez visités, toutes les pages Web qui pourraient exister , ou même tout ce qui ne existent).

Kilian Foth
la source
17
Donc, d'une certaine manière, nous utilisons déjà ce système - mais nous le faisons avec une évaluation paresseuse des modèles de bits de la taille d'un kilo-octet, ce qui nous permet d'économiser des tonnes d'espace de stockage!
Theodoros Chatzigiannakis
3
Le stockage est légèrement réduit, en raison du chevauchement (1024 zéros suivis de 1024 contiennent 1025 motifs uniques) ... réduits mais toujours incroyablement volumineux. En outre, un bloc de 1 Ko représente 2 <sup> 13 </sup> bits, et non 2 <sup> 10 </sup>.
Ben Voigt du
2
Notez que la limite de 10 ^ 80 sur les particules dans l'univers ne signifie pas directement que vous ne pouvez pas stocker plus de, disons, 10 ^ 80 bits dans l'univers - car avec chaque particule, vous pouvez potentiellement stocker plus d'un bit d'informations ( en fonction de sa position dans l'univers, et éventuellement de sa vitesse, etc.). Cela ne signifie cependant pas que vous pouvez stocker chaque bloc de 1K - le nombre de ceux-ci dépasse le nombre de particules par un facteur étonnamment grand, donc c'est toujours une valeur très sûre que vous ne pouvez pas tous les stocker!
psmears
2
@Neil Si vous avez un système de codage qui vous permet de stocker 10 ^ 80 en le codant comme "10 ^ 80", comment stockez-vous "10 ^ 80"? Si certains éléments de données sont encodés plus court que les données réelles, d'autres doivent être encodés plus longtemps. Ou si toutes vos données sont des nombres, alors vous stockez chaque chiffre décimal comme un octet entier.
Random832
3
Avec des séquences de Bruijn, 2 ^ 1024 bits suffiraient.
gronostaj
20

Comme d'autres l'ont déjà souligné, vous avez 2 ^ 8192 possibilités pour un bloc de 1k. Cela signifie que vous auriez besoin de 8192 bits pour coder l'adresse d'un bloc si toutes les adresses de blocs sont codées avec la même quantité de bits, de sorte que vos adresses auraient une longueur de 1k. Vous n'auriez rien gagné sauf l'ajout d'une couche d'indirection afin de ne gagner aucune performance.

Si vous voulez avoir des adresses plus courtes, vous devrez encoder certains blocs avec une adresse courte et certains avec des adresses plus longues et faire en sorte que les longs n'apparaissent pas souvent, et vous compressez maintenant simplement les données (probablement avec quelque chose comme un code Huffman ). Cela nécessiterait la connaissance des données que vous stockez avant de les stocker ou des changements réguliers dans l'encodage. Il serait également probablement moins efficace que d'autres algorithmes de compression qui utilisent des blocs de longueur variable.

user2313067
la source
1

Il y a deux problèmes avec cela.

Premièrement, «toutes les permutations binaires possibles d'un kilo-octet» représentent une énorme quantité de données. 1024 octets * 8 bits par octet = 8192 bits en kilo-octet. Toutes les permutations possibles seraient 2 ^ 8192. C'est environ 1.09e+2466kilo-octets! (À des fins de comparaison, un lecteur de 1 To équivaut à des 1e09kilo - octets.)

Deuxièmement, même si vous aviez une table aussi énorme et que vous y étiez indexé avec des pointeurs, que feriez-vous si vous vouliez référencer des données inférieures à exactement 1 Ko?

Mason Wheeler
la source
2
En outre, le stockage de tous les blocs inférieurs à 1 Ko ne prendra pas beaucoup plus d'espace. En supposant uniquement des blocs de taille octet, la taille des blocs plus petits ensemble est légèrement supérieure à 1/256 de la taille des blocs de 1 Ko. En supposant des blocs de taille binaire, vous ajoutez à nouveau environ la même taille.
Paŭlo Ebermann
-1

Comme d'autres affiches l'ont souligné, à un moment donné, la taille du pointeur nécessaire pour indexer dans votre liste toutes les valeurs possibles annule votre gain.

Cependant, certaines langues utilisent une version limitée de ce que vous proposez afin d'optimiser l'utilisation de la mémoire. Python utilise la chaîne «interning» pour réduire le nombre de chaînes en double en mémoire. Vous pouvez trouver plus d'informations en recherchant «intern chaîne de python».

JS.
la source
1
L'OP pose des questions sur un ensemble dense, contenant chaque permutation. Les pointeurs ne sont utiles que pour les données éparses, où les bits requis pour contenir un pointeur sont plus petits que les bits pointés. L'internement peut rendre l'espace plus clairsemé s'il y a des doublons, il y a donc une connexion, mais votre réponse ne le dit pas vraiment bien.
Peter Cordes