Un bon schéma pour représenter des nombres entiers de 0 à l'infini, en supposant que vous avez un stockage binaire linéaire infini?

10

Je voudrais qu'un schéma représente des nombres entiers commençant par 0, sans aucune limite (en supposant l'accès au stockage linéaire infini).

Voici un schéma qui peut représenter des nombres de 0 à 255:

Utilisez le premier octet de la mémoire (adresse 0) pour stocker l'entier.

Supposons maintenant que je veuille représenter des nombres supérieurs à 255. Bien sûr, je pourrais utiliser plus d'un octet pour représenter l'entier, mais tant qu'il s'agit d'un nombre fixe, il y aura finalement un entier si grand qu'il ne pourra pas être représenté par le schéma d'origine.

Voici un autre schéma qui devrait être en mesure de faire la tâche, mais il est probablement loin d'être efficace.

Utilisez simplement une sorte d'octet unique de "fin de numéro" et utilisez tous les octets précédents pour représenter le nombre. Évidemment, cet octet de "fin de nombre" ne peut être utilisé nulle part dans la représentation numérique, mais cela peut être réalisé en utilisant un système de numérotation base-255 (au lieu de base-256).

Cependant, c'est lent et probablement inefficace. Je veux en avoir un meilleur qui fonctionne mieux avec des valeurs faibles et qui évolue bien.

C'est essentiellement un système UUID. Je veux voir s'il est possible de créer un système UUID à performance rapide qui peut théoriquement évoluer pour être utilisé pendant des années, des milliers d'années, des millions d'années, sans avoir à être repensé.

storage numbers uuid Dmitri Shuralyov
la source
1
Voulez-vous quelque chose qui peut évoluer à l'infini (comme dans votre ouverture), ou pour des millions d'années (comme dans votre fermeture)? Les deux exigences sont (évidemment) complètement différentes. Le complément à deux sur une machine 64 bits évoluera pendant des millions d'années.
user16764
1
@ user16764, voulez-vous dire une seule variable entière 64 bits? Cela ne fonctionnera certainement pas: si 6 millions de personnes consomment 1 million d'UUID par seconde, cela durera à peine plus d'un mois.
Dmitri Shuralyov
1
Et combien de temps cela prendrait-il sur une machine 128 bits?
user16764
2
Les idées de la RFC 2550 , qui fournit une représentation ASCII lexicographique ordonnée pour des entiers positifs arbitrairement grands, peuvent être adaptables à cela. En fin de compte, il se décompose en un segment unaire qui code la longueur d'un segment base-26 qui code la longueur d'un segment base-10 - les deux dernières bases étant davantage liées à la représentation ASCII qu'à tout élément fondamental du schéma.
Random832
1
En supposant que vous générez des nombres de 128 bits séquentiellement: si nous limitons la capacité de calcul de tous les ordinateurs en donnant à chaque être humain un ordinateur pétaflop, alors il faudrait 9 millions d'années avant que ces nombres ne s'épuisent. Si d'un autre côté, chaque humain générait au hasard 600 millions de nombres à 128 bits, il y a 50% de chances qu'il génère 1 doublon. Est-ce que cela vous convient? ( en.wikipedia.org/wiki/Universally_unique_identifier ) Sinon, l'utilisation de 256 bits multiplie ces deux chiffres par 2 ^ 128 = 3,4 * 10 ^ 38, ce qui est plus que le carré de l'âge de l'univers en secondes.
Alex ten Brink

Réponses:

13

Une approche que j'ai utilisée: compter le nombre de bits 1 en tête, par exemple n. La taille du nombre est alors de 2 ^ n octets (y compris les 1 premiers bits). Prenez les bits après le premier 0 bit comme un entier et ajoutez la valeur maximale (plus un) qui peut être représentée par un nombre en utilisant ce codage en 2 ^ (n-1) octets.

Donc, 

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

Ce schéma permet à toute valeur non négative d'être représentée d'une seule manière.

(De manière équivalente, utilisé le nombre de bits 0 de tête.)

