Пишу библиотеку, в которой создаются объекты с уникальными идентификаторами. Сейчас это обычный инкремент,
поэтому объекты получают идентификаторы 0, 1, 2, ..., n, n+1, ...
Подскажите какую-нибудь простую функцию, которая по-случайнее "разбрасывает" идентификаторы по некоторому диапазону
(например, [0..UINT_MAX)), но так, чтобы генерируемые идентификаторы оставались уникальными. Например, чтобы
получалась последовательность 54231, 3, 9547, 4431, 1, 8877, ...
Сложность алгоритма должна быть O(1) и без дополнительных огромных массивов и т.п.
Получается, это должна быть какая-то негладкая биективная функция... Пока навскидку придумал переставлять
байты в обычном счетчике. Но тогда будут получаться серии подряд идущих байтов, что не очень хорошо.
Было бы идеально получить обратную функцию, ну да это уже не так важно.
Это нужно вот для чего: после генерации с этими идентификаторами производятся некие манипуляции,
поэтому хочется проверить поведение библиотеки на разных значениях этих идентификаторов (и её независимость от
прямого следования). Кроме того, пользователи могут подумать, что идентификаторы последовательны и использовать
это в своих корыстных целях -- например, они могут полагать, что первый объект всегда имеет идентификатор 0, и явно забивать
этот 0 в свои программы (а не использовать getNextId() из моей библиотеки). Да и внутри библиотеки это не
помешает.
Здравствуйте, malphunction, Вы писали:
M>Подскажите какую-нибудь простую функцию, которая по-случайнее "разбрасывает" идентификаторы по некоторому диапазону M>(например, [0..UINT_MAX)), но так, чтобы генерируемые идентификаторы оставались уникальными. Например, чтобы M>получалась последовательность 54231, 3, 9547, 4431, 1, 8877, ...
M>Сложность алгоритма должна быть O(1) и без дополнительных огромных массивов и т.п.
Задачка известная, вот пара ссылок на обсуждение: здесь
берешь симметричный блочный шифр с размером блока, равным размеру идентификатора. Для 64-битного блока таких шифров полно. Для 32 бит придется специально затачивать. Берешь случайный ключ и последовательно (в режиме ECB) шифруешь им блоки содержащие 0, 1, 2, 3, и т.д.
Здравствуйте, malphunction, Вы писали:
M>Пишу библиотеку, в которой создаются объекты с уникальными идентификаторами. Сейчас это обычный инкремент, M>поэтому объекты получают идентификаторы 0, 1, 2, ..., n, n+1, ...
M>Подскажите какую-нибудь простую функцию, которая по-случайнее "разбрасывает" идентификаторы по некоторому диапазону M>(например, [0..UINT_MAX)), но так, чтобы генерируемые идентификаторы оставались уникальными. Например, чтобы M>получалась последовательность 54231, 3, 9547, 4431, 1, 8877, ...
M>Сложность алгоритма должна быть O(1) и без дополнительных огромных массивов и т.п.
M>Получается, это должна быть какая-то негладкая биективная функция...
Вот этот вывод уже поспешен. Например, если сильно расширить объём идентификатора, то можно обойтись просто случайной его генерацией. 128 бит для этого хватит с головой. Можно воспользоваться системным генератором UUID'ов, если они не MAC-based.
Ещё можно использовать симметричный шифр (см. ответ dilmah'а), но я бы делал чуть не так: шифруется не номер по порядку, а адрес структуры объекта в памяти библиотеки. Дополнительная польза — можно расшифровать и сравнить с адресом.
N>но я бы делал чуть не так: шифруется не номер по порядку, а адрес структуры объекта в памяти библиотеки. Дополнительная польза — можно расшифровать и сравнить с адресом.
тут вопрос для чего эти идентификаторы используются. Если у объектов есть время жизни, то старый и новый объекты могут иметь одинаковый адрес.
Собственно, в последний раз когда я использлвал такие идентификаторы в своей практике они использовались как раз с целью отличать новый объект от привидений из прошлого которые размещались по этому же адресу.
N>>но я бы делал чуть не так: шифруется не номер по порядку, а адрес структуры объекта в памяти библиотеки. Дополнительная польза — можно расшифровать и сравнить с адресом.
D>тут вопрос для чего эти идентификаторы используются. Если у объектов есть время жизни, то старый и новый объекты могут иметь одинаковый адрес. D>Собственно, в последний раз когда я использлвал такие идентификаторы в своей практике они использовались как раз с целью отличать новый объект от привидений из прошлого которые размещались по этому же адресу.
Да, в таком случае действительно нужна своя нумерация.
N>>но я бы делал чуть не так: шифруется не номер по порядку, а адрес структуры объекта в памяти библиотеки. Дополнительная польза — можно расшифровать и сравнить с адресом.
D>тут вопрос для чего эти идентификаторы используются. Если у объектов есть время жизни, то старый и новый объекты могут иметь одинаковый адрес. D>Собственно, в последний раз когда я использлвал такие идентификаторы в своей практике они использовались как раз с целью отличать новый объект от привидений из прошлого которые размещались по этому же адресу.
Интересно, что это за проект был, в котором потребовалось такое решение? Есть информация в инете?
D>>тут вопрос для чего эти идентификаторы используются. Если у объектов есть время жизни, то старый и новый объекты могут иметь одинаковый адрес. D>>Собственно, в последний раз когда я использлвал такие идентификаторы в своей практике они использовались как раз с целью отличать новый объект от привидений из прошлого которые размещались по этому же адресу.
M>Интересно, что это за проект был, в котором потребовалось такое решение? Есть информация в инете?
допустим есть некая асинхронная система, может быть многопоточная, или использующая libevent. На каждый объект могут быть ссылки в других частях системы, и в будущем может прийти коллбэк или сообщение для него.
Часто может быть нужно удалить объект. Но при этом удалять все связанные с ним задачи может быть и дорого (в многопоточных системах на это потребуется синхронизация) или это может требовать кучи говнокода, или в моем случае это было просто невозможно, потому что интерфейс libevent/evdns не предоставляет возможность отменить DNS коллбэк.
Не уничтожать объект пока все задачи не отработают также неуместно.
Поэтому просто объектам присваиваются уникальные идентификаторы, для живых идентификаторов хранится соответствие идентификатора адресу объекта; когда объект уничтожается, он удаляется, удаляется все связанное с ним что можно легко удалить, на удаление остальных следов забивается, и его идентификатор удаляется из множества живых.
Когда приходит коллбэк или сообщение для неживого идентификатора оно просто игнорируется.
