Какова вероятность столкновения с 6-значным случайным буквенно-цифровым кодом?

Question

Я использую следующий код perl для генерации случайных буквенно-цифровых строк (только заглавные буквы и цифры) для использования в качестве уникальных идентификаторов для записей в моей базе данных MySQL. База данных, вероятно, останется менее 1 000 000 строк, но абсолютный реалистичный максимум составит около 3 000 000. Есть ли у меня опасная вероятность того, что 2 записи будут иметь один и тот же случайный код, или это может произойти незначительно мало раз? Я очень мало знаю о вероятности (если это еще не до конца понятно из природы этого вопроса) и хотел бы получить чей-то вклад.

perl -le 'print map { ("A".."Z", 0..9)[rand 36] } 1..6'

Answer 1

Из-за парадокса дня рождения это более вероятно, чем вы могли бы подумать.

Есть 2 176 782 336 возможных кодов, но даже при вставке всего 50 000 строк уже существует довольно высокая вероятность столкновения,Для 1 000 000 строк почти неизбежно будет много коллизий (в среднем около 250).

Я провел несколько тестов, и это число кодов, которое я мог сгенерировать до того, как произошла первая коллизия:

• 73366
• 59307
• 79297
• 36909

Столкновения будут происходить чаще с увеличением количества кодов.

Вот мой тестовый код (написанный на Python):

>>> import random
>>> codes = set()
>>> while 1:
        code=''.join(random.choice('1234567890qwertyuiopasdfghjklzxcvbnm')for x in range(6))
        if code in codes: break
        codes.add(code)

>>> len(codes)
36909

Answer 2

Ну, у вас есть 36 ** 6 возможных кодов, что составляет около 2 миллиардов.Назовите это d .Используя формулу, найденную здесь , мы находим, что вероятность столкновения для n кодов составляет примерно

1 - ((d-1)/d)**(n*(n-1)/2)

Для любогоn более 50 000 или около того, это довольно много.

Похоже, что 10-символьный код имеет вероятность столкновения всего лишь около 1/800.Так что иди с 10 или более.

Answer 3

Как упоминалось ранее, парадокс дня рождения делает это событие вполне вероятным.В частности, точное приближение может быть определено, когда задача рассматривается как проблема столкновения.Пусть p(n; d) будет вероятностью того, что по крайней мере два числа одинаковы, d будет количеством комбинаций и n количеством следов.Затем мы можем показать, что p(n; d) приблизительно равно:

1 - ((d-1)/d)^(n*(n-1)/2)

. Мы можем легко построить это в R:

> d = 2176782336
> n = 1:100000
> plot(n,1 - ((d-1)/d)^(n*(n-1)/2), type='l')

, что дает

Как видите, вероятность столкновения очень быстро возрастает с увеличением количества попыток / строк

Answer 4

На основании уравнений, приведенных в http://en.wikipedia.org/wiki/Birthday_paradox#Approximation_of_number_of_people,, существует 50% -ная вероятность столкновения хотя бы с одним столкновением после добавления только 55 000 записей или около того во вселенную такого размера:

http://wolfr.am/niaHIF

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

Answer 5

Хотя я не знаю специфики того, как именно вы хотите использовать эти псевдослучайные идентификаторы, вы можете рассмотреть возможность создания массива из 3000000 целых чисел (от 1 до 3000000) и случайного его тасования.Это будет гарантировать, что номера являются уникальными.См. Фишера-Йейтса в Википедии .

Answer 6

Предупреждение: Остерегайтесь полагаться на встроенный rand, где имеет значение качество генератора псевдослучайных чисел. Я недавно узнал о Math :: Random :: MT :: Auto :

Mersenne Twister - это быстрый генератор псевдослучайных чисел (PRNG), способный предоставлять большие объемы (> 10 ^ 6004) «высококачественных» псевдослучайных данных приложениям, которые могут исчерпать доступные «действительно» случайные источники данных или системные предоставленные PRNG, такие как rand.

Модуль обеспечивает замену rand, что очень удобно.

Вы можете сгенерировать последовательность ключей с помощью следующего кода:

#!/usr/bin/env perl

use warnings; use strict;
use Math::Random::MT::Auto qw( rand );

my $SEQUENCE_LENGTH = 1_000_000;
my %dict;
my $picks;

for my $i (1 .. $SEQUENCE_LENGTH) {
    my $pick = pick_one();
    $picks += 1;

    redo if exists $dict{ $pick };

    $dict{ $pick } = undef;
}

printf "Generated %d keys with %d picks\n", scalar keys %dict, $picks;

sub pick_one {
    join '', map { ("A".."Z", 0..9)[rand 36] } 1..6;
}

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