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

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

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

Ответ 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

Ответ 2

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

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

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

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

Ответ 3

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

http://wolfr.am/niaHIF

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

Ответ 4

Как упоминалось ранее, парадокс дня рождения делает это событие вполне вероятным. В частности, точная аппроксимация может быть определена, когда задача задана как проблема столкновения. Пусть 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')

который дает

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

Ответ 5

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

Ответ 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, но в вашей системе могут быть другие ограничения или ошибки.