¿Un buen esquema para representar números enteros de 0 a infinito, suponiendo que tenga un almacenamiento binario lineal infinito?

10

Me gustaría que un esquema represente números enteros que comiencen por 0, sin ningún límite (suponiendo el acceso al almacenamiento lineal infinito).

Aquí hay un esquema que puede representar números del 0 al 255:

Use el primer byte del almacenamiento (dirección 0) para almacenar el entero.

Ahora, supongamos que quiero representar números mayores que 255. Por supuesto, podría usar más de 1 byte para representar el número entero, pero mientras sea un número fijo, eventualmente habrá un número entero tan grande que no puede ser representado por El esquema original.

Aquí hay otro esquema que debería ser capaz de hacer la tarea, pero probablemente esté lejos de ser eficiente.

Simplemente use algún tipo de byte único de "fin de número" y use todos los bytes anteriores para representar el número. Obviamente, este byte "fin de número" no se puede usar en ninguna parte de la representación numérica, pero esto se puede lograr usando un sistema de numeración base-255 (en lugar de base-256).

Sin embargo, eso es lento y probablemente ineficiente. Quiero tener uno mejor que funcione mejor con valores bajos y escale bien.

Esencialmente, es un sistema UUID. Quiero ver si es posible crear un sistema UUID de rendimiento rápido que, en teoría, pueda escalar para usar durante años, miles de años, millones de años, sin tener que rediseñarlo.

storage numbers uuid Dmitri Shuralyov
fuente
1
¿Desea algo que pueda escalar infinitamente (como en su apertura), o por millones de años (como en su cierre)? Los dos requisitos son (obviamente) completamente diferentes. Dos complementos en una máquina de 64 bits se ampliarán durante millones de años.
user16764
1
@ user16764, ¿quiere decir una sola variable entera de 64 bits? Eso ciertamente no funcionará: si 6 millones de personas consumen 1 millón de UUID por segundo, apenas durará más de un mes.
Dmitri Shuralyov
1
¿Y cuánto tardaría en una máquina de 128 bits?
user16764
2
Las ideas en RFC 2550 , que proporciona una representación ASCII ordenada lexicográficamente para enteros positivos arbitrariamente grandes, pueden adaptarse a esto. En última instancia, se descompone en un segmento unario que codifica la longitud de un segmento de base 26 que codifica la longitud de un segmento de base 10; las dos últimas bases tienen más que ver con la representación ASCII que con cualquier cosa fundamental del esquema.
Random832
1
Suponiendo que genere números de 128 bits secuencialmente: si limitamos la capacidad de cálculo de todas las computadoras al darle a cada humano una computadora petaflop, entonces tomaría 9 millones de años antes de que estos números se agoten. Si, por otro lado, cada humano generara aleatoriamente 600 millones de números de 128 bits, hay un 50% de posibilidades de que generen 1 duplicado. ¿Eso es lo suficientemente bueno para ti? ( en.wikipedia.org/wiki/Universally_unique_identifier ) Si no, el uso de 256 bits multiplica ambas cifras por 2 ^ 128 = 3.4 * 10 ^ 38, que es más que el cuadrado de la edad del universo en segundos.
Alex ten Brink

Respuestas:

13

Un enfoque que he usado: contar el número de 1 bit inicial, por ejemplo n. El tamaño del número es entonces 2 ^ n bytes (incluidos los 1 bits iniciales). Tome los bits después del primer bit 0 como un entero y agregue el valor máximo (más uno) que puede ser representado por un número usando esta codificación en 2 ^ (n-1) bytes.

Así, 

                  0 = 0b00000000
                   ...
                127 = 0b01111111
                128 = 0b1000000000000000
                   ...
              16511 = 0b1011111111111111
              16512 = 0b11000000000000000000000000000000
                   ...
          536887423 = 0b11011111111111111111111111111111
          536887424 = 0b1110000000000000000000000000000000000000000000000000000000000000
                   ...
