Was ist die Wahrscheinlichkeit der Kollision mit einem 6-stelligen zufälligen alphanumerischen code?

Ich bin mit dem folgenden perl-code zu generieren zufällige alphanumerische Zeichenketten (Großbuchstaben und zahlen, nur) als eindeutige Identifikatoren für Datensätze in meiner MySQL-Datenbank. Die Datenbank wird wahrscheinlich bleiben unter 1.000.000 Zeilen, aber die absolute realistische maximum wäre etwa 3,000,000. Muss ich eine gefährliche chance, die 2 Datensätze mit der gleichen random-code, oder wird es wahrscheinlich passieren, eine verschwindend kleine Anzahl der Zeiten? Ich weiß sehr wenig über die Wahrscheinlichkeit (wenn das nicht bereits klar aus der Natur der Frage) und würde gerne jemanden Eingang.

perl -le 'print map { ("A".."Z", 0..9)[rand 36] } 1..6'
  • Warum kannst du nicht einfach verwenden, ein auto-increment Feld?
  • Wenn aus irgendeinem Grund die "auto increment" nicht funktioniert, ziehen Sie die Verwendung einer UUID statt. Diese sind entworfen, um die random-IDS mit einer minimalen chance auf Kollision. metacpan.org/module/Data::UUID
  • Wenn Sie einen eindeutigen index erstellen in der Datenbank haben, erhalten Sie eine Ausnahme von DBI, wenn eine Kollision Auftritt. Man könnte die Ausnahme abfangen, einen anderen code zu erzeugen, und versuchen Sie es erneut. Der Kurs, der nicht besonders effizient sein, wenn Sie viele der verfügbaren codes.
InformationsquelleAutor Nick | 2011-09-29
  1. 40

    Wegen der Geburtstag Paradox es ist wahrscheinlicher, als Sie vielleicht denken.

    Gibt es 2,176,782,336 möglichen codes, aber auch das einfügen von nur 50.000 Zeilen es ist schon eine Recht hohe Wahrscheinlichkeit einer Kollision. Für 1.000.000 Zeilen ist es fast unausweichlich, dass es viele Kollisionen (ich denke, etwa 250 im Schnitt).

    Ich lief ein paar tests und die Anzahl der codes, die ich erzeugen könnte, bevor die erste Kollision:

    • 73366
    • 59307
    • 79297
    • 36909

    Kollisionen häufiger, wie die Anzahl der codes erhöht.

    Hier war mein test-code (geschrieben in 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
    InformationsquelleAutor Mark Byers
  2. 12

    Gut, Sie haben 36**6 möglichen codes, die etwa 2 Milliarden Euro. Rufen Sie diese d. Mit Hilfe einer Formel gefunden hier, finden wir, dass die Wahrscheinlichkeit einer Kollision, für n codes, etwa

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

    Für alle n über 50.000 oder so, das ist ziemlich hoch.

    Sieht aus wie ein 10-Zeichen-code hat eine Kollision Wahrscheinlichkeit von nur etwa 1/800. Also mit 10 oder mehr.

    InformationsquelleAutor Tom Zych
  3. 8

    Wie bereits erwähnt, ist das Geburtstags-Paradoxon macht dieses Ereignis sehr wahrscheinlich. Insbesondere eine genaue Näherung bestimmt werden kann, wenn das problem geworfen, als eine Kollision-problem. Lassen Sie p(n; d) werden, die Wahrscheinlichkeit, dass mindestens zwei zahlen gleich sind, d werden die Anzahl der Kombinationen und der n die Anzahl von Wanderwegen. Dann können wir zeigen, dass p(n; d) ist ungefähr gleich:

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

    Können wir leicht dieses Grundstück in R:

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

    gibt

    Was ist die Wahrscheinlichkeit der Kollision mit einem 6-stelligen zufälligen alphanumerischen code?

    Wie Sie sehen können die Kollisions-Wahrscheinlichkeit steigt sehr schnell mit der Anzahl der versuche/Zeilen

    InformationsquelleAutor csgillespie
  4. 7

    Basierend auf den Gleichungen unter http://en.wikipedia.org/wiki/Birthday_paradox#Approximation_of_number_of_people, gibt es eine 50% chance der Begegnung mindestens eine Kollision nach dem einfügen nur als 55.000 Datensätze oder so, in einem Universum dieser Größe:

    http://wolfr.am/niaHIF

    Versuchen, fügen Sie zwei bis sechs mal so viele Datensätze führt fast zwangsläufig zu einer Kollision. Benötigen Sie zum zuordnen von codes nonrandomly, oder verwenden Sie einen größeren code.

    InformationsquelleAutor duskwuff
  5. 1

    Während ich nicht wissen, die Besonderheiten der genau wie du wollen diese pseudo-Zufalls-IDs, möchten Sie vielleicht zu prüfen, erzeugen Sie ein array von 3000000 zahlen (von 1 bis 3000000) und nach dem Zufallsprinzip mischen Sie es. Das würde garantieren, dass die zahlen eindeutig sind.
    Sehen Fisher-Yates-shuffle auf Wikipedia.

    • Angesichts der Anzahl der möglichen Permutationen, jemanden Sequenzen wäre eher ausgewählt werden als andere.
    InformationsquelleAutor Alexey Frunze
  6. 0

    Vorsicht: Hüten Sie sich vor der Berufung auf die built-in rand wo die Qualität der pseudo-Zufallszahl-generator zählt. Vor kurzem fand ich heraus, über Math::Random::MT::Auto:

    Den Mersenne-Twister ist eine schnelle Pseudo-Zufallsgenerator (PRNG), die in der Lage ist die großen Mengen (> 10^6004) - "hohe Qualität" Pseudo-zufälligen Daten, um Anwendungen, die Auspuffanlage verfügbar "wirklich" zufällige Datenquellen oder vom system bereitgestellten PRNGs wie rand.

    Bietet das Modul eine drop-in-Ersatz für rand was praktisch ist.

    Erzeugen können Sie die Reihenfolge der Tasten mit den folgenden code:

    #!/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;
}

    Vor einiger Zeit schrieb ich über die begrenzte Palette von built-in rand auf Windows. Sie können nicht auf Windows, aber möglicherweise gibt es noch weitere Einschränkungen oder fallen auf Ihrem system.

    InformationsquelleAutor Sinan Ünür
Schreibe einen Kommentar