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

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

в общем случае вычисление метрики («близости») чисел имеет квадратичную сложность.

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

это частный специальный случай. Мало того, я не гарантирую близости, я просто беру случайный эл-т по определённым правилам. Близость - побочный эффект этого алгоритма(он возникает потому, что сл. случайное число размера M получается всегда из числа размером M-1, но оно не обязательно является случайным выбором из M альтернатив, потому-что отличается последним битом, а не любым).

Дело в том, что к числу из M битов существует ровно M ближайших чисел, с метрикой равной 1. Но я беру не из них, а одно из чисел размера M+1. Таких чисел 0,1 или 2.

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

Если 20% заняты, значит не хватает разрядности. Нет смысла пытаться такое решить костылями. Вы определитесь, вам либо рандомизация, либо разрядов поменьше.

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

Эти проблемы возникают от попытки смешать id и user-friendly url. Вы либо используйте автоинкремент, либо заведите 2 разных поля. Одно рандомно-уникальное, второе красиво-уникальное.

в общем случае вычисление метрики («близости») чисел имеет квадратичную сложность.
Дело в том, что к числу из M битов существует ровно M ближайших чисел, с метрикой равной 1.

«Близостью» я назвал модуль разности чисел. Твой «общий случай» к предложенному мной алгоритму отношения не имеет.

Как же правильно решать задачу такого типа? <...> Есть ли готовые решения? (для линупса естественно)

cat /proc/sys/kernel/random/uuid

поверх счётчика прикрутить шифрование

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

id - равномерно возрастающее, скажем 32 бита

GUID=block_crypt(id) - (вполне)равномерно распределённое в тех-же 32-х битах.

остаётся выбрать симметричный блочный шифр по вкусу и где-то инкрементировать id

А может хранилище само будет выдавать свободне UUID?

По моему вам нужно взять любой из предложенных псевдослучайных алгоритмов с seed а потом запустить численный эксперимент на ночь/день/whatever - хватит ли чисел без коллизий на определенное в тз примерное количество id. Получится такой запас. :) Соответственно в программе каждый день/неделю проверять сколько в БД уже занято IDшников. Если уже близко к исчерпанию - ругатся и/или потом останавливать работу под лозунгом «вызывайте специалистов».

Соответственно можно адаптировать этот алгоритм добавив к нему описанное вами дерево. То есть когда запас idшников исчерпывается, мы добавляем префикс из нашей же (или другой) псевдослучайной последовательности и продолжаем использовать псевдослучанйые числа но уже с префиксом.

У слова GUID есть четкое определение.

К стати вопрос по схожей теме - надо псевдослучайный генератор с периодом >90% значений. Незначительное колличество коллизий не проблема. Кто знает такой?

«Близостью» я назвал модуль разности чисел. Твой «общий случай» к предложенному мной алгоритму отношения не имеет.

теперь расскажи, как ты свой «алгоритм» реализуешь.

К стати вопрос по схожей теме - надо псевдослучайный генератор с периодом >90% значений. Незначительное колличество коллизий не проблема. Кто знает такой?

см. выше. Это к Кнуту.

есть ещё вариант: сдвигаешь число влево на 1 бит, и вдвигаешь туда XOR старшего бита и какого-нить ещё бита. Для многих M период равен 2**M-1 (не входит 00000…, ибо 0+0=0).

теперь расскажи, как ты свой «алгоритм» реализуешь.

Ты про устройство хранилища спрашиваешь, или что-то еще не ясно?

Ты про устройство хранилища спрашиваешь, или что-то еще не ясно?

ну если у тебя со мной такие разночтения с метрикой - то со всем остальным мне вообще ничего непонятно.

со всем остальным мне вообще ничего непонятно

Ок, давай тогда на время предположим, что хранилище уже есть готовое и разберемся «со всем остальным». Алгоритм следующий: «Генерируешь рандомный GUID и запрашиваешь у хранилища ближайший к нему неиспользованный.» Со смыслом слово «ближайший» уже разобрались. Что еще не ясно: задавай конкретные вопросы.

Алгоритм следующий: «Генерируешь рандомный GUID и запрашиваешь у хранилища ближайший к нему неиспользованный.» Со смыслом слово «ближайший» уже разобрались. Что еще не ясно: задавай конкретные вопросы.