1152921505143734399 = 0b1110111111111111111111111111111111111111111111111111111111111111
1152921505143734400 = 0b111100000000000000000000000000000000000000000000 ...

Este esquema permite que cualquier valor no negativo se represente exactamente de una manera.

(De manera equivalente, usé el número de 0 bits iniciales).

retroceder
fuente
1
Me resultó difícil determinar qué respuesta marcar como aceptada, porque creo que muchas de ellas son muy informativas y buenas. Pero creo que esta es la mejor opción para la pregunta que hice (posiblemente no la subyacente que tenía en mente, que es más difícil de expresar).
Dmitri Shuralyov
2
Escribí un artículo más detallado con un ejemplo de implementación y consideraciones de diseño.
retroceder
10

Hay mucha teoría basada en lo que estás tratando de hacer. Eche un vistazo a la página wiki sobre códigos universales : hay una lista bastante exhaustiva de métodos de codificación de enteros (algunos de los cuales se están utilizando en la práctica).

En la compresión de datos, un código universal para enteros es un código de prefijo que asigna los enteros positivos a palabras de código binario

O simplemente puede usar los primeros 8 bytes para almacenar la longitud del número en algunas unidades (bytes más probables) y luego colocar los bytes de datos. Sería muy fácil de implementar, pero bastante ineficiente para números pequeños. Y podría codificar un número entero el tiempo suficiente para llenar todas las unidades de datos disponibles para la humanidad :)

Matěj Zábský
fuente
Gracias por eso, eso es muy interesante. Quería marcar esto como respuesta aceptada, pero tomó el segundo lugar. Esta es una muy buena respuesta desde un punto de vista teórico, la OMI.
Dmitri Shuralyov
4

¿Qué tal si el número de los primeros 1 más el primer 0 sea el tamaño (sizeSize) del tamaño del número (numSize) en bits. NumSize es un número binario que proporciona el tamaño de la representación del número en bytes, incluidos los bits de tamaño. Los bits restantes son el número (num) en binario. Para un esquema entero positivo, aquí hay algunos ejemplos de números de ejemplo:

Number              sizeSize  numSize    num
63:                 0 (1)     1 (1)      111111
1048575:            10 (2)    11 (3)     1111 11111111 11111111
1125899906842623:   110 (3)   111 (7)    11 11111111 11111111 11111111 11111111 11111111 11111111
5.19.. e+33:        1110 (4)  1111 (15)  11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
Briguy37
fuente
4

¿Qué tal eso? Un byte para la longitud, luego n bytes para el número (primero el byte menos significativo). Repita longitud + número siempre que la longitud anterior fuera 255.

Esto permite números arbitrariamente grandes, pero sigue siendo fácil de manejar y no desperdicia demasiada memoria.

usuario281377
fuente
fNek: no hay límite superior. Por ejemplo, si necesita 513 bytes para el número, la secuencia de bytes es [255, b0, ..., b255,255, b256, ..., b511,2, b512, b513]
user281377
Lo siento. Debería aprender a leer con más cuidado.
fNek
3

¿Por qué no usar solo 7 bits de cada byte y usar el octavo bit para indicar si hay otro byte a seguir? Entonces 1-127 estaría en un byte, 128 estaría representado por 0x80 0x01, etc.

Paul Tomblin
fuente
1
Este esquema codifica solo 128 valores en cada 8 bits, que en realidad es menos eficiente en espacio que el segundo esquema de codificación propuesto por el interrogador, donde 255 valores se codifican en cada 8 bits. Ambos esquemas adolecen del hecho de que necesita leer el número entero para saber cuánto almacenamiento necesita para almacenarlo.
Mark Booth
3
Entonces necesita escanear el número dos veces para hacer una copia, ¿y qué? Si puedo esperar un número infinitamente grande, puedo esperarlo dos veces.
Russell Borogove
Aunque no lo especifiqué con mucho cuidado, estoy buscando una solución que funcione de la manera más eficiente posible (en lugar de una solución que simplemente cumpla con los requisitos; ya he descrito una respuesta potencialmente ineficiente en mi pregunta).
Dmitri Shuralyov
3

