Как эффективно создать большой список различных UUID? - PullRequest
Новая
       58

Как эффективно создать большой список различных UUID?

2 голосов
/ 04 мая 2019

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

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

Я использую NodeJS с UUID v4.

Спасибо!

Ответы [ 2 ]

1 голос
/ 04 мая 2019

Вы можете использовать доморощенную функцию UUID, которая гарантированно будет уникальным псевдослучайным целым числом в диапазоне [0 ... 2 128 ).Ниже приведен пример, основанный на линейном конгенциальном генераторе .Константы взяты из здесь или здесь .Вам нужно только держать предыдущий номер / UUID под рукой, чтобы сгенерировать следующий, нет необходимости проверять, потому что он будет повторяться только после полного периода 2 128 .

Код зависит от BigInt,протестировано с узлом v12 

const a = 199967246047888932297834045878657099405n; // should satisfy a % 8n = 5n
const c = 1n;                                       // should be odd
const m = (1n << 128n);
const mask = m - 1n;

function LCG128(state) {
    return (BigInt(state) * a + c) & mask; // same as % m
}

q = 7654321n; // seed

q = LCG128(q);
q.toString(16); // first UUID

q = LCG128(q);
q.toString(16); // second UUID

q = LCG128(q);
q.toString(16); // third UUID

ОБНОВЛЕНИЕ

Просто чтобы быть более философским в данном вопросе:

  1. Вы можете считать UUID4 черным ящиком иповерьте - это то, что @ChrisWhite предложил
  2. Вы можете считать UUID4 черным ящиком и не доверять ему - это то, что вы предложили проверить в списке или ответить @ KevinPastor
  3. Сделайте свой собственныйпрозрачная коробка, которая производит числа в нужном диапазоне и быть уникальной - это мое предложение

Красота подхода LCG заключается в том, что, учитывая хороший множитель и перенос, он уникально и обратимый диапазон карт [0 ...2 128 ) в себя (это может быть сделано для 64-разрядных чисел, с различными a, c или 32-разрядными числами и т. Д. И т. Д.).Вы даже можете использовать счетчик в качестве входных данных, начиная с 0 до 2 128 -1, и он будет генерировать неповторяемые числа в том же диапазоне, заполняя все [0 ... 2 128 ),Таким образом, вы знаете, что если вы связываете его с предыдущим uuid или используете счетчик, то вероятность столкновения равна 0.

1 голос
/ 04 мая 2019

Вы можете создать пустой объект и каждый раз, когда вы генерируете UUID, вы добавляете атрибут к тому объекту, где ключом является сгенерированный UUID. Когда вы сгенерируете другой UUID, вам просто нужно проверить, является ли атрибут объекта undefined или нет, чтобы увидеть, используется ли он уже. 

const uuids = [];
let uuidUsed = {};
const size = 10;
for (let i = 0; i < size; i++) {
    let uuid = uuidv4();
    while (uuidUsed[uuid] !== undefined) {
        uuid = uuidv4();
    }
    uuidUsed[uuid] = true;
}
...