Хорошая схема для представления целых чисел от 0 до бесконечности, при условии, что у вас бесконечная линейная двоичная память?

10

Я хотел бы, чтобы схема представляла целые числа, начиная с 0, без каких-либо ограничений (предполагая доступ к бесконечному линейному хранилищу).

Вот схема, которая может представлять числа от 0 до 255:

Используйте первый байт памяти (адрес 0) для хранения целого числа.

Теперь предположим, что я хочу представить числа, превышающие 255. Конечно, я мог бы использовать более 1 байта для представления целого числа, но, пока это фиксированное число, в конечном итоге будет целое число, настолько большое, что оно не может быть представлено оригинальная схема.

Вот еще одна схема, которая должна быть в состоянии выполнить задачу, но, вероятно, она далеко не эффективна.

Просто используйте какой-то уникальный байт «конца числа» и используйте все предыдущие байты для представления числа. Очевидно, что этот байт «конца числа» не может использоваться нигде в числовом представлении, но этого можно достичь, используя систему нумерации base-255 (вместо base-256).

Однако это медленно и, вероятно, неэффективно. Я хочу иметь лучший, который работает лучше с низкими значениями и хорошо масштабируется.

По сути, это система UUID. Я хочу посмотреть, возможно ли создать быстродействующую систему UUID, которая теоретически может масштабироваться для использования в течение многих лет, тысяч лет, миллионов лет без необходимости ее перепроектирования.

storage numbers uuid Дмитрий Шуралев
источник
1
Вы хотите что-то, что может масштабироваться бесконечно (как при вашем открытии) или за миллионы лет (как при вашем закрытии)? Эти два требования (очевидно) совершенно разные. Двойное дополнение на 64-битной машине будет масштабироваться миллионы лет.
user16764
1
@ user16764, вы имеете в виду одну 64-битную целочисленную переменную? Это, конечно, не сработает: если 6 миллионов человек потребляют 1 миллион UUID в секунду, это едва ли продлится больше месяца.
Дмитрий Шуралев
1
И сколько времени это займет на 128-битной машине?
user16764
2
Идеи в RFC 2550 , который обеспечивает лексикографически упорядоченное представление ASCII для сколь угодно больших натуральных чисел, могут быть адаптированы к этому. В конечном итоге он разбивается на унарный сегмент, который кодирует длину сегмента base-26, который кодирует длину сегмента base-10 - последние две базы в большей степени связаны с представлением ASCII, чем с чем-либо фундаментальным для схемы.
Random832
1
Предполагая, что вы генерируете 128-битные числа последовательно: если мы ограничим вычислительную мощность всех компьютеров, предоставив каждому человеку петафлоп-компьютер, то пройдет 9 миллионов лет, прежде чем эти числа закончатся. С другой стороны, если каждый человек случайным образом сгенерирует 600 миллионов 128-битных чисел, существует 50% вероятность, что он сгенерирует 1 дубликат. Это достаточно хорошо для вас? ( en.wikipedia.org/wiki/Universally_unique_identifier ) Если нет, то использование 256 бит умножает обе эти цифры на 2 ^ 128 = 3,4 * 10 ^ 38, что больше квадрата возраста вселенной в секундах.
Алекс тен Бринк

Ответы:

13

Подход, который я использовал: подсчитать количество старших 1 бит, скажем n. Размер числа составляет 2 ^ n байтов (включая первые 1 бит). Возьмите биты после первого 0-битного числа как целое число и добавьте максимальное значение (плюс один), которое может быть представлено числом с использованием этой кодировки в 2 ^ (n-1) байтах.

Таким образом, 

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

Эта схема позволяет любому неотрицательному значению быть представленным точно одним способом.

(Эквивалентно, используется количество ведущих 0 битов.)

retracile
источник
1
Мне было трудно понять, какой ответ пометить как принятый, потому что я думаю, что многие из них очень информативны и хороши. Но я думаю, что этот вопрос лучше всего подходит для вопроса, который я задал (возможно, не тот, который я имел в виду, что сложнее выразить).
Дмитрий Шуралев
2
Я написал более глубокую статью с примером реализации и соображениями дизайна.
откат
10

Существует целая теория, основанная на том, что вы пытаетесь сделать. Взгляните на вики-страницу о универсальных кодах - здесь приведен довольно исчерпывающий список методов целочисленного кодирования (некоторые из которых фактически используются на практике).

В сжатии данных универсальный код для целых чисел является префиксным кодом, который отображает натуральные числа в двоичные кодовые слова.

Или вы можете просто использовать первые 8 байтов для хранения длины числа в некоторых единицах (наиболее вероятных байтах), а затем поместить байты данных. Это было бы очень легко реализовать, но довольно неэффективно для небольших номеров. И вы сможете закодировать целое число достаточно долго, чтобы заполнить все диски данных, доступные человечеству :)

Матей Забский
источник
Спасибо за это, это очень интересно. Я хотел отметить это как принятый ответ, но он занял 2 место. Это очень хороший ответ с теоретической точки зрения, ИМО.
Дмитрий Шуралев
4

Как насчет того, чтобы число первых 1 плюс первые 0 было размером (sizeSize) размера числа (numSize) в битах. NumSize - это двоичное число, которое дает размер представления числа в байтах, включая биты размера. Остальные биты - это число (num) в двоичном виде. Для положительной целочисленной схемы вот несколько примеров чисел:

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
источник
4