Los sistemas UUID se basan en una potencia informática limitada (pero grande) en un universo finito (pero grande). El número de UUID es grande incluso en comparación con cosas absurdamente grandes como el número de partículas en el universo. Sin embargo, el número de UUID, con cualquier número de bits fijos, es pequeño, en comparación con el infinito.

El problema con el uso de 0xFFFF para representar su indicador de fin de número es que hace que la codificación de su número sea menos eficiente cuando los números son grandes. Sin embargo, parece que su esquema UUID empeora este problema. En lugar de omitir uno de cada 256 bytes, ahora tiene todo el espacio UUID desperdiciado. La eficiencia de la computación / reconocimiento (en lugar del espacio) depende mucho de su computadora teórica (lo cual, supongo que tiene si está hablando de infinito). Para una TM con una cinta y un controlador de estado finito, cualquier esquema de UUID es imposible de escalar de manera eficiente (básicamente, el lema de bombeo evita que se mueva más allá de un marcador de extremo de longitud fija de manera eficiente). Si no asume un controlador de estado finito, esto podría no aplicarse, pero debe pensar dónde van los bits en el proceso de decodificación / reconocimiento.

Si solo desea una mejor eficiencia que 1 de 256 bytes, puede usar cualquier longitud de bit de 1s que iba a usar para su esquema UUID. Eso es 1 de 2 ^ longitud de bits en ineficiencia.

Sin embargo, tenga en cuenta que hay otros esquemas de codificación. La codificación de bytes con delimitadores resulta ser la más fácil de implementar.

ccoakley
fuente
2

Sugeriría tener una matriz de bytes (o ints o longs) y un campo de longitud que diga qué tan largo es el número.

Este es más o menos el enfoque utilizado por BigInteger de Java . El espacio de direcciones posible a partir de esto es masivo, lo suficientemente fácil como para dar un UUID diferente a cada átomo individual en el universo :-)

A menos que tenga una muy buena razón para hacerlo, sugeriría simplemente usar BigInteger directamente (o su equivalente en otros idiomas). No es necesario reinventar la rueda de números grandes ...

mikera
fuente
No puede codificar la longitud de la matriz cuando el número de campos puede ser infinito.
Slawek
Estoy de acuerdo en que es preferible utilizar una solución existente (especialmente una que haya pasado por un escrutinio profesional) para un problema dado, cuando sea posible. Gracias.
Dmitri Shuralyov
@Slawek: verdadero, pero para el caso de uso que describe el OP (es decir, UUID), un BigInteger es efectivamente infinito. De todos modos, no puede codificar información infinita en ninguna computadora con memoria de tamaño finito, por lo que BigInteger es tan bueno como cualquier otra cosa que pueda lograr.
mikera
2

En primer lugar, gracias a todos los que contribuyeron con excelentes respuestas a mi pregunta relativamente vaga y abstracta.

Me gustaría aportar una respuesta potencial que he pensado después de pensar en otras respuestas. No es una respuesta directa a la pregunta formulada, pero es relevante.

Como algunas personas señalaron, el uso de un número entero de 64/128/256 bits ya le brinda un espacio muy grande para UUID. Obviamente no es infinito, pero ...

Tal vez sea una buena idea usar un tamaño fijo int (digamos, 64 bits para comenzar) hasta que 64 bits no sea suficiente (o esté cerca de él). Luego, suponiendo que tenga dicho acceso a todas las instancias anteriores de los UUID, simplemente actualícelos a todos a ints de 128 bits y considere que es su número entero de tamaño fijo.

Si el sistema permite tales pausas / interrupciones del servicio, y debido a que tales operaciones de "reconstrucción" deberían ocurrir con poca frecuencia, quizás los beneficios (un sistema muy simple, rápido y fácil de implementar) sobrepasarán las desventajas (tener que reconstruir todos los enteros previamente asignados) a un nuevo tamaño de bit entero).

Dmitri Shuralyov
fuente