Как я могу создать собственный GUID-алгоритм с меньшим «глобальным»?

Question

У меня есть собственное приложение с гораздо меньшим «глобальным», чем наш настоящий глобальный, и мне нужна более короткая версия GUID. Теперь предположим, что у меня есть конкретное количество идентификаторов, которые, по моим оценкам, никогда не превышают (например, 100 миллионов идентификаторов). Как определить количество случайных бит, которые должны иметь такое же свойство, как и GUID? (Глобально уникальный, не требующий центральной власти для его создания). Использование обычного GUID будет излишним.

Мое «излишество» относится к этому: мне нужно, чтобы идентификатор был так же легко набрал/сказал/записал как можно скорее и имел несколько астрономически низкий шанс столкновения как GUID в одно и то же время. Я слышал, что GUID можно назначить на каждое зерно песка на земле. Мое приложение - игра, каждый игрок получает один идентификатор, очевидно, мои игроки не так сильно, как количество песка на земле.

Было бы лучше, если бы игрок мог сказать «Мой идентификатор XXXX-XXXX». В этом случае я не был бы уверен, что 8 символов рандомизированных гексов недостаточно или слишком много для 100 миллионов игроков. (На самом деле, я кодирую его в A-Z 0-9 вместо hex). Моя игра не ограничена онлайн, поэтому я хотел бы, чтобы каждый игрок мог получить уникальный идентификатор, даже если он не был онлайн. (нет сервера для проверки коллизий ID)

GUID был разработан, чтобы быть уникальным во всем мире. Но я не знаю, почему это приводит к 128-битной последовательности. Может быть, они просто выбирают «очень большой», который имеет силу 2? Я не знаю, что они думают при разработке GUID, чтобы убедиться, что он не столкнется. (Они что-то используют в мировом населении? Если это так, я тоже могу использовать в 10 миллионов раз что-то.)

Answer 1

Хорошо, я обсуждал с другом и придумал решение. Вот как определить количество «персонажей» моего ID игры.

Символ будет состоять из 0-9 и A-Z вместо HEX, то есть 36 видов символов.Мы вытащили 0 O 1, поэтому он был бы печатаем для множества шрифтов без путаницы, что оставляет 32 вида персонажей.

Тогда, если каждый персонаж будет псевдослучайным, сколько игроков мы можем безопасно иметь?

Использовано квадратное приближение Birthday paradox. Формула на этой странице показывает, сколько людей должно иметь 50% вероятность столкновения двух человек. Для дня рождения проблема составляет 22,99 человека. (365 возможных вариантов)

Теперь подставим 32^No.of символов в уравнение вместо 365. Это количество игроков, которые вызывают 50% шанс 2 игроков, имеющих один и тот же ID:

Наконец, мы договорились выбрать 9-значный идентификатор, чтобы можно было зарегистрировать игру до 6,9 миллиона игроков до того, как всего 2 из 6,9 миллиона игроков будут иметь одинаковый идентификатор (50% шанс).

В игре нет даже онлайн-игр! Это только сталкивается, если 2 игрока все еще активно играют в одно и то же время и решают отправить счет на табло за ту же неделю из-за сброса недельного счёта. Таким образом, фактическое число, которое может удерживать игра, будет несколько выше. (В игре, вероятно, не будет много игроков .. это всего лишь небольшая счастливая мечта каждого запуска игры. Ну, по крайней мере, вычисление было забавным.)

Это, вероятно, будет выглядеть следующим образом: 5XT-339 -A67

Answer 2

128-битный guid обычно будет хорошо работать, поскольку большинство компиляторов достаточно умны, чтобы уменьшить количество операций на нем пара 64-битных операций (и на некоторых процессорах, одна 128-битная расширенная операция). Java и C#/VB.NET, скорее всего, будут иметь намного больше накладных расходов, чем C++, но если вы используете Java или C#/VB.NET, вы уже приняли довольно много накладных расходов, а GUID не будет добавлять много к нему.

Однако, если вам действительно нужны меньшие значения, вы можете вручную уменьшить GUIDs, с помощью XOR-кий верхнего 64 бита с нижними 64 битами (тем самым сохраняя некоторые уникальности оригинала), чтобы создать компактные 64 -битный в основном уникальный номер.

Вы можете уменьшить до 32-бит или 48 бит аналогичным образом, всегда кратным размеру исходного GUID. Это имеет то преимущество, что вы начинаете с номера, который должен быть уникальным в очень большом наборе. Однако имейте в виду, что для 100 миллионов элементов требуется довольно большое количество бит для сохранения неперекрывающейся гарантии, поэтому вы можете просто настроить себя на очень трудную для поиска проблему позже, если не будете осторожны.

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

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