¿Es posible un recuerdo de todas las permutaciones posibles de un bloque de kilobytes y punteros?

23

Esta es una idea bastante difícil de entender y agradecería mucho cualquier edición / ayuda para que sea más legible para aquellos que están al tanto.

¿Es teóricamente posible tener un disco duro que haya guardado una copia de cada permutación binaria posible de un kilobyte y luego hacer que el resto del sistema simplemente cree punteros a estas ubicaciones?

¿Sería un sistema hecho de esa manera más rápido que simplemente tener información almacenada directamente?

Para explicar otra forma, diga en lugar de tener oraciones:

"Hola, soy Bob". y "Ese sándwich se ve delicioso".

... almacenado en el disco duro, tendríamos todas las permutaciones del alfabeto y otros caracteres hasta cierto número (digamos, 1000 caracteres más o menos), y luego almacenar nuestras oraciones como algo así como:

[Puntero # 21381723]

Amagii Discordus Penndragon
fuente
Puede que le resulte interesante cómo funciona git , llamado contenido direccionable .
JDługosz
55
github.com/philipl/pifs Se basa en el mismo principio que su idea, excepto que en lugar de tener todas las permutaciones de un kb, usa pi.
Waxen
12
Sus punteros tendrían que tener 1 kilobyte de largo. Puede optar por no almacenar los bloques que no tienen sentido en inglés, ¡en cuyo caso ha reinventado independientemente la idea de la compresión!
user253751
La respuesta básica es NO: es imposible debido al número y al tamaño de las permutaciones. ¿Pero para qué aplicación posible creías que sería útil si fuera posible?
Arcángel

Respuestas:

91

Hay 2 8192 posibles bloques de 1K diferentes. Almacenarlos a todos tomaría 2 8202 bits de almacenamiento. Dado que el universo contiene solo alrededor de 10 80 (o ~ 2 266 ) partículas, es una apuesta segura que no es posible almacenarlas todas, y no tiene que preguntarse si ahorraría tiempo o no.

Pero hay, de hecho, una forma más interesante de responder a esto. Usted sugiere crear un índice en un gran grupo de constantes. Pero, ¿cómo saber qué índice desreferenciar? Imagine por el bien de un argumento que desea almacenar solamente de 1 carácter bloques: a, b, c... Es de suponer que sus índices serían 0, 1, 2, etc., ya que es la disposición más eficiente de almacenar los bloques.

¿Notas algo sobre el arreglo? ¡Su índice es, de hecho, una representación codificada de los datos almacenados ! En otras palabras, no tiene que desreferenciar en absoluto, solo tiene que transformar el índice en los datos que desea.

Cuando almacena todos los valores posibles de algo en una tabla, esto siempre sucede: su índice se convierte simplemente en una versión codificada de los datos en sí, por lo que el almacenamiento de datos se vuelve innecesario en primer lugar. Es por esto que en el mundo real, los índices sólo son útiles para datos dispersos (por ejemplo, todas las páginas web que ha visitado, no todas las páginas web que pudieran existir , o incluso todo lo que hacen existir).

Kilian Foth
fuente
17
Entonces, en cierto modo, ya estamos usando este sistema, ¡pero lo estamos haciendo con una evaluación perezosa de los patrones de bits del tamaño de kilobytes, lo que nos permite ahorrar toneladas de espacio de almacenamiento!
Theodoros Chatzigiannakis
3
El almacenamiento se reduce ligeramente debido a la superposición (1024 ceros seguidos de 1024 contienen 1025 patrones únicos) ... reducido pero aún increíblemente grande. Además, un bloque de 1 KB tiene 2 <sup> 13 </sup> bits, no 2 <sup> 10 </sup>.
Ben Voigt
2
Tenga en cuenta que el límite de 10 ^ 80 en partículas en el universo no significa directamente que no puede almacenar más de, digamos, 10 ^ 80 bits en el universo, porque con cada partícula puede potencialmente almacenar más de un bit de información ( basado en su posición dentro del universo, y posiblemente su velocidad, etc.). Sin embargo, eso no significa que pueda almacenar cada bloque de 1K: ¡la cantidad de esos excede el número de partículas en un factor asombrosamente grande, por lo que sigue siendo una apuesta muy segura de que no puede almacenarlos todos!
psmears
2
@Neil Si tiene un sistema de codificación que le permite almacenar 10 ^ 80 codificándolo como "10 ^ 80", entonces, ¿cómo almacena "10 ^ 80"? Si algunos datos se codifican más cortos que los datos reales, otros deben codificarse más tiempo. O si todos sus datos son números, entonces está almacenando cada dígito decimal como un byte completo.
Random832
3
Con las secuencias de Bruijn serían suficientes 2 ^ 1024 bits.
gronostaj
20

Como otros ya han señalado, tiene 2 ^ 8192 posibilidades para un bloque de 1k. Esto significa que necesitaría 8192 bits para codificar la dirección de un bloque si todas las direcciones de los bloques están codificadas con la misma cantidad de bits, por lo que sus direcciones tendrían una longitud de 1k. No habría ganado nada excepto agregar una capa de indirección para no obtener ningún rendimiento.

Si quisieras tener direcciones más cortas, tendrías que codificar algunos bloques con una dirección corta y algunos con direcciones más largas y hacer que las largas no aparezcan tan a menudo, y ahora simplemente estás comprimiendo datos (probablemente con algo como un código Huffman ). Eso requeriría conocer los datos que está almacenando antes de almacenarlos o cambios regulares en la codificación. Probablemente también sería menos eficiente que otros algoritmos de compresión que usan bloques de longitud variable.

usuario2313067
fuente
1

Hay dos problemas con eso.

Primero, "todas las permutaciones binarias posibles de un kilobyte" son una gran cantidad de datos. 1024 bytes * 8 bits por byte = 8192 bits en un kilobyte. Todas las permutaciones posibles serían 2 ^ 8192. ¡Eso es alrededor de 1.09e+2466kilobytes! (Para fines de comparación, una unidad de 1 TB es 1e09kilobytes).

En segundo lugar, incluso si tuviera una tabla tan enorme y la indexara con punteros, ¿qué haría si quisiera hacer referencia a algunos datos más pequeños que exactamente 1 KB?

Mason Wheeler
fuente
2
Almacenar todos los bloques de menos de 1 KB además no ocupará mucho más espacio. Suponiendo solo bloques del tamaño de un byte, el tamaño de los bloques más pequeños juntos es ligeramente superior a 1/256 del tamaño de los bloques de 1 KB. Suponiendo bloques de tamaño de bit, agrega nuevamente aproximadamente el mismo tamaño.
Paŭlo Ebermann
-1

Como otros carteles han señalado, en algún momento, el tamaño del puntero necesario para indexar en su lista de todos los valores posibles anula su ganancia.

Sin embargo, algunos idiomas usan una versión limitada de lo que sugiere para optimizar el uso de la memoria. Python usa la cadena 'interning' para disminuir el número de cadenas duplicadas en la memoria. Puede encontrar más información buscando 'python string intern'.

JS.
fuente
1
El OP pregunta por un conjunto denso que contiene cada permutación. Los punteros solo son útiles para datos dispersos, donde los bits necesarios para contener un puntero son más pequeños que los bits apuntados. La internación puede hacer que el espacio sea más escaso si hay duplicados, por lo que hay una conexión allí, pero su respuesta realmente no lo expresa bien.
Peter Cordes