ну это у тебя целых 2 алгоритма в одном:

1. генерируешь случайный

2. если случилась коллизия, берёшь X+1, X+2 и т.д.

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

2. если случилась коллизия, берёшь X+1, X+2 и т.д.

Точнее, результат выглядит так, будто бы алгоритм рассматривал поочередно X+1, X-1, X+2, X-2 и так далее до нахождения первого незанятого GUID-а. Как этот результат получается на самом деле — это уже деталь реализации хранилища, предлагаю вернуться к устройству хранилища когда других вопросов не останется.

1. генерируешь случайный
2. если случилась коллизия, берёшь X+1, X+2 и т.д.
зачем это надо, и какой в этом профит?

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

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

<Время на создание> = <время на генерацию случайного GUID (константа)> + <время за которое хранилище выполнит запрос по поиску ближайшего свободного GUID>. Верно?

2. Взятие ближайшего свободного GUID — это способ разрешить коллизию за одно обращение к хранилищу.

вообще-то только само хранилище в состоянии решить, какое там значение «ближайшее». У меня в бинарном дереве это узел нижнего уровня. Если его нет - то это и есть искомый uid.

<Время на создание> = <время на генерацию случайного GUID (константа)> + <время за которое хранилище выполнит запрос по поиску ближайшего свободного GUID>. Верно?

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

но «запрос свободного» - это долго

«Запрос свободного» в наихудшем случае делается за O(log N), где N - количество занятых GUID.

log2(36 ^ 5 ) ~= 26.

Не так уж и долго.

«Запрос свободного» в наихудшем случае делается за O(log N), где N - количество занятых GUID.

«запрос свободного» завершается неудачей с вероятностью 95% при заполненном на 95% хранилище. Откуда и тормоза.

А за O(log(N)) делается запрос случайного(так же, как и запрос след. случайного, или большего на 1 случайного).

log2

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

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

Освежать не обязательно, я помню формальное определение O-большого наизусть. Обрати внимание, что внутри O-большого я и не указал основание логарифма. Основание я указал там же, где подставил конкретное значение N.

«запрос свободного» завершается неудачей с вероятностью 95% при заполненном на 95% хранилище.

Запрос по поиску ближайшего свободного GUID завершается удачей с вероятностью 100% при наличии хотя бы одного свободного GUID.

Что до реализации хранилища, то вот иллюстрация идеи (написал за 10 минут, не тестил, наверняка есть баги):

#include <map>

class Storage
{
	typedef int value_t;
	typedef std::map<value_t, value_t> ranges_t; // big_edge -> little_edge

	ranges_t ranges;

	bool Contains(ranges_t::const_iterator it, value_t item) const
	{
		return it != ranges.end() && it->first >= item && item >= it->second;
	}
public:
	bool Insert(value_t item)
	{
		ranges_t::iterator it = ranges.lower_bound(item);
		if(Contains(it, item))
			return false;

		ranges_t::iterator next(it);
		ranges_t::iterator prev(it == ranges.begin() ? ranges.end() : --it);

		// consider merging with next range
		value_t big_edge = item;
		if(next != ranges.end() && next->second == item + 1)
		{
			big_edge = next->first;
			ranges.erase(next);
		}

		// consider merging with prev range
		value_t little_edge = item;
		if(prev != ranges.end() && prev->first + 1 == item)
		{
			little_edge = prev->second;
			ranges.erase(prev);
		}

		ranges.insert(std::make_pair(big_edge, little_edge));
		return true;
	}
	bool Erase(value_t item)
	{
		ranges_t::iterator it = ranges.lower_bound(item);
		if(!Contains(it, item))
			return false;

		value_t big_edge = it->first;
		value_t little_edge = it->second;
		ranges.erase(it);

		// consider splitting out big part
		if(big_edge != item)
		{
			ranges.insert(std::make_pair(big_edge, item + 1));
		}

		// consider splitting out little part
		if(little_edge != item)
		{
			ranges.insert(std::make_pair(item - 1, little_edge));
		}

		return true;
	}
	std::pair<value_t, value_t> FindNearestUnused(value_t item) const
	{
		ranges_t::const_iterator it = ranges.lower_bound(item);

		if(!Contains(it, item))
			return std::make_pair(item, item);
		else
			return std::make_pair(it->first + 1, it->second - 1);
	}
};