retracile
la source
1
Il était difficile pour moi de déterminer quelle réponse marquer comme acceptée, car je pense que beaucoup d'entre eux sont très instructifs et bons. Mais je pense que celui-ci est le mieux adapté à la question que j'ai posée (peut-être pas celle sous-jacente que j'avais en tête, qui est plus difficile à exprimer).
Dmitri Shuralyov
2
J'ai écrit un article plus approfondi avec un exemple d'implémentation et de considérations de conception.
retracile le
10

Il y a beaucoup de théorie basée sur ce que vous essayez de faire. Jetez un oeil à la page wiki sur les codes universels - il y a une liste assez exhaustive des méthodes de codage entier (dont certaines sont en fait utilisées dans la pratique).

Dans la compression de données, un code universel pour les entiers est un code de préfixe qui mappe les entiers positifs sur des mots de code binaires

Ou vous pouvez simplement utiliser les 8 premiers octets pour stocker la longueur du nombre dans certaines unités (les octets les plus probables), puis mettre les octets de données. Il serait très facile à mettre en œuvre, mais plutôt inefficace pour les petits nombres. Et vous seriez en mesure de coder un entier suffisamment longtemps pour remplir tous les lecteurs de données disponibles pour l'humanité :)

Matěj Zábský
la source
Merci pour ça, c'est très intéressant. Je voulais marquer cela comme une réponse acceptée, mais elle a pris la 2e place. C'est une très bonne réponse d'un point de vue théorique, l'OMI.
Dmitri Shuralyov
4

Que diriez-vous de laisser le nombre de 1 en tête plus le premier 0 être la taille (sizeSize) de la taille du nombre (numSize) en bits. NumSize est un nombre binaire qui donne la taille de la représentation numérique en octets, y compris les bits de taille. Les bits restants sont le nombre (num) en binaire. Pour un schéma d'entier positif, voici quelques exemples de numéros d'exemple:

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
la source
4

Que diriez-vous de cela: un octet pour la longueur, puis n octets pour le nombre (octet le moins significatif en premier). Répétez longueur + nombre tant que la longueur précédente était de 255.

Cela permet des nombres arbitrairement grands, mais est toujours facile à gérer et ne gaspille pas trop de mémoire.

user281377
la source
fNek: Il n'y a pas de limite supérieure. Par exemple, si vous avez besoin de 513 octets pour le nombre, la séquence d'octets est [255, b0, ..., b255,255, B256, ..., b511,2, b512, B513]
user281377
Désolé. Devrait apprendre à lire plus attentivement.
fNek
3

Pourquoi ne pas simplement utiliser 7 bits sur chaque octet et utiliser le 8e bit pour indiquer s'il y a un autre octet à suivre? Ainsi, 1-127 serait dans un octet, 128 serait représenté par 0x80 0x01, etc.

Paul Tomblin
la source
1
Ce schéma code seulement 128 valeurs sur 8 bits, ce qui est en fait moins efficace en termes d'espace que le deuxième schéma de codage proposé par le questionneur, où 255 valeurs sont codées sur 8 bits. Les deux schémas souffrent du fait que vous devez lire le nombre entier pour savoir de combien de stockage vous avez besoin pour le stocker.
Mark Booth
3
Vous devez donc scanner le numéro deux fois pour en faire une copie, alors quoi? Si je peux attendre un nombre infiniment grand, je peux l'attendre deux fois.
Russell Borogove
Bien que je ne l'ai pas précisé très attentivement, je recherche une solution aussi performante que possible (au lieu d'une solution qui corresponde simplement aux exigences; j'ai déjà décrit une réponse potentiellement inefficace dans ma question).
Dmitri Shuralyov
3

Les systèmes UUID sont basés sur une puissance de calcul finie (mais grande) dans un univers fini (mais grand). Le nombre d'UUID est important même par rapport à des choses absurdement grandes comme le nombre de particules dans l'univers. Le nombre d'UUID, avec un nombre quelconque de bits fixes, est cependant petit par rapport à l'infini.

Le problème avec l'utilisation de 0xFFFF pour représenter votre indicateur de fin de numéro est qu'il rend l'encodage de votre numéro moins efficace lorsque les nombres sont grands. Cependant, il semble que votre schéma UUID aggrave encore ce problème. Au lieu d'un octet sur 256 ignoré, vous avez maintenant tout l'espace UUID perdu. L'efficacité du calcul / reconnaissance (au lieu de l'espace) dépend beaucoup de votre ordinateur théorique (ce que je suppose que vous avez si vous parlez de l'infini). Pour une MT avec une bande et un contrôleur à états finis, tout schéma UUID est impossible à mettre à l'échelle efficacement (fondamentalement, le lemme de pompage vous empêche de dépasser efficacement un marqueur d'extrémité à longueur de bit fixe). Si vous ne supposez pas un contrôleur d'état fini, cela peut ne pas s'appliquer, mais vous devez penser à où vont les bits dans le processus de décodage / reconnaissance.

