Преобразовать последовательность чисел в случайные идентификаторы?

Question

Я работаю над приложением, в котором мне нужно генерировать уникальные непоследовательные идентификаторы. Одно из ограничений, которые у меня есть, состоит в том, что они должны состоять из 3 цифр, за которыми следуют 2 буквы (только около 600 тыс. Идентификаторов). Учитывая мой сравнительно небольшой пул идентификаторов, я подумывал просто сгенерировать все возможные идентификаторы, перетасовать их и поместить в базу данных. Поскольку внутри у меня будет простой, последовательный ID для использования, будет легко вытащить их по одному и быть уверенным, что у меня нет повторов.

Это не очень удачное решение. У кого-нибудь есть более интересный метод генерации уникальных идентификаторов из ограниченного пула, чем этот метод «лотереи»?

Answer 1

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

Идентификационный номер = ддд с 1 с [0]

Вариант 1 (по сути, как хеширование, аналогично хэшированию Зака):
1 Создайте случайное число от 0 до количества возможностей (676k).
2- конвертировать число в комбинацию

    ddd = random / (26^2)
    c[0] = random % (26)
    c[1] = (random / 26) % 26

3- Запросить БД на наличие идентификатора и приращения, пока не будет найден свободный.

Вариант 2 (регистр сдвига с линейной обратной связью, см. wikipedia ):
1- Семя со случайным числом в диапазоне (0,676k). (См. Ниже, почему вы не можете посеять с '0')
2. Создайте последующие случайные числа, применив следующее к текущему идентификационному номеру.

    num = (num >> 1) ^ (-(num & 1u) & 0x90000u);

3- Пропустить идентификаторы, превышающие диапазон (т. Е. 0xA50A0 +)
4- Конвертируйте число в формат идентификатора (как указано выше)
* Вам нужно будет сохранить последнее сгенерированное число, использованное для идентификатора, но вам не нужно будет запрашивать БД, чтобы узнать, используется ли оно. Это решение будет перечислять все возможные идентификаторы, кроме [000 AA] из-за того, как работает LFSR.

[править] Так как ваш диапазон на самом деле больше, чем вам нужно, вы можете получить обратно [000 AA], вычтя 1, прежде чем преобразовать в идентификатор, и ваш допустимый диапазон будет (0,0xA50A0]

Answer 2

Вы можете сгенерировать случайный идентификатор, соответствующий этому стандарту, сделать выбор БД, чтобы увидеть, существует ли он уже, а затем вставить его в БД, чтобы отметить, что он «использовался». В течение первых 25% срока службы этой схемы (или около 150 тыс. Записей) генерирование новых случайных идентификаторов должно быть относительно быстрым. Однако после этого потребуется больше и больше времени, и вы могли бы также предварительно заполнить таблицу, чтобы найти свободные идентификаторы.

Answer 3

Используйте конечную группу. В основном, возьмите 32- или 64-разрядное целое число и найдите большое число, взаимно простое с максимальным значением для вашего целого числа; назовите это число M. Тогда для всех целых чисел n, n * M приведет к уникальному номеру, который имеет много цифр.

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

Answer 4

В зависимости от того, что вы определяете как последовательный, вы можете просто выбрать определенную начальную точку на буквах, например, 'aa', и просто перебрать три цифры, так что это будет: 001aa 002aa 003aa

Как только вы доберетесь до zz, увеличьте числовую часть.

Answer 5

Вы можете использовать модульную арифметику для генерации идентификаторов. Выберите число, взаимно простое с 676 000 и для семени. id - это стандартный инкрементный идентификатор таблицы. Тогда вам нужен следующий псевдокод:

uidNo = (id * seed) % 676000
digits = uidNo / 676
char1 = uidNo % 26
char2 = (uidNo / 26) % 26
uidCode = str(digits) + chr(char1+65) + chr(char2+65)

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