Dobry schemat reprezentujący liczby całkowite od 0 do nieskończoności, zakładając, że masz nieskończoną liniową pamięć binarną?

10

Chciałbym, aby schemat reprezentował liczby całkowite zaczynające się od 0, bez żadnych ograniczeń (zakładając dostęp do nieskończonej pamięci liniowej).

Oto schemat, który może reprezentować liczby od 0 do 255:

Użyj pierwszego bajtu pamięci (adres 0), aby zapisać liczbę całkowitą.

Załóżmy teraz, że chcę reprezentować liczby większe niż 255. Oczywiście mógłbym użyć więcej niż 1 bajtu do przedstawienia liczby całkowitej, ale dopóki jest to stała liczba, w końcu będzie liczba całkowita tak duża, że ​​nie będzie mogła być reprezentowana przez oryginalny schemat.

Oto kolejny schemat, który powinien być w stanie wykonać zadanie, ale prawdopodobnie nie jest skuteczny.

Wystarczy użyć jakiegoś unikalnego bajtu „końca liczby” i użyć wszystkich poprzednich bajtów do przedstawienia liczby. Oczywiście tego bajtu „końca liczby” nie można użyć w dowolnym miejscu w reprezentacji liczb, ale można to osiągnąć za pomocą systemu numeracji base-255 (zamiast base-256).

Jest to jednak powolne i prawdopodobnie nieefektywne. Chcę mieć lepszy, który działa lepiej przy niskich wartościach i dobrze się skaluje.

Zasadniczo jest to system UUID. Chcę sprawdzić, czy można stworzyć szybko działający system UUID, który teoretycznie można skalować do użycia przez lata, tysiące lat, miliony lat, bez konieczności przeprojektowywania.

storage numbers uuid Dmitrij Shuralyov
źródło
1
Czy chcesz czegoś, co można skalować w nieskończoność (jak na początku), czy na miliony lat (jak na końcu)? Te dwa wymagania są (oczywiście) zupełnie inne. Dwóch uzupełnień na 64-bitowej maszynie będzie skalować przez miliony lat.
user16764
1
@ user16764, czy masz na myśli pojedynczą 64-bitową zmienną całkowitą? To na pewno nie zadziała: jeśli 6 milionów ludzi spożywa 1 milion UUID na sekundę, nie potrwa to dłużej niż miesiąc.
Dmitri Shuralyov
1
A jak długo potrwa na komputerze 128-bitowym?
user16764,
2
Pomysły w RFC 2550 , która zapewnia uporządkowaną leksykograficznie reprezentację ASCII dla dowolnie dużych liczb całkowitych dodatnich, można do tego dostosować. Ostatecznie rozpada się na segment jednoargumentowy, który koduje długość segmentu base-26, który koduje długość segmentu base-10 - te dwie ostatnie zasady są bardziej związane z reprezentacją ASCII niż z czymkolwiek fundamentalnym dla schematu.
Random832
1
Zakładając, że generujesz kolejno 128-bitowe liczby: jeśli przekroczymy górną granicę mocy obliczeniowej wszystkich komputerów, dając każdemu człowiekowi komputer petaflop, upłynie 9 milionów lat, zanim te liczby się wyczerpią. Jeśli z drugiej strony każdy człowiek wygeneruje losowo 600 milionów 128-bitowych liczb, istnieje 50% szansa, że ​​wygeneruje 1 duplikat. Czy to ci wystarczy? ( en.wikipedia.org/wiki/Universally_unique_identifier ) Jeśli nie, użycie 256 bitów zwielokrotnia obie te liczby przez 2 ^ 128 = 3,4 * 10 ^ 38, co w sekundach przekracza kwadrat wieku wszechświata.
Alex ten Brink

Odpowiedzi:

13

Podejście, które zastosowałem: policz liczbę wiodących 1 bitów, powiedzmy n. Rozmiar liczby wynosi wtedy 2 ^ n bajtów (w tym 1 pierwszy bit). Weź bity po pierwszych 0 bitach jako liczbę całkowitą i dodaj maksymalną wartość (plus jeden), która może być reprezentowana przez liczbę przy użyciu tego kodowania w 2 ^ (n-1) bajtach.

A zatem, 

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

Ten schemat pozwala przedstawić dowolną nieujemną wartość dokładnie w jeden sposób.

(Odpowiednio użyto liczby wiodących 0 bitów.)

