Ein gutes Schema zur Darstellung von Ganzzahlen von 0 bis unendlich, vorausgesetzt, Sie haben einen unendlichen linearen Binärspeicher?

10

Ich möchte, dass ein Schema ganzzahlige Zahlen beginnend mit 0 ohne Einschränkung darstellt (vorausgesetzt, der Zugriff auf unendlichen linearen Speicher).

Hier ist ein Schema, das Zahlen von 0 bis 255 darstellen kann:

Verwenden Sie das erste Byte des Speichers (Adresse 0), um die Ganzzahl zu speichern.

Angenommen, ich möchte Zahlen darstellen, die größer als 255 sind. Natürlich könnte ich mehr als 1 Byte verwenden, um die Ganzzahl darzustellen, aber solange es sich um eine feste Zahl handelt, wird es schließlich eine Ganzzahl geben, die so groß ist, dass sie nicht durch dargestellt werden kann das ursprüngliche Schema.

Hier ist ein weiteres Schema, das die Aufgabe ausführen sollte, aber wahrscheinlich alles andere als effizient ist.

Verwenden Sie einfach eine Art eindeutiges "Ende der Zahl" -Byte und verwenden Sie alle vorherigen Bytes, um die Zahl darzustellen. Offensichtlich kann dieses "Ende der Zahl" -Byte nirgendwo in der Zahlendarstellung verwendet werden, aber dies kann erreicht werden, indem ein Nummerierungssystem der Basis 255 (anstelle der Nummer 256) verwendet wird.

Das ist jedoch langsam und wahrscheinlich ineffizient. Ich möchte eine bessere haben, die mit niedrigen Werten besser abschneidet und gut skaliert.

Im Wesentlichen handelt es sich um ein UUID-System. Ich möchte sehen, ob es möglich ist, ein schnelles UUID-System zu erstellen, das theoretisch für Jahre, Tausende von Jahren, Millionen von Jahren skaliert werden kann, ohne dass es neu gestaltet werden muss.

storage numbers uuid Dmitri Shuralyov
quelle
1
Möchten Sie etwas, das sich unendlich skalieren lässt (wie bei Ihrer Eröffnung) oder für Millionen von Jahren (wie bei Ihrer Schließung)? Die beiden Anforderungen sind (offensichtlich) völlig unterschiedlich. Zwei Komplemente auf einem 64-Bit-Computer werden sich über Millionen von Jahren skalieren lassen.
user16764
1
@ user16764, meinst du eine einzelne 64-Bit-Ganzzahlvariable? Das wird sicherlich nicht funktionieren: Wenn 6 Millionen Menschen 1 Million UUIDs pro Sekunde verbrauchen, wird es kaum länger als einen Monat dauern.
Dmitri Shuralyov
1
Und wie lange würde es auf einem 128-Bit-Computer dauern?
user16764
2
Die Ideen in RFC 2550 , das eine lexikografisch geordnete ASCII-Darstellung für beliebig große positive ganze Zahlen liefert, können daran angepasst werden. Letztendlich zerfällt es in ein unäres Segment, das die Länge eines Basis-26-Segments codiert, das die Länge eines Basis-10-Segments codiert - wobei die beiden letztgenannten Basen mehr mit der ASCII-Darstellung als mit irgendetwas grundlegendem für das Schema zu tun haben.
Random832
1
Angenommen, Sie generieren nacheinander 128-Bit-Zahlen: Wenn wir die Rechenkapazität aller Computer übersteigen, indem wir jedem Menschen einen Petaflop-Computer geben, würde es 9 Millionen Jahre dauern, bis diese Zahlen aufgebraucht sind. Wenn andererseits jeder Mensch zufällig 600 Millionen 128-Bit-Zahlen erzeugen würde, besteht eine 50% ige Chance, dass er 1 Duplikat erzeugt. Ist das gut genug für dich ( en.wikipedia.org/wiki/Universally_unique_identifier ) Wenn nicht, multipliziert die Verwendung von 256 Bit diese beiden Zahlen mit 2 ^ 128 = 3,4 * 10 ^ 38, was mehr als das Quadrat des Alters des Universums in Sekunden ist.
Alex Ten Brink

Antworten:

13

Ein Ansatz, den ich verwendet habe: Zählen Sie beispielsweise die Anzahl der führenden 1 Bits n. Die Größe der Zahl beträgt dann 2 ^ n Bytes (einschließlich der führenden 1 Bits). Nehmen Sie die Bits nach dem ersten 0-Bit als Ganzzahl und addieren Sie den Maximalwert (plus eins), der durch eine Zahl dargestellt werden kann, indem Sie diese Codierung in 2 ^ (n-1) Bytes verwenden.

Somit, 

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

