Um bom esquema para representar números inteiros de 0 a infinito, supondo que você tenha armazenamento binário linear infinito?

10

Eu gostaria que um esquema representasse números inteiros começando com 0, sem nenhum limite (assumindo acesso ao armazenamento linear infinito).

Aqui está um esquema que pode representar números de 0 a 255:

Use o primeiro byte do armazenamento (endereço 0) para armazenar o número inteiro.

Agora, suponha que eu queira representar números maiores que 255. É claro que eu poderia usar mais de 1 byte para representar o número inteiro, mas desde que seja um número fixo, haverá eventualmente um número inteiro tão grande que não pode ser representado por o esquema original.

Aqui está outro esquema que deve ser capaz de executar a tarefa, mas provavelmente está longe de ser eficiente.

Basta usar algum tipo de byte "final de número" exclusivo e usar todos os bytes anteriores para representar o número. Obviamente, esse byte de "fim de número" não pode ser usado em nenhum lugar da representação numérica, mas isso pode ser alcançado usando um sistema de numeração de base 255 (em vez de 256 de base).

No entanto, isso é lento e provavelmente ineficiente. Quero ter um melhor que tenha um desempenho melhor com valores baixos e dimensione bem.

Essencialmente, é um sistema UUID. Quero ver se é possível criar um sistema UUID de desempenho rápido que, teoricamente, pode ser escalado para uso por anos, milhares de anos, milhões de anos, sem precisar ser redesenhado.

storage numbers uuid Dmitri Shuralyov
fonte
11
Você quer algo que possa escalar infinitamente (como na sua abertura) ou por milhões de anos (como na sua conclusão)? Os dois requisitos são (obviamente) completamente diferentes. O complemento de dois em uma máquina de 64 bits será escalado por milhões de anos.
precisa saber é o seguinte
11
@ user16764, você quer dizer uma única variável inteira de 64 bits? Isso certamente não funcionará: se 6 milhões de pessoas estão consumindo 1 milhão de UUIDs por segundo, durará apenas mais de um mês.
Dmitri Shuralyov
11
E quanto tempo levaria em uma máquina de 128 bits?
precisa saber é o seguinte
2
As idéias na RFC 2550 , que fornece uma representação ASCII lexicográfica ordenada para números inteiros positivos arbitrariamente grandes, podem ser adaptáveis ​​a isso. Em última análise, divide-se em um segmento unário que codifica o comprimento de um segmento da base 26 que codifica o comprimento de um segmento da base 10 - as duas últimas bases estão mais relacionadas à representação ASCII do que qualquer coisa fundamental para o esquema.
precisa saber é o seguinte
11
Supondo que você gere números de 128 bits sequencialmente: se limitarmos a capacidade computacional de todos os computadores, dando a cada humano um computador petaflop, levaria 9 milhões de anos antes que esses números se esgotassem. Se, por outro lado, todo ser humano gerar aleatoriamente 600 milhões de números de 128 bits, há 50% de chance de gerar 1 duplicata. Isso é bom o suficiente para você? ( en.wikipedia.org/wiki/Universally_unique_identifier ) Caso contrário, o uso de 256 bits multiplica essas duas figuras por 2 ^ 128 = 3,4 * 10 ^ 38, que é mais do que o quadrado da idade do universo em segundos.
Alex ten Brink

Respostas:

13

Uma abordagem que usei: conte o número dos 1 bits iniciais, digamos n. O tamanho do número é então 2 ^ n bytes (incluindo os 1 bits iniciais). Pegue os bits após o primeiro 0 bit como um número inteiro e adicione o valor máximo (mais um) que pode ser representado por um número usando essa codificação em 2 ^ (n-1) bytes.

Portanto, 

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

Esse esquema permite que qualquer valor não negativo seja representado exatamente de uma maneira.

(Equivalentemente, usou o número de 0 bits iniciais.)

retrátil
fonte
11
Foi difícil para mim descobrir qual resposta marcar como aceita, porque acho que muitas delas são muito informativas e boas. Mas acho que este é o mais adequado para a pergunta que fiz (possivelmente não a subjacente que eu tinha em mente, que é mais difícil de expressar).
Dmitri Shuralyov
2
Escrevi um artigo mais aprofundado com um exemplo de implementação e considerações de design.
retracile
10

Há muita teoria baseada no que você está tentando fazer. Dê uma olhada na página da wiki sobre códigos universais - há uma lista exaustiva de métodos de codificação de números inteiros (alguns dos quais estão realmente sendo usados ​​na prática).

Na compactação de dados, um código universal para números inteiros é um código de prefixo que mapeia os números inteiros positivos em palavras de código binárias

Ou você pode simplesmente usar os primeiros 8 bytes para armazenar o comprimento do número em algumas unidades (bytes mais prováveis) e depois colocar os bytes dos dados. Seria muito fácil de implementar, mas ineficiente para pequenos números. E você seria capaz de codificar um número inteiro por tempo suficiente para preencher todas as unidades de dados disponíveis para a humanidade :)

Matěj Zábský
fonte
Obrigado por isso, é muito interessante. Eu queria marcar isso como resposta aceita, mas ficou em 2º lugar. Esta é uma resposta muito boa do ponto de vista teórico, IMO.
Dmitri Shuralyov
4

Que tal deixar que o número de 1s iniciais e o primeiro 0 sejam o tamanho (sizeSize) do tamanho do número (numSize) em bits. O numSize é um número binário que fornece o tamanho da representação numérica em bytes, incluindo os bits de tamanho. Os bits restantes são o número (num) em binário. Para um esquema inteiro positivo, aqui estão alguns exemplos de números de exemplo:

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