retracile
źródło
1
Trudno mi było ustalić, którą odpowiedź oznaczyć jako zaakceptowaną, ponieważ uważam, że wiele z nich jest bardzo pouczających i dobrych. Ale myślę, że to najlepiej pasuje do pytania, które zadałem (być może nie do tego, które miałem na myśli, co trudniej wyrazić).
Dmitri Shuralyov
2
Napisałem bardziej szczegółowy artykuł z przykładowymi rozważaniami dotyczącymi implementacji i projektowania.
retracile,
10

Istnieje wiele teorii opartych na tym, co próbujesz zrobić. Zajrzyj na stronę wiki o kodach uniwersalnych - istnieje dość wyczerpująca lista metod kodowania liczb całkowitych (niektóre z nich są faktycznie stosowane w praktyce).

W kompresji danych uniwersalny kod liczb całkowitych jest kodem prefiksu, który mapuje dodatnie liczby całkowite na binarne słowa kodowe

Możesz też użyć pierwszych 8 bajtów do przechowywania długości liczb w niektórych jednostkach (najprawdopodobniej bajtów), a następnie umieścić bajty danych. Byłby bardzo łatwy do wdrożenia, ale raczej nieefektywny w przypadku małych liczb. I będziesz w stanie zakodować liczbę całkowitą wystarczająco długo, aby wypełnić wszystkie dyski danych dostępne ludzkości :)

Matěj Zábský
źródło
Dzięki za to, to bardzo interesujące. Chciałem zaznaczyć to jako zaakceptowaną odpowiedź, ale zajęło 2 miejsce. To bardzo dobra odpowiedź z teoretycznego punktu widzenia, IMO.
Dmitri Shuralyov
4

Co powiesz na to, aby liczba wiodących jedynek plus pierwsze 0 była rozmiarem (sizeSize) wielkości liczbowej (numSize) w bitach. NumSize to liczba binarna, która podaje rozmiar reprezentacji liczby w bajtach, w tym w bitach wielkości. Pozostałe bity to liczba (liczba) w systemie binarnym. Dla schematu dodatnich liczb całkowitych oto kilka przykładowych liczb:

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
źródło
4

Co powiesz na to: jeden bajt na długość, a następnie n bajtów na liczbę (najpierw najmniej znaczący bajt). Powtórz długość + liczbę, o ile poprzednia długość wynosiła 255.

Pozwala to na dowolnie duże liczby, ale nadal jest łatwe w obsłudze i nie marnuje zbyt dużo pamięci.

użytkownik 281377
źródło
fNek: Nie ma górnej granicy. Na przykład, jeśli potrzebujesz 513 bajtów dla liczby, sekwencja bajtów to [255, b0, ..., b255,255, b256, ..., b511,2, b512, b513]
281377
Przepraszam. Powinieneś nauczyć się czytać uważniej.
fNek
3

Dlaczego po prostu nie użyć 7 bitów z każdego bajtu i użyć ósmego bitu, aby wskazać, czy jest kolejny bajt do naśladowania? Więc 1-127 będzie w jednym bajcie, 128 będzie reprezentowane przez 0x80 0x01 itd.

Paul Tomblin
źródło
1
Ten schemat koduje tylko 128 wartości na każde 8 bitów, co w rzeczywistości jest mniej efektywne pod względem przestrzeni niż drugi schemat kodowania zaproponowany przez pytającego, w którym 255 wartości jest kodowanych na każde 8 bitów. Oba schematy cierpią z powodu tego, że musisz przeczytać całą liczbę, aby dowiedzieć się, ile miejsca potrzebujesz do przechowywania.
Mark Booth,
3
Musisz więc zeskanować numer dwa razy, aby zrobić jego kopię, więc co? Jeśli mogę poczekać na jedną nieskończenie dużą liczbę, mogę na nią poczekać dwa razy.
Russell Borogove
Chociaż nie sprecyzowałem go bardzo dokładnie, szukam rozwiązania, które działa tak wydajnie, jak to możliwe (zamiast rozwiązania, które po prostu spełnia wymagania; w moim pytaniu już opisałem jedną potencjalnie nieefektywną odpowiedź).
Dmitri Shuralyov
3

Systemy UUID oparte są na skończonej (ale dużej) mocy obliczeniowej we skończonym (ale dużym) wszechświecie. Liczba UUID jest duża, nawet w porównaniu z absurdalnie dużymi rzeczami, takimi jak liczba cząstek we wszechświecie. Liczba UUID, przy dowolnej liczbie stałych bitów, jest jednak niewielka w porównaniu do nieskończoności.

