18

我正在使用以下 perl 代码生成随机字母数字字符串（仅限大写字母和数字），以用作我的 MySQL 数据库中记录的唯一标识符。数据库可能保持在 1,000,000 行以下，但绝对现实的最大值约为 3,000,000。我有 2 条记录具有相同随机代码的危险机会，还是可能发生的次数很少？我对概率知之甚少（如果从这个问题的性质来看这还不是很清楚的话）并且会喜欢某人的意见。

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

6 回答 6

48

由于生日悖论，它比你想象的更有可能。

有 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
于 2011-09-29T00:17:16.213 回答
14

好吧，你有 36**6 个可能的代码，大约是 20 亿。称之为d。使用此处找到的公式，我们发现对于n 个代码，发生冲突的概率大约为

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

对于任何超过 50,000 左右的 n，这是相当高的。

看起来 10 个字符的代码的碰撞概率只有 1/800 左右。所以去10个或更多。

于 2011-09-29T00:29:53.887 回答
8

根据http://en.wikipedia.org/wiki/Birthday_paradox#Approximation_of_number_of_people中给出的方程式，在这种大小的宇宙中仅插入 55,000 条左右的记录后，有 50% 的机会遇到至少一次碰撞：

http://wolfr.am/niaHIF

尝试插入 2 到 6 倍的记录几乎肯定会导致冲突。您需要非随机分配代码，或使用更大的代码。

于 2011-09-29T00:31:05.563 回答
8

如前所述，生日悖论使这一事件很有可能发生。特别是，当问题被视为碰撞问题时，可以确定准确的近似值。设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')

这使

在此处输入图像描述

如您所见，碰撞概率随着试验/行数的增加而迅速增加

于 2011-09-29T15:47:58.313 回答
1

虽然我不知道您希望如何使用这些伪随机 ID 的具体细节，但您可能需要考虑生成一个包含 3000000 个整数（从 1 到 3000000）的数组并随机打乱它。这将保证这些数字是唯一的。请参阅Wikipedia 上的 Fisher-Yates shuffle。

于 2011-09-29T00:28:09.217 回答
0

一个警告：当心依赖内置rand的伪随机数生成器的质量很重要。我最近发现了Math::Random::MT::Auto：

Mersenne Twister 是一种快速伪随机数生成器 (PRNG)，能够为可能耗尽可用“真正”随机数据源或系统提供的 PRNG 等应用程序提供大量 (> 10^6004) 的“高质量”伪随机数据作为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;
}

前段时间，我写了一篇关于Windows内置的有限范围的rand文章。您可能不在 Windows 上，但您的系统可能存在其他限制或陷阱。

于 2011-09-29T15:21:15.907 回答