Генерация случайного GUID

libuuid, не?

не. интересует именно отсутствие коллизий by design

А чем элементарный алгоритм «сгенерить случайный id, проверить бинарным поиском на совпадение. Если id существует, повторить, иначе return.» не устраивает? Число коллизий будет мало, пока список UID-ов не начнёт переполняться. Если число uid-ов порядка нескольких миллиардов, число перебросов будет несущественным.

Когда количество занятых id станет больше 20% из возможных id - этот алгоритм будет супер неэффективным.

очень часто возникает задача минимизации размера id, например артикул товара при продажах

Ну вот сначала наберите 36^8*0.2 = 564221981491 товаров, а там посмотрим.

Альтернативный алгоритм: храним предыдущий uid, каждому новому товару присваиваем uid+1. Вышеобозначенных проблем алгоритм не имеет. Думаю, осилите перевести число в систему счисления с нужными символами.

это ясно. но всетаки

Получить свободный GUID без коллизий с (желательно) равной вероятностью среди всех свободных GUID

интересует теоретическая подоплека этого вопроса =)

Для генерации гуидов тащемта есть стандарт. Курите Википедию.

http://en.wikipedia.org/wiki/Globally_unique_identifier

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

Ну, с равной вероятностью не знаю, что ещё можно предложить. Разве что шифровать id. А минимизировать длину попробовать можно, например, сжимая по Хаффману. Насчёт стройной теории не знаю.

Boost.UUID? ЕМНИП там есть разные алгоритмы генерации, в том числе алгоритм, который помнить ранее сгенерённые UUID'ы.

у нас недавно был сайтик, на котором заказчик хотел минимизировать идшник и чтобы он был случайный. мы сделали именно обычным бинарным поиском. заказчик просил 4 символа, но нам пришлось сделать 6. 36 ^ 4 = 1679616, а товаров ожидалось порядка 200 тыщ в год

ничтожно мала для алгоритма v4 с количеством позиций 32. а меня интересует фиксированное число позиций (например 4-6)

Не, ну можно же не истинно случайные ID-сделать, а подогнать распределение вероятностей, например, перемешиванием битов. Это должно быть быстро и похоже на рандом, хотя на самом деле вполне просчитываемо. ИМХО, самый реальный вариант.

кинь плс ссылку где почитать

Тогда это уже не гуид.

а как правильно называть? я не в курсе

Ну, например, можно глянуть, как осуществляется перемешивание в алгоритмах симметричного шифрования. Там одной из задач тоже является получение равновероятной последовательности.

Вот. После этого:
1) простой счётчик выдаёт id
2) мы это дело прогоняем через наш шифратор, дающий на выходе последовательность с хорошими вероятностными характеристиками и без коллизий.
3) мы преобразуем последовательность бит в нужный нам формат записи

Сделать guid зависимым от времени

Можешь использовать Bloom Filter. Он обеспечит компактное хранение данных и быстрое время проверки коллизий.

http://en.wikipedia.org/wiki/Bloom_filter

Возьми большое простое n и случайное число m. m будет зерном. По формуле m^i mod n сможешь находить следующее число. i, начиная с 1 просто каждый раз увеличивай на 1.

Желательно, чтобы кто-то еще сказал правильно ли это, т.к. в математике я не силен.

В целом, моя задача перебрать все классы вычетов большого простого числа.

Желательно, чтобы кто-то еще сказал правильно ли это, т.к. в математике я не силен.

Кроме того, что длина периода будет плавать как попало.

Например, пусть n=3571 (простое). Мы, вероятно, ожидаем, что период будет тоже 3571. По факту наблюдаем:

m     период
-------------
12     714
14     596
17     120
20     120
22     43

43 !!! Т.е. мы использовали порядка 1% доступного битового пространства, а затем начались повторения.

И правда. А если не в степень возводить, а умножать? m*i mod n

Получим самый обычный рандом. Причём, опять же, m и n должны быть правильными, чтобы период был достаточно большим. В общем, схема может работать, если тщательно выбрать входные параметры (удостовериться, что нам хватит периода).

А можешь сказать (или ссылку кинуть), где будет объяснено, почему формулой m*i mod n можно перебрать все классы вычетов n и почему m должно быть простым?

У Кнута по генераторам псевдослучайных чисел всё должно быть.

m и n должны быть взаимно простыми

Занятые GUID храняться
Получить свободный GUID без коллизий

00000
00001
00002
Дальше сам.

Ещё можно воспользоваться алгоритмом RSA - связь между i и результатом будет намного менее очевидна.

Но трудно будет предсказать коллизию. А в том, что предложил я, есть заранее известный период коллизии.

Но трудно будет предсказать коллизию.

Что? Какие коллизии в случае с RSA? Пока счётчик не начнёт повторяться, никаких коллизий не будет. Я, если кто помнит, почти сразу предложил этот метод — поверх счётчика прикрутить шифрование.

Ты же сам писал, что если возводить в степень, то

Кроме того, что длина периода будет плавать как попало.

RSA - это чуть больше, чем просто возведение в степень. Давай немного отвлечёмся от непосредственно алгоритма. Одним из основных условий добротности шифра является однозначность расшифрования. Если бы шифротексты на выходе повторялись, мы бы не смогли расшифровать данные однозначно. Следовательно, по определению, коллизий на выходе шифра быть не должно. Шифр для данного алгоритма может быть любой, но дающий на выходе равновероятную последовательность.