Problem z użyciem 0xFFFF do przedstawienia flagi końca numeru polega na tym, że kodowanie liczb jest mniej wydajne, gdy liczby są duże. Wydaje się jednak, że Twój schemat UUID jeszcze bardziej pogarsza ten problem. Zamiast jednego z 256 bajtów pominiętych, masz teraz zmarnowane całe miejsce UUID. Wydajność obliczeń / rozpoznawania (zamiast przestrzeni) zależy w dużej mierze od twojego komputera teoretycznego (który, jak zakładam, masz, jeśli mówisz o nieskończoności). W przypadku TM z taśmą i kontrolerem stanu skończonego żaden schemat UUID jest niemożliwy do skutecznego skalowania (w zasadzie lemat pompowania nie pozwala wydajnie przejść poza znacznik końcowy o stałej długości bitów). Jeśli nie zakładasz kontrolera stanu skończonego, może to nie mieć zastosowania, ale musisz pomyśleć o tym, gdzie bity idą w procesie dekodowania / rozpoznawania.

Jeśli chcesz po prostu lepszej wydajności niż 1 z 256 bajtów, możesz użyć dowolnej długości 1s, która miałaby być używana dla twojego schematu UUID. To 1 z 2 ^ długości bitowej nieefektywności.

Pamiętaj jednak, że istnieją inne schematy kodowania. Kodowanie bajtów z ogranicznikami jest najłatwiejsze do zaimplementowania.

Ccoakley
źródło
2

Proponuję mieć tablicę bajtów (lub liczb całkowitych lub długich) i pole długości określające, jak długo jest to liczba.

Z grubsza takie podejście stosuje BigInteger Javy . Możliwa z tego przestrzeń adresowa jest ogromna - na tyle łatwo, że każdemu atomowi we wszechświecie nadaje się inny UUID :-)

Jeśli nie masz bardzo dobrego powodu, aby zrobić inaczej, sugeruję użycie bezpośrednio BigInteger (lub jego odpowiednika w innych językach). Nie ma szczególnej potrzeby wymyślania koła z dużą liczbą ...

mikera
źródło
Nie można zakodować długości tablicy, gdy liczba pól może być nieskończona.
Sławek
Zgadzam się, że preferowane jest korzystanie z istniejącego rozwiązania (zwłaszcza takiego, które zostało poddane profesjonalnej kontroli) dla danego problemu, jeśli to możliwe. Dzięki.
Dmitri Shuralyov
@ Sławek: prawda, ale w przypadku użycia, który opisuje OP (tj. UUID), BigInteger jest faktycznie nieskończony. W każdym razie nie możesz zakodować nieskończonych informacji na żadnym komputerze z pamięcią o skończonej wielkości, więc BigInteger jest tak dobry, jak wszystko, co możesz osiągnąć.
mikera
2

Przede wszystkim dziękuję wszystkim, którzy wnieśli świetne odpowiedzi na moje stosunkowo niejasne i abstrakcyjne pytanie.

Chciałbym przekazać potencjalną odpowiedź, o której pomyślałem po zastanowieniu się nad innymi odpowiedziami. Nie jest to bezpośrednia odpowiedź na zadane pytanie, ale jest istotna.

Jak niektórzy zauważyli, użycie liczby całkowitej o rozmiarze 64/128/256 bitów już zapewnia bardzo dużą przestrzeń dla UUID. Oczywiście nie jest to nieskończone, ale ...

Być może dobrym pomysłem jest użycie int o stałym rozmiarze (powiedzmy 64-bit na początek), dopóki 64-bit nie będzie wystarczający (lub blisko niego). Następnie, zakładając, że masz taki dostęp do wszystkich poprzednich instancji identyfikatorów UUID, po prostu zaktualizuj je wszystkie do 128-bitowych liczb całkowitych i wybierz jako liczbę całkowitą o ustalonym rozmiarze.

Jeśli system pozwala na takie przerwy / przerwy w świadczeniu usług, a ponieważ takie operacje „przebudowywania” powinny odbywać się dość rzadko, być może korzyści (bardzo prosty, szybki i łatwy do wdrożenia system) przeważą wady (konieczność przebudowania wszystkich wcześniej przydzielonych liczb całkowitych) do nowego całkowitego rozmiaru bitu).

Dmitrij Shuralyov
źródło