Я был вдохновлен этим unique id code для генерации случайного 64-битного идентификатора.Является ли 64-разрядный случайный идентификатор достаточно хорошим для примерно 10 миллионов записей?
Мой вопрос: будет ли это достаточно хорошо для примерно 10 миллионов записей?
def self.generateId
(0..15).collect{(rand*16).to_i.to_s(16)}.join
end
Это классическая проблема с днем рождения.
С m=10^7 и n=10^20 (С 2^64 ~ 10^20), и вероятность столкновения определяется по формуле:
p = 1 - exp(-m^2/(2*n))
Дает вероятность столкновений 5e-07
Я бы сказал, отбор без замены является ваш лучший вариант.
Я хотел бы сделать это 128 немного долго, таким образом вам не придется беспокоиться наверняка о 10М записей
2^64 составляет около EDIT:
10^31
10^21, который больше 10^7 (10 миллионов) в 10 ~ 14 раз. Таким образом, почти полностью безопасно использовать только 64 бита.
Это не так, извините. '2^64 = (2^10)^6 * 2^4 = 1024^6 * 2^4 ~ 10^18 * 10 ~ 10^19' –
Вы правы, моя вина. Я хотел сказать: 2^10 составляет около 10^3, поэтому 2^64 составляет около 10^21, поэтому 10^31 была опечаткой, она должна была читать 10^21. Во всяком случае, 10^21 больше 10^7 в 10 раз 14, любой мой аргумент остается в силе. Я отредактировал свой ответ соответственно. –
Спасибо. Что вы подразумеваете под «выборкой без замены»? – Mark
Представьте себе набор пронумерованных предметов в сумке и нарисуйте их в случайном порядке. Поскольку элемент рисуется и не заменяется, он никогда не будет повторяться. Большинство библиотек 'math' имеют поддержку выборки без замены. – Nishanth
Я вижу. В моем случае это не будет вариант, потому что идентификаторы генерируются многими разными клиентами, которые не знают друг о друге. – Mark