Занятые GUID храняться
Получить свободный GUID без коллизий с (желательно) равной вероятностью среди всех свободных GUID, обращаясь к хранилищу минимальное количество раз.
Когда количество занятых id станет больше 20% из возможных id

Генерируешь рандомный GUID и запрашиваешь у хранилища ближайший к нему неиспользованный. Чтобы эффективно обслуживать такой запрос, хранилище должно оперировать не отдельными GUID-ами, а непрерывными диапазонами GUID-ов: расширять и объединять диапазоны по мере добавления в него новых GUID-ов, сужать и разделять диапазоны по мере уничтожения старых GUID-ов.

чему тебя в школе учат? да. дерево. бинарное. идёшь от корня к случайному узлу влево/вправо. Если узла нет - создаёшь новый uid. номер uid равен пути от корня. (0 - влево, 1 - вправо). Если у тебя есть 1048576 uid, то тебе надо в среднем 20 прыжков для нового uid. Лучше сделать невозможно.

Если тебе нужны uid'ы переменной длинны, старший бит считай всегда равным 1, дабы отличить 0000 от 000000000. Если uid фиксированный, то 1 добавлять не нужно, однако возникает проблема переполнения uid (как тут уже сказали, эффективность упадёт, если почти все uid'ы заюзаны).

Генерируешь рандомный GUID и запрашиваешь у хранилища ближайший к нему неиспользованный.

ты что курил? представляешь, сколько времени займёт такой запрос? Это же квадратичная сложность! Если ты конечно не сделаешь структуру в виде дерева, о чём я в прошлом посте писал(или её эквивалент).

Что? Какие коллизии в случае с RSA? Пока счётчик не начнёт повторяться, никаких коллизий не будет.

ты ошибаешься. коллизии могут быть, никто не гарантирует их отсутствие. Вот в md5 уже нашли, в других алгоритмах ещё нет, но не факт, что там их нет. Да и смысла нет в таком сложном алгоритме. Вполне подойдёт и (A*x+B)modC.

43 !!! Т.е. мы использовали порядка 1% доступного битового пространства, а затем начались повторения.

у Кнута есть исчерпывающий анализ, с рецептом выбора хороших констант. Я не помню, как там точно, посмотреть? По его рецепту получается более 95% пространства охваченным ЕМНИП.

Чтобы говорить о их существовании, нужен хотя бы один пример их появления в RSA. А то это как Бог — в него можно верить, но никто его никогда не видел.

у Кнута есть исчерпывающий анализ, с рецептом выбора хороших констант. Я не помню, как там точно, посмотреть? По его рецепту получается более 95% пространства охваченным ЕМНИП.

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

Чтобы говорить о их существовании, нужен хотя бы один пример их появления в RSA. А то это как Бог — в него можно верить, но никто его никогда не видел.

во первых, коллизии в md5 тоже никто не видел. Пока их не нашли. Во вторых - ты вот в CRC32 коллизии видел? Уверен - не видел. А я их не только видел, но и сам создавал, как мне было надо. Т.ч. Б-г тут не при делах. Нельзя надеяться на то, чего ты просто не понимаешь.

Математики нам НЕ гарантируют, что таких коллизий не будет, они предполагают, что сломать RSA будет сложно, а вот про коллизии - вообще ничего не предполагают.

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

дык вот Кнут как раз и нашёл формулу, которая даёт «хорошие» константы. У меня 32х битный генератор 100 000 000 чисел дал, и не разу не повторился. Мне этого хватило.

Точно.

Пойду читать Кнута :)

А порядок важен? МОжно лексикографически следующий генерировать.

Уверен - не видел.

Лоровские аналитики такие аналитики.

диапазоны могут дробиться до 36 ^ 8 / 3 что тоже очень много. тяжело оперировать ими =)

че ты такой злюк. нас этому на 1 курсе в универе учили =) я почти так и думал делать. создал тему чтобы посмотреть альтернативные алгоритмы

порядок не важен. что ты имеешь в виду?

че ты такой злюк. нас этому на 1 курсе в универе учили =) я почти так и думал делать. создал тему чтобы посмотреть альтернативные алгоритмы

а какой тут может быть альтернативный алгоритм? если

Занятые GUID храняться

без коллизий

равной вероятностью среди всех свободных GUID

другого варианта и быть не может.

из-за последнего твоего условия вариант N+1 не подходит, ибо даёт сл. uid не случайным, а вполне предсказуемым, даже если ты его свёрнёшь и зашифруешь криптостойким хешем. Например, если ты используешь sha256, злоумышленник может догадаться об этом, и проверить свою догадку. Более сложные схемы тоже уязвимы (в принципе). Единственный неуязвимый в принципе алгоритм - случайный выбор.

Это же квадратичная сложность!

Чем докажешь?

Если ты конечно не сделаешь структуру в виде дерева

То есть сложность всё-таки не квадратичная. Ну и чего ты раскудахтался тогда?

Занятые GUID храняться

храняться

Ну как можно так писать?

диапазоны могут дробиться до 36 ^ 8 / 3 что тоже очень много. тяжело оперировать ими =)

Ты в любом случае собираешься хранить все занятые GUID-ы. Диапазонов придётся хранить не больше, чем занято GUID-ов. То есть в плане тяжести особой разницы нет.

порядок не важен. что ты имеешь в виду?

это N+1. только система счисления не десятичная, а Mричная. Где M — число «цифр» в системе счисления. так файлы например split нумерует. (aa, ab, ac…)