Que tal: Um byte para o comprimento, depois n bytes para o número (primeiro byte menos significativo). Repita o comprimento + número, desde que o comprimento anterior fosse 255.

Isso permite números arbitrariamente grandes, mas ainda é fácil de manusear e não desperdiça muita memória.

user281377
fonte
fNek: Não há limite superior. Por exemplo, se você precisar de 513 bytes para o número, a sequência de bytes será [255, b0, ..., b255,255, b256, ..., b511,2, b512, b513]
user281377
Desculpa. Deve aprender a ler com mais cuidado.
fNek
3

Por que não usar apenas 7 bits de cada byte e usar o 8º bit para indicar se há outro byte a seguir? Portanto, 1-127 estaria em um byte, 128 seria representado por 0x80 0x01 etc.

Paul Tomblin
fonte
11
Esse esquema codifica apenas 128 valores a cada 8 bits, o que na verdade é menos eficiente em termos de espaço que o segundo esquema de codificação proposto pelo questionador, onde 255 valores são codificados a cada 8 bits. Ambos os esquemas sofrem com o fato de que você precisa ler o número inteiro para descobrir quanto armazenamento você precisa para armazená-lo.
Mark Booth
3
Então, você precisa digitalizar o número duas vezes para fazer uma cópia, e daí? Se posso esperar por um número infinitamente grande, posso esperar duas vezes.
Russell Borogove
Embora não o tenha especificado com muito cuidado, estou procurando uma solução com o desempenho mais eficiente possível (em vez de uma solução que simplesmente atenda aos requisitos; já descrevi uma resposta potencialmente ineficiente na minha pergunta).
Dmitri Shuralyov
3

Os sistemas UUID são baseados no poder de computação finito (mas grande) em um universo finito (mas grande). O número de UUIDs é grande, mesmo quando comparado a coisas absurdamente grandes, como o número de partículas no universo. O número de UUIDs, com qualquer número de bits fixos, é pequeno, no entanto, comparado ao infinito.

O problema com o uso de 0xFFFF para representar seu sinalizador de final de número é que isso torna a codificação do número menos eficiente quando os números são grandes. No entanto, parece que o seu esquema UUID torna esse problema ainda pior. Em vez de um dos 256 bytes ignorados, agora você tem todo o espaço UUID desperdiçado. A eficiência da computação / reconhecimento (em vez do espaço) depende muito do seu computador teórico (o que, suponho que você tenha, se estiver falando de infinito). Para uma TM com fita e controlador de estado finito, é impossível escalar com eficiência qualquer esquema UUID (basicamente, o lema de bombeamento impede que você se mova além de um marcador final de comprimento de bit fixo com eficiência). Se você não assume um controlador de estado finito, isso pode não se aplicar, mas você precisa pensar sobre onde os bits vão no processo de decodificação / reconhecimento.

Se você quer uma eficiência melhor que 1 em 256 bytes, pode usar o tamanho de 1s que você usaria para o seu esquema UUID. Isso representa 1 em 2 ^ bits de comprimento em ineficiência.

Observe que existem outros esquemas de codificação. A codificação de bytes com delimitadores é a mais fácil de implementar.

ccoakley
fonte
2

Eu sugiro ter uma matriz de bytes (ou ints ou longs) e um campo de comprimento que diga quanto tempo o número é.

Essa é aproximadamente a abordagem usada pelo BigInteger do Java . O espaço de endereço possível disso é enorme - com facilidade suficiente para fornecer um UUID diferente para cada átomo individual do universo :-)

A menos que você tenha uma boa razão para fazer o contrário, sugiro que você use o BigInteger diretamente (ou seu equivalente em outros idiomas). Não é necessário reinventar a grande roda de números ....

Mikera
fonte
Você não pode codificar o comprimento da matriz quando o número de campos puder ser infinito.
Slawek
Concordo que é preferível usar uma solução existente (especialmente uma que tenha sido submetida a exame profissional) para um determinado problema, quando possível. Obrigado.
Dmitri Shuralyov
@ Slawwe: true, mas para o caso de uso que o OP está descrevendo (por exemplo, UUIDs), um BigInteger é efetivamente infinito. Você não pode codificar informações infinitas em nenhum computador com memória de tamanho finito, portanto o BigInteger é tão bom quanto qualquer outra coisa que você provavelmente conseguirá.
Mikera
2

Antes de tudo, obrigado a todos que contribuíram com ótimas respostas para minha pergunta relativamente vaga e abstrata.

Gostaria de contribuir com uma resposta potencial em que pensei depois de pensar em outras respostas. Não é uma resposta direta à pergunta, mas é relevante.

Como algumas pessoas apontaram, o uso de um número inteiro de tamanho de 64/128/256 bits já oferece um espaço muito grande para UUIDs. Obviamente, não é infinito, mas ...

Talvez seja uma boa ideia usar apenas um tamanho fixo int (por exemplo, 64 bits para começar) até que 64 bits não sejam suficientes (ou próximos a ele). Então, supondo que você tenha esse acesso a todas as instâncias anteriores dos UUIDs, basta atualizá-las para ints de 128 bits e considerar que esse é o seu tamanho fixo de número inteiro.

Se o sistema permitir tais pausas / interrupções de serviço e como essas operações de "reconstrução" ocorrerem com pouca frequência, talvez os benefícios (um sistema muito simples, rápido e fácil de implementar) superem as desvantagens (tendo que reconstruir todos os números inteiros previamente alocados) para um novo tamanho de bit inteiro).

Dmitri Shuralyov
fonte