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)

n が 50,000 程度を超えると、かなり高い値になります。

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 レコード程度を挿入しただけで、少なくとも 1 回衝突が発生する確率は 50% です。

http://wolfr.am/niaHIF

2 ～ 6 倍のレコードを挿入しようとすると、ほぼ確実に競合が発生します。コードを非ランダムに割り当てるか、より大きなコードを使用する必要があります。

于 2011-09-29T00:31:05.563 に答える
8

前述のように、誕生日のパラドックスにより、このイベントが発生する可能性が非常に高くなります。特に、問題が衝突問題としてキャストされると、正確な近似を決定できます。p(n; d)少なくとも 2 つの数が同じである確率を、組み合わせ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) であり、大量 (> 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;
}

少し前に、 Windowsのビルトインの範囲が限定されrandていることについて書きました。Windows を使用していない可能性がありますが、システムには他の制限や落とし穴がある可能性があります。

于 2011-09-29T15:21:15.907 に答える