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.
Du musst angemeldet sein, um einen Kommentar abzugeben.
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:
Kollisionen häufiger, wie die Anzahl der codes erhöht.
Hier war mein test-code (geschrieben in Python):
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.
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 dern
die Anzahl von Wanderwegen. Dann können wir zeigen, dassp(n; d)
ist ungefähr gleich:Können wir leicht dieses Grundstück in R:
gibt
Wie Sie sehen können die Kollisions-Wahrscheinlichkeit steigt sehr schnell mit der Anzahl der versuche/Zeilen
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.
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.
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: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:
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.