Mit diesem Schema kann jeder nicht negative Wert auf genau eine Weise dargestellt werden.

(Entspricht entsprechend der Anzahl der führenden 0-Bits.)

retracile
quelle
1
Es war schwer für mich herauszufinden, welche Antwort als akzeptiert zu markieren ist, da ich denke, dass viele von ihnen sehr informativ und gut sind. Aber ich denke, dies passt am besten zu der Frage, die ich gestellt habe (möglicherweise nicht die zugrunde liegende, die ich mir vorgestellt habe und die schwerer auszudrücken ist).
Dmitri Shuralyov
2
Ich habe einen ausführlicheren Artikel mit einem Beispiel für Implementierungs- und Designüberlegungen geschrieben.
Retracile
10

Es gibt eine Menge Theorie, die darauf basiert, was Sie versuchen zu tun. Werfen Sie einen Blick auf die Wiki-Seite über universelle Codes - es gibt eine ziemlich ausführliche Liste von Ganzzahl-Codierungsmethoden (von denen einige tatsächlich in der Praxis verwendet werden).

Bei der Datenkomprimierung ist ein universeller Code für Ganzzahlen ein Präfixcode, der die positiven Ganzzahlen auf binäre Codewörter abbildet

Oder Sie können einfach die ersten 8 Bytes verwenden, um die Länge der Nummer in einigen Einheiten (höchstwahrscheinlich Bytes) zu speichern und dann die Datenbytes abzulegen. Es wäre sehr einfach zu implementieren, aber für kleine Zahlen eher ineffizient. Und Sie könnten eine Ganzzahl lange genug codieren, um alle Datenlaufwerke zu füllen, die der Menschheit zur Verfügung stehen :)

Matěj Zábský
quelle
Danke dafür, das ist sehr interessant. Ich wollte dies als akzeptierte Antwort markieren, aber es belegte den 2. Platz. Dies ist aus theoretischer Sicht eine sehr gute Antwort, IMO.
Dmitri Shuralyov
4

Wie wäre es, wenn die Anzahl der führenden Einsen plus der ersten 0 die Größe (sizeSize) der Zahlengröße (numSize) in Bits ist? Die numSize ist eine Binärzahl, die die Größe der Zahlendarstellung in Bytes einschließlich der Größenbits angibt. Die verbleibenden Bits sind die binäre Zahl (num). Für ein positives Ganzzahlschema sind hier einige Beispielbeispielnummern aufgeführt:

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
quelle
4

Wie wäre es damit: Ein Byte für die Länge, dann n Bytes für die Zahl (niedrigstwertiges Byte zuerst). Wiederholen Sie Länge + Nummer, solange die vorherige Länge 255 betrug.

Dies ermöglicht beliebig große Zahlen, ist aber dennoch einfach zu handhaben und verschwendet nicht zu viel Speicher.

user281377
quelle
fNek: Es gibt keine Obergrenze. Wenn Sie beispielsweise 513 Bytes für die Nummer benötigen, lautet die Bytesequenz [255, b0, ..., b255,255, b256, ..., b511,2, b512, b513]
user281377
Es tut uns leid. Sollte lernen, genauer zu lesen.
fNek
3

Warum nicht einfach 7 Bits pro Byte verwenden und mit dem 8. Bit angeben, ob ein weiteres Byte folgen soll? 1-127 wäre also in einem Byte, 128 würde durch 0x80 0x01 usw. dargestellt.

Paul Tomblin
quelle
1
Dieses Schema codiert nur 128 Werte in jeweils 8 Bits, was tatsächlich weniger platzsparend ist als das vom Fragesteller vorgeschlagene zweite Codierungsschema, bei dem 255 Werte in jeweils 8 Bits codiert werden. Beide Schemata leiden unter der Tatsache, dass Sie die ganze Zahl einlesen müssen, um herauszufinden, wie viel Speicher Sie zum Speichern benötigen.
Mark Booth
3
Sie müssen die Nummer also zweimal scannen, um eine Kopie davon zu erstellen. Na und? Wenn ich auf eine unendlich große Zahl warten kann, kann ich zweimal darauf warten.
Russell Borogove
Obwohl ich es nicht sehr sorgfältig spezifiziert habe, suche ich nach einer Lösung, die so effizient wie möglich arbeitet (anstelle einer Lösung, die einfach den Anforderungen entspricht; ich habe in meiner Frage bereits eine mögliche ineffiziente Antwort beschrieben).
Dmitri Shuralyov
3

UUID-Systeme basieren auf endlicher (aber großer) Rechenleistung in einem endlichen (aber großen) Universum. Die Anzahl der UUIDs ist groß, selbst im Vergleich zu absurd großen Dingen wie der Anzahl der Partikel im Universum. Die Anzahl der UUIDs mit einer beliebigen Anzahl fester Bits ist jedoch im Vergleich zur Unendlichkeit gering.