Как насчет этого: один байт для длины, затем n байтов для числа (сначала младший байт). Повторите длину + число, если предыдущая длина была 255.

Это допускает произвольно большие числа, но все же легко обрабатывается и не тратит слишком много памяти.

user281377
источник
fNek: верхнего предела нет. Например, если вам нужно 513 байтов для числа, последовательность байтов будет [255, b0, ..., b255,255, b256, ..., b511,2, b512, b513]
user281377
Сожалею. Надо научиться читать более внимательно.
fNek
3

Почему бы просто не использовать 7 бит из каждого байта и использовать 8-й бит, чтобы указать, есть ли еще один байт? Таким образом, 1-127 будет в одном байте, 128 будет представлен 0x80 0x01 и т. Д.

Пол Томблин
источник
1
Эта схема кодирует только 128 значений в каждых 8 битах, что на самом деле занимает меньше места, чем вторая схема кодирования, предложенная спрашивающим, где 255 значений кодируются в каждых 8 битах. Обе схемы страдают от того, что вам нужно прочитать целое число, чтобы узнать, сколько памяти вам нужно для его хранения.
Марк Бут
3
Так что вам нужно дважды отсканировать число, чтобы сделать его копию, и что? Если я могу ждать одного бесконечно большого числа, я могу ждать его дважды.
Рассел Борогове
Хотя я не указывал это очень тщательно, я ищу решение, которое работает максимально эффективно (вместо решения, которое просто соответствует требованиям; я уже описал один потенциальный неэффективный ответ в своем вопросе).
Дмитрий Шуралев
3

Системы UUID основаны на конечной (но большой) вычислительной мощности в конечной (но большой) вселенной. Количество UUID велико даже по сравнению с абсурдно большими вещами, такими как количество частиц во вселенной. Однако число UUID с любым количеством фиксированных битов мало по сравнению с бесконечностью.

Проблема с использованием 0xFFFF для представления вашего флага конца номера состоит в том, что он делает вашу кодировку чисел менее эффективной при больших числах. Однако кажется, что ваша UUID-схема делает эту проблему еще хуже. Вместо пропущенного одного из 256 байтов теперь все пространство UUID потрачено впустую. Эффективность вычислений / распознавания (а не пространства) во многом зависит от вашего теоретического компьютера (который, я полагаю, у вас есть, если вы говорите о бесконечности). Для ТМ с магнитной лентой и контроллером конечного состояния любую схему UUID невозможно эффективно масштабировать (в принципе, лемма прокачки мешает вам эффективно выйти за конечный маркер фиксированной длины). Если вы не предполагаете наличие контроллера конечного состояния, это может не применяться, но вам нужно подумать о том, куда идут биты в процессе декодирования / распознавания.

Если вы просто хотите повысить эффективность, чем 1 из 256 байтов, вы можете использовать любую битовую длину 1 с, которую вы собирались использовать для своей схемы UUID. Это 1 из 2-х бит длины в неэффективности.

Обратите внимание, что существуют и другие схемы кодирования. Байтовое кодирование с разделителями оказывается наиболее простым в реализации.

ccoakley
источник
2

Я бы предложил иметь массив байтов (или целых или длинных) и поле длины, которое говорит о том, как долго это число.

Это примерно тот подход, который используется в Java BigInteger . Возможное из этого адресное пространство огромно - достаточно легко, чтобы дать разные UUID каждому отдельному атому во вселенной :-)

Если у вас нет веской причины поступить иначе, я бы предложил просто использовать BigInteger напрямую (или его эквивалент на других языках). Нет особой необходимости изобретать колесо большого числа ....

mikera
источник
Вы не можете закодировать длину массива, когда количество полей может быть бесконечным.
Славек
Я согласен с тем, что по возможности предпочтительнее использовать существующее решение (особенно, прошедшее профессиональную проверку) для данной проблемы. Спасибо.
Дмитрий Шуралев
@Slawek: верно, но для случая использования, который описывает OP (т. Е. UUID), BigInteger фактически бесконечен. В любом случае, вы не можете кодировать бесконечную информацию на любом компьютере с памятью ограниченного размера, поэтому BigInteger так же хорош, как и все остальное, чего вы, вероятно, достигнете.
Микера
2

Прежде всего, спасибо всем, кто дал отличные ответы на мой относительно неопределенный и абстрактный вопрос.

Я хотел бы внести потенциальный ответ, о котором я подумал, подумав о других ответах. Это не прямой ответ на заданный вопрос, но он актуален.

Как отмечали некоторые люди, использование целого числа размером 64/128/256 бит уже дает вам очень большое пространство для UUID. Очевидно, это не бесконечно, но ...

Возможно, будет хорошей идеей просто использовать фиксированный размер int (скажем, 64-битный для начала), пока 64-битный не будет достаточно (или близко к нему). Затем, предполагая, что у вас есть такой доступ ко всем предыдущим экземплярам UUID, просто обновите их до 128-битных целочисленных значений и примите это как целое число фиксированного размера.

Если система допускает такие паузы / прерывания обслуживания и поскольку такие операции «перестроения» должны выполняться довольно редко, возможно, преимущества (очень простая, быстрая и простая в реализации система) перевесят недостатки (необходимость перестраивать все ранее выделенные целые числа). к новому целочисленному размеру бита).

Дмитрий Шуралев
источник