Si vous voulez simplement une meilleure efficacité que 1 octet sur 256, vous pouvez utiliser la longueur de bit de 1 que vous alliez utiliser pour votre schéma UUID. C'est 1 sur 2 ^ bits d'inefficacité.

Notez qu'il existe cependant d'autres schémas d'encodage. Le codage d'octets avec des délimiteurs se trouve être le plus facile à implémenter.

ccoakley
la source
2

Je suggère d'avoir un tableau d'octets (ou des entiers ou des longs) et un champ de longueur qui indique la longueur du nombre.

C'est à peu près l'approche utilisée par BigInteger de Java . L'espace d'adressage possible est énorme - assez facilement pour donner un UUID différent à chaque atome individuel dans l'univers :-)

Sauf si vous avez une très bonne raison de faire autrement, je vous suggère d'utiliser directement BigInteger (ou son équivalent dans d'autres langues). Plus besoin de réinventer la roue des grands nombres ...

mikera
la source
Vous ne pouvez pas coder la longueur du tableau lorsque le nombre de champs peut être infini.
Slawek
Je suis d'accord que l'utilisation d'une solution existante (en particulier celle qui a fait l'objet d'un examen professionnel) pour un problème donné, lorsque cela est possible, est préférable. Merci.
Dmitri Shuralyov
@Slawek: vrai, mais pour le cas d'utilisation décrit par l'OP (c'est-à-dire les UUID), un BigInteger est effectivement infini. De toute façon, vous ne pouvez pas coder des informations infinies sur un ordinateur avec une mémoire de taille finie, donc BigInteger est aussi bon que tout ce que vous êtes susceptible de réaliser.
mikera
2

Tout d'abord, merci à tous ceux qui ont apporté d'excellentes réponses à ma question relativement vague et abstraite.

Je voudrais apporter une réponse potentielle à laquelle j'ai pensé après avoir pensé à d'autres réponses. Ce n'est pas une réponse directe à la question posée, mais elle est pertinente.

Comme certaines personnes l'ont souligné, l'utilisation d'un entier de taille 64/128/256 bits vous donne déjà un très grand espace pour les UUID. Ce n'est évidemment pas infini, mais ...

Peut-être que ce serait une bonne idée d'utiliser simplement une taille fixe int (disons, 64 bits pour commencer) jusqu'à ce que 64 bits ne soit pas suffisant (ou proche). Ensuite, en supposant que vous ayez un tel accès à toutes les instances précédentes des UUID, il vous suffit de les mettre à niveau en entiers 128 bits et de prendre cela comme votre taille fixe d'entier.

Si le système autorise de telles pauses / interruptions de service, et parce que de telles opérations de "reconstruction" doivent se produire assez rarement, les avantages (un système très simple, rapide et facile à mettre en œuvre) l'emporteront peut-être sur les inconvénients (devoir reconstruire tous les entiers précédemment alloués). à une nouvelle taille de bit entière).

Dmitri Shuralyov
la source