Das Problem bei der Verwendung von 0xFFFF zur Darstellung Ihres End-of-Number-Flags besteht darin, dass Ihre Nummerncodierung bei großen Zahlen weniger effizient ist. Es scheint jedoch, dass Ihr UUID-Schema dieses Problem noch verschlimmert. Anstatt eines von 256 Bytes zu überspringen, wird jetzt der gesamte UUID-Speicherplatz verschwendet. Die Effizienz der Berechnung / Erkennung (anstelle des Speicherplatzes) hängt stark von Ihrem theoretischen Computer ab (den Sie vermutlich haben, wenn Sie über Unendlichkeit sprechen). Bei einem TM mit einem Band und einem Finite-State-Controller ist es unmöglich, ein UUID-Schema effizient zu skalieren (im Grunde verhindert das Pump-Lemma, dass Sie sich effizient über einen Endmarker mit fester Bitlänge hinausbewegen). Wenn Sie keinen Finite-State-Controller annehmen, trifft dies möglicherweise nicht zu, Sie müssen jedoch darüber nachdenken, wohin die Bits beim Decodierungs- / Erkennungsprozess gehen.

Wenn Sie nur eine bessere Effizienz als 1 von 256 Bytes wünschen, können Sie die Bitlänge von 1s verwenden, die Sie für Ihr UUID-Schema verwenden wollten. Das ist 1 von 2 ^ Bit Länge in Ineffizienz.

Beachten Sie jedoch, dass es andere Codierungsschemata gibt. Die Bytecodierung mit Trennzeichen ist einfach am einfachsten zu implementieren.

ccoakley
quelle
2

Ich würde vorschlagen, ein Array von Bytes (oder Ints oder Longs) und ein Längenfeld zu haben, das angibt, wie lang die Zahl ist.

Dies ist ungefähr der Ansatz von Javas BigInteger . Der daraus mögliche Adressraum ist riesig - leicht genug, um jedem einzelnen Atom im Universum eine andere UUID zu geben :-)

Sofern Sie keinen guten Grund haben, etwas anderes zu tun, würde ich vorschlagen, BigInteger direkt (oder in anderen Sprachen gleichwertig) zu verwenden. Keine besondere Notwendigkeit, das große Zahlenrad neu zu erfinden ....

mikera
quelle
Sie können die Länge des Arrays nicht codieren, wenn die Anzahl der Felder unendlich sein kann.
Slawek
Ich bin damit einverstanden, dass die Verwendung einer vorhandenen Lösung (insbesondere einer Lösung, die einer professionellen Prüfung unterzogen wurde) für ein bestimmtes Problem nach Möglichkeit bevorzugt wird. Vielen Dank.
Dmitri Shuralyov
@Slawek: true, aber für den Anwendungsfall, den das OP beschreibt (dh UUIDs), ist eine BigInteger praktisch unendlich. Sie können ohnehin keine unendlichen Informationen in einem Computer mit endlichem Speicher codieren, daher ist BigInteger so gut wie alles andere, was Sie wahrscheinlich erreichen werden.
Mikera
2

Zunächst einmal vielen Dank an alle, die großartige Antworten auf meine relativ vage und abstrakte Frage gegeben haben.

Ich möchte eine mögliche Antwort einbringen, an die ich gedacht habe, nachdem ich über andere Antworten nachgedacht habe. Es ist keine direkte Antwort auf die gestellte Frage, aber es ist relevant.

Wie einige Leute betonten, bietet die Verwendung einer Ganzzahl mit einer Bitgröße von 64/128/256 bereits einen sehr großen Platz für UUIDs. Offensichtlich ist es nicht unendlich, aber ...

Vielleicht ist es eine gute Idee, nur eine feste Größe int zu verwenden (z. B. 64-Bit, um zu beginnen), bis 64-Bit nicht mehr ausreicht (oder nahe daran liegt). Angenommen, Sie haben einen solchen Zugriff auf alle vorherigen Instanzen der UUIDs, aktualisieren Sie sie einfach alle auf 128-Bit-Ints und nehmen Sie dies als Ihre feste Ganzzahlgröße.

Wenn das System solche Pausen / Unterbrechungen des Dienstes zulässt und solche "Wiederherstellungs" -Operationen ziemlich selten auftreten sollten, überwiegen möglicherweise die Vorteile (ein sehr einfaches, schnelles und einfach zu implementierendes System) die Nachteile (alle zuvor zugewiesenen Ganzzahlen müssen neu erstellt werden) auf eine neue ganzzahlige Bitgröße).

Dmitri Shuralyov
quelle