Ich möchte eine Zufallszahl generieren und sie an eine Tabelle in einer Datenbank für eine bestimmte Benutzer-ID ausgeben. Der Haken ist, die gleiche Nummer kann nicht zweimal verwendet werden. Es gibt eine Million Möglichkeiten, dies zu tun, aber ich hoffe, dass jemand, der sehr scharf auf Algorithmen ist, einen cleveren Weg hat, das Problem in einer eleganten Lösung zu lösen, indem die folgenden Kriterien erfüllt werden:
1) Die geringste Anzahl von Abfragen an die Datenbank wird gemacht. 2) Die geringste Menge an Crawling durch eine Datenstruktur im Speicher wird gemacht.
Im Wesentlichen ist die Idee, das Folgende zu tun
1) Erstellen Sie eine Zufallszahl von 0 bis 9999999
2) Überprüfen Sie die Datenbank, um festzustellen, ob die Nummer vorhanden ist
ODER
2) Abfrage der Datenbank nach allen Zahlen
3) Sehen Sie, ob das zurückgegebene Ergebnis mit dem übereinstimmt, was von db
kam
4) Wenn es übereinstimmt, wiederholen Sie Schritt 1, wenn nicht, ist das Problem gelöst.
Danke.
Nein, Ihr Algorithmus ist nicht skalierbar. Was ich vorher gemacht habe, ist, Zahlen seriell (+1 jedes Mal) auszugeben und sie dann durch eine XOR-Operation zu übergeben, um die Bits zu durcheinander zu bringen und mir so scheinbar zufällige Zahlen zu geben. Natürlich sind sie nicht wirklich zufällig, aber sie sehen für die Augen der Benutzer so aus.
[Bearbeiten] Zusätzliche Informationen
Die Logik dieses Algorithmus geht so, dass Sie eine bekannte Sequenz verwenden erzeuge eindeutige Zahlen und manipuliere sie dann deterministisch, sie sehen also nicht mehr seriell aus. Die allgemeine Lösung ist zu verwenden irgendeine Form der Verschlüsselung, die in meinem Fall ein XOR-Flipflop war, weil es ist so schnell wie es nur geht, und es erfüllt die Garantie, dass Zahlen wird niemals kollidieren.
Sie können jedoch andere Formen der Verschlüsselung verwenden, wenn Sie noch mehr bevorzugen zufällig aussehende Zahlen, über die Geschwindigkeit (sagen Sie, dass Sie nicht viele generieren müssen IDs zu einem Zeitpunkt). Jetzt der wichtige Punkt bei der Auswahl eines Verschlüsselungsalgorithmus ist "die Garantie, dass Zahlen niemals kollidieren". Und eine Möglichkeit zu beweisen, ob ein Verschlüsselungsalgorithmus erfüllt werden kann Diese Garantie prüft, ob sowohl die ursprüngliche Anzahl als auch das Ergebnis von die Verschlüsselung hat die gleiche Anzahl von Bits, und das ist der Algorithmus reversibel (Bijektion).
[Danke an Adam Liss & amp; CesarB für die Lösung der Lösung]
Wollen Sie eine übertriebene Lösung?
Ich gehe davon aus, dass Zufälligkeit nicht als Verschlüsselungsqualität gedacht ist, sondern gerade genug, um zu verhindern, dass die Nutzungsdauer eines Benutzers nach user_id geschätzt wird.
Generieren Sie während der Entwicklung eine Liste aller 10 Millionen Zahlen in Zeichenfolgenform.
Führen Sie optional eine einfache Transformation aus, z. B. das Hinzufügen einer konstanten Zeichenfolge zur Mitte. (Dies ist nur für den Fall, dass das Ergebnis zu vorhersehbar ist.)
Übergeben Sie sie an ein Werkzeug, das Perfect Hash-Funktionen generiert, z. B. gperf .
Der resultierende Code kann verwendet werden, um die ID des Benutzers zur Laufzeit schnell in einen eindeutigen Hash-Wert zu codieren, der garantiert nicht mit anderen Hash-Werten kollidiert.
Warum verwenden Sie nicht einfach eine GUID? Die meisten Sprachen sollten eine eingebaute Möglichkeit haben, dies zu tun. Es ist garantiert einzigartig (mit sehr vernünftigen Grenzen).
Ich möchte eine Zufallszahl generieren und sie an eine Tabelle in einer Datenbank für eine bestimmte Benutzer-ID ausgeben. Der Haken ist, die gleiche Nummer kann nicht zweimal verwendet werden. Es gibt eine Million Möglichkeiten, dies zu tun, aber ich hoffe, dass jemand, der sehr scharf auf Algorithmen ist, einen cleveren Weg hat, das Problem in einer eleganten Lösung zu lösen, indem die folgenden Kriterien erfüllt werden:
1) Die geringste Anzahl von Abfragen an die Datenbank wird gemacht. 2) Die geringste Menge an Crawling durch eine Datenstruktur im Speicher wird gemacht.
Im Wesentlichen ist die Idee, das Folgende zu tun
1) Erstellen Sie eine Zufallszahl von 0 bis 9999999
2) Überprüfen Sie die Datenbank, um festzustellen, ob die Nummer vorhanden ist
ODER
2) Abfrage der Datenbank nach allen Zahlen
3) Sehen Sie, ob das zurückgegebene Ergebnis mit dem übereinstimmt, was von db
kam
4) Wenn es übereinstimmt, wiederholen Sie Schritt 1, wenn nicht, ist das Problem gelöst.
Danke.
Wollen Sie eine übertriebene Lösung?
Ich gehe davon aus, dass Zufälligkeit nicht als Verschlüsselungsqualität gedacht ist, sondern gerade genug, um zu verhindern, dass die Nutzungsdauer eines Benutzers nach user_id geschätzt wird.
Generieren Sie während der Entwicklung eine Liste aller 10 Millionen Zahlen in Zeichenfolgenform.
Führen Sie optional eine einfache Transformation aus, z. B. das Hinzufügen einer konstanten Zeichenfolge zur Mitte. (Dies ist nur für den Fall, dass das Ergebnis zu vorhersehbar ist.)
Übergeben Sie sie an ein Werkzeug, das Perfect Hash-Funktionen generiert, z. B. gperf .
Der resultierende Code kann verwendet werden, um die ID des Benutzers zur Laufzeit schnell in einen eindeutigen Hash-Wert zu codieren, der garantiert nicht mit anderen Hash-Werten kollidiert.
Nein, Ihr Algorithmus ist nicht skalierbar. Was ich vorher gemacht habe, ist, Zahlen seriell (+1 jedes Mal) auszugeben und sie dann durch eine XOR-Operation zu übergeben, um die Bits zu durcheinander zu bringen und mir so scheinbar zufällige Zahlen zu geben. Natürlich sind sie nicht wirklich zufällig, aber sie sehen für die Augen der Benutzer so aus.
[Bearbeiten] Zusätzliche Informationen
Die Logik dieses Algorithmus geht so, dass Sie eine bekannte Sequenz verwenden erzeuge eindeutige Zahlen und manipuliere sie dann deterministisch, sie sehen also nicht mehr seriell aus. Die allgemeine Lösung ist zu verwenden irgendeine Form der Verschlüsselung, die in meinem Fall ein XOR-Flipflop war, weil es ist so schnell wie es nur geht, und es erfüllt die Garantie, dass Zahlen wird niemals kollidieren.
Sie können jedoch andere Formen der Verschlüsselung verwenden, wenn Sie noch mehr bevorzugen zufällig aussehende Zahlen, über die Geschwindigkeit (sagen Sie, dass Sie nicht viele generieren müssen IDs zu einem Zeitpunkt). Jetzt der wichtige Punkt bei der Auswahl eines Verschlüsselungsalgorithmus ist "die Garantie, dass Zahlen niemals kollidieren". Und eine Möglichkeit zu beweisen, ob ein Verschlüsselungsalgorithmus erfüllt werden kann Diese Garantie prüft, ob sowohl die ursprüngliche Anzahl als auch das Ergebnis von die Verschlüsselung hat die gleiche Anzahl von Bits, und das ist der Algorithmus reversibel (Bijektion).
[Danke an Adam Liss & amp; CesarB für die Lösung der Lösung]
Probieren Sie die Anweisung in mysql aus SELECT CAST (RAND () * 1000000 AS INT)
Ich denke, Sie werden feststellen, dass Sie das wirklich nicht tun wollen. Wenn die Zahlen in der Datenbank zunehmen, könnten Sie zu viel Zeit in der Schleife "Sicherstellen, dass diese Nummer nicht vergeben wurde" verbringen.
Ich persönlich hatte Glück mit Hashes als Alternative, aber um eine bessere Lösung zu finden, müsste ich wirklich wissen, warum Sie das so machen wollen.
Meine Erfahrung bestand einfach darin, den RNG in PHP zu verwenden. Ich habe festgestellt, dass eine bestimmte Größe der Nummer (Ich benutze ein int, so dass ich ein Maximum von 4G). Ich habe einige Tests durchgeführt und festgestellt, dass ich im Durchschnitt in 500.000 Iterationen 120 einzelne Duplikate erhielt. Ich habe nie ein Triplikat bekommen, nachdem ich die Schleife einige Male ausgeführt hatte. Meine "Lösung" war dann einfach einzufügen und zu prüfen, ob es fehlschlägt, dann eine neue ID zu generieren und erneut zu gehen.
Mein Rat ist, das Gleiche zu tun und zu sehen, wie hoch die Kollisionsrate ist und ob es für Ihren Fall akzeptabel ist.
Dies ist nicht optimal, also wenn jemand Vorschläge hat, schaue ich auch :)
EDIT: Ich war auf eine 5-stellige ID beschränkt ([a-zA-z0-9] {5,5}), je länger die ID (mehr Kombination, die wenigen Kollisionen). Ein MD5 der E-Mail würde fast nie in Konflikt geraten.
Angenommen:
Sie könnten etwas Einfaches tun, indem Sie die Zufallszahl als 64-Bit-Ganzzahl haben, wobei die oberen 32 Bits den Zeitstempel (bei Zeileneinfügung) und die unteren 32 Bits die Benutzer-ID enthalten. Dies wäre sogar für mehrere Zeilen mit demselben Benutzer eindeutig, vorausgesetzt, Sie verwenden eine geeignete Auflösung für Ihren Zeitstempel, je nachdem, wie oft Sie für denselben Benutzer neue Zeilen hinzufügen. Kombinieren Sie sie mit einer eindeutigen Einschränkung für die zufällige Spalte, und fangen Sie einen solchen Fehler in Ihrer Logik auf und versuchen Sie es dann einfach erneut.
Es ist einfach, einen Pseudozufallszahlengenerator mit einer langen Nichtwiederholung zu entwerfen; z.B. dieses , das für die gleiche Sache verwendet wird, für die Sie es wollen .
BTW, warum nicht einfach die Benutzer-IDs nacheinander ausgeben?
Das Problem ist, dass wenn Sie Zufallszahlen generieren, es sehr gut möglich ist, Duplikate infinately zu erzeugen.
jedoch:
%Vor%Während dies tun wird, was Sie wollen, ist es auch eine schlechte Idee, da diese nicht lange skalieren wird. Eventuell wird Ihr Array zu groß und es wird eine extrem lange Zeit brauchen, um ein zufälliges Ergebnis zu generieren in Ihrer Datenbank.
Ich mag Oddthinks Idee, aber anstatt die stärkste Hash-Funktion der Welt zu wählen, könntest du einfach:
MD5's sind schnell, und wenn Sie überprüfen, ob eine Zeichenkette zu einem Array gehört, vermeiden Sie eine SELECT.
Wenn Sie wirklich "zufällige" Zahlen von 0 bis 9 999 999 erhalten wollen, dann sollten Sie die "Randomisierung" einmal durchführen und dann das Ergebnis auf Ihrer Festplatte speichern.
Es ist nicht schwer, das gewünschte Ergebnis zu erhalten, aber ich denke eher an "mach eine lange Liste mit Zahlen" als an "bekomme eine Zufallszahl".
%Vor%Sie brauchen auch einen Zeiger auf die aktuelle Position in $ numbers (speichern Sie es in einer Datenbank); Beginnen Sie mit 0 und erhöhen Sie es jedes Mal, wenn Sie eine neue Nummer benötigen. (Oder Sie könnten array_shift () oder array_pop () verwenden, wenn Sie keine Zeiger verwenden möchten.)
Ein geeigneter PRNG (Pseudo-Random Number Generator) -Algorithmus hat eine Zykluszeit, während der er niemals im selben Zustand sein wird. Wenn Sie den gesamten Status des PRNG in der von ihm abgerufenen Nummer angeben, erhalten Sie eine Zahl, die für den Zeitraum des Generators eindeutig ist.
Eine einfache PRNG, die dies tut, wird als linearer kongruenter PRNG bezeichnet, der eine Formel iteriert:
%Vor%Unter Verwendung des richtigen Paares von Faktoren können Sie eine Periode von 2 ^ 30 (ungefähr 1 Milliarde) von einem einfachen PRNG mit einem 32-Bit-Akkumulator erhalten. Beachten Sie, dass Sie eine 64 Bit lange temporäre Variable benötigen, um den mittleren AX-Teil der Berechnung zu speichern. Die meisten, wenn nicht alle C-Compiler unterstützen diesen Datentyp. Sie sollten dies auch mit einem numerischen Datentyp in den meisten SQL-Dialekten tun können.
Mit den richtigen Werten von A und M können wir einen Zufallszahlengenerator mit guten statistischen und geometrischen Eigenschaften erhalten. Es gibt ein berühmtes Papier darüber geschrieben von Fishman und Moore.
Für M = 2 ^ 31 - 1 können wir die Werte von A unten verwenden, um eine PRNG mit einer schönen langen Periode (2 ^ 30 IIRC) zu erhalten.
Gute Werte von A:
%Vor%Beachten Sie, dass dieser Generatortyp per Definition nicht kryptografisch sicher ist. Wenn Sie die letzte generierte Nummer kennen, können Sie vorhersagen, was als nächstes zu tun ist. Leider glaube ich, dass Sie keine kryptografische Sicherheit und gleichzeitig garantierte Unwiederholbarkeit erhalten können. Damit ein PRNG kryptographisch sicher ist (z. B. Blum Blum Shub ), kann er nicht genügend Status in einer generierten Nummer verfügbar machen, um den nächsten zu erlauben Nummer in der Sequenz, die vorhergesagt werden soll. Daher ist der interne Zustand breiter als die erzeugte Zahl und (um eine gute Sicherheit zu haben) ist die Periode länger als die Anzahl der möglichen Werte, die erzeugt werden können. Dies bedeutet, dass die exponierte Nummer innerhalb des Zeitraums nicht eindeutig ist.
Aus ähnlichen Gründen gilt das auch für langperiodische Generatoren wie den Mersenne Twister
Ich habe Ihren Standpunkt wahrscheinlich nicht verstanden, aber was ist mit auto_increments?
PHP hat dafür bereits eine Funktion, uniqid . Es erzeugt eine Standard-UUID, die großartig ist, wenn Sie auf die Daten von anderswo zugreifen müssen. Erfinde das Rad nicht neu.
Ich habe vorher schon geschrieben Artikel dazu . Es verfolgt den gleichen Ansatz wie Robert Goulds Antwort, zeigt aber zusätzlich, wie man eine Blockchiffre auf eine geeignete Länge verkürzen kann, indem man x oder faltet, und dann die Permutationen über einen Bereich erzeugt, der keine Potenz von 2 ist Eindeutigkeitseigenschaft.
es gibt ein paar Wege, um über diese eine Möglichkeit zu gehen, ein Array mit den Zahlen 0000000 bis 9999999 zu konstruieren und dann eine zufällige Auswahl dieser Zahlen in diesem Array auszuwählen und tausche die gewählten Zahlenwerte mit dem höchsten Wert Max Reduziere dann max um 1 und wähle ein anderes zufälliges Mitglied dieses Arrays bis zum neuen Maximum aus
bei jeder Reduzierung von Max um eins
zum Beispiel (in basic): (rechts sind Kommentare, die im eigentlichen Programm entfernt werden sollen) Rndfunc ist ein Aufruf an die von Ihnen verwendete Zufallsgeneratorfunktion
%Vor%Machen Sie das für jede Nummer, die Sie auswählen möchten, aber Sie müssen die Möglichkeit haben, sehr große Arrays zu verwenden
Die andere Methode wäre wie folgt: Erzeugen Sie eine Zahl und speichern Sie sie in einem Array, das dynamisch wachsen kann Wählen Sie dann eine neue Zahl aus und vergleichen Sie sie mit dem Wert, der auf halbem Weg zwischen dem ersten und dem letzten Element im Array liegt. In diesem Fall wäre es die erste ausgewählte Nummer Wenn es eine andere Zufallszahl auswählt, sortiere das Array nach der Größe und wenn es keine Übereinstimmung gibt, dann ist es abhängig von der Wetterlage größer oder kleiner als die Zahl, mit der du es verglichen hast Jedes Mal, wenn es nicht übereinstimmt und größer oder kleiner ist als das, mit dem Sie es vergleichen.
Jedes Mal, wenn Sie es halbiert haben, bis Sie eine Lückengröße von eins erreichen, dann checken Sie einmal und halten an, da es keine Übereinstimmung gibt, und dann wird die Nummer zur Liste hinzugefügt und die Liste wird in aufsteigender Reihenfolge neu sortiert, und so weiter bis du fertig bist, zufällige Zahlen zu wählen ... hoffe das hilft ..
Wenn Sie sicherstellen möchten, dass sich die Zufallszahlen nicht wiederholen, benötigen Sie einen sich nicht wiederholenden Zufallsgenerator (wie beschrieben). hier ).
Der Grundgedanke ist, dass die folgende Formel %code% nicht-wiederholende Zufallszahlen für jede Eingabe erzeugt %code% und %code% erzeugt alle anderen Zufallszahlen, die sich nicht wiederholen, aber nur wenn %code% . Alles was du brauchst ist eine Primzahl, die so nah wie möglich an %code% ist. Auf diese Weise kann der Aufwand auf ein einzelnes Lesefeld reduziert werden, aber mit dem Nachteil, dass entweder zu große IDs generiert werden oder zu wenige IDs generiert werden.
Dieser Algorithmus lässt sich nicht sehr gut vertauschen, daher würde ich empfehlen, ihn entweder mit XOR oder Addition oder einem anderen Ansatz zu kombinieren, um den genauen Wert zu ändern, ohne die 1-zu-1-Beziehung zwischen den Seeds und ihrem generierten Wert zu zerstören.
Ich denke, Sie werden feststellen, dass Sie das wirklich nicht tun wollen. Wenn die Zahlen in der Datenbank zunehmen, könnten Sie zu viel Zeit in der Schleife "Sicherstellen, dass diese Nummer nicht vergeben wurde" verbringen.
Ich persönlich hatte Glück mit Hashes als Alternative, aber um eine bessere Lösung zu finden, müsste ich wirklich wissen, warum Sie das so machen wollen.
Meine Erfahrung bestand einfach darin, den RNG in PHP zu verwenden. Ich habe festgestellt, dass eine bestimmte Größe der Nummer (Ich benutze ein int, so dass ich ein Maximum von 4G). Ich habe einige Tests durchgeführt und festgestellt, dass ich im Durchschnitt in 500.000 Iterationen 120 einzelne Duplikate erhielt. Ich habe nie ein Triplikat bekommen, nachdem ich die Schleife einige Male ausgeführt hatte. Meine "Lösung" war dann einfach einzufügen und zu prüfen, ob es fehlschlägt, dann eine neue ID zu generieren und erneut zu gehen.
Mein Rat ist, das Gleiche zu tun und zu sehen, wie hoch die Kollisionsrate ist und ob es für Ihren Fall akzeptabel ist.
Dies ist nicht optimal, also wenn jemand Vorschläge hat, schaue ich auch :)
EDIT: Ich war auf eine 5-stellige ID beschränkt ([a-zA-z0-9] {5,5}), je länger die ID (mehr Kombination, die wenigen Kollisionen). Ein MD5 der E-Mail würde fast nie in Konflikt geraten.
Das Problem ist, dass wenn Sie Zufallszahlen generieren, es sehr gut möglich ist, Duplikate infinately zu erzeugen.
jedoch:
%Vor%Während dies tun wird, was Sie wollen, ist es auch eine schlechte Idee, da diese nicht lange skalieren wird. Eventuell wird Ihr Array zu groß und es wird eine extrem lange Zeit brauchen, um ein zufälliges Ergebnis zu generieren in Ihrer Datenbank.
Warum verwenden Sie nicht einfach eine GUID? Die meisten Sprachen sollten eine eingebaute Möglichkeit haben, dies zu tun. Es ist garantiert einzigartig (mit sehr vernünftigen Grenzen).
Ich möchte eine Zufallszahl generieren und sie an eine Tabelle in einer Datenbank für eine bestimmte Benutzer-ID ausgeben. Der Haken ist, die gleiche Nummer kann nicht zweimal verwendet werden. Es gibt eine Million Möglichkeiten, dies zu tun, aber ich hoffe, dass jemand, der sehr scharf auf Algorithmen ist, einen cleveren Weg hat, das Problem in einer eleganten Lösung zu lösen, indem die folgenden Kriterien erfüllt werden:
1) Die geringste Anzahl von Abfragen an die Datenbank wird gemacht. 2) Die geringste Menge an Crawling durch eine Datenstruktur im Speicher wird gemacht.
Im Wesentlichen ist die Idee, das Folgende zu tun
1) Erstellen Sie eine Zufallszahl von 0 bis 9999999
2) Überprüfen Sie die Datenbank, um festzustellen, ob die Nummer vorhanden ist
ODER
2) Abfrage der Datenbank nach allen Zahlen
3) Sehen Sie, ob das zurückgegebene Ergebnis mit dem übereinstimmt, was von db
kam
4) Wenn es übereinstimmt, wiederholen Sie Schritt 1, wenn nicht, ist das Problem gelöst.
Danke.
Wollen Sie eine übertriebene Lösung?
Ich gehe davon aus, dass Zufälligkeit nicht als Verschlüsselungsqualität gedacht ist, sondern gerade genug, um zu verhindern, dass die Nutzungsdauer eines Benutzers nach user_id geschätzt wird.
Generieren Sie während der Entwicklung eine Liste aller 10 Millionen Zahlen in Zeichenfolgenform.
Führen Sie optional eine einfache Transformation aus, z. B. das Hinzufügen einer konstanten Zeichenfolge zur Mitte. (Dies ist nur für den Fall, dass das Ergebnis zu vorhersehbar ist.)
Übergeben Sie sie an ein Werkzeug, das Perfect Hash-Funktionen generiert, z. B. gperf .
Der resultierende Code kann verwendet werden, um die ID des Benutzers zur Laufzeit schnell in einen eindeutigen Hash-Wert zu codieren, der garantiert nicht mit anderen Hash-Werten kollidiert.
Nein, Ihr Algorithmus ist nicht skalierbar. Was ich vorher gemacht habe, ist, Zahlen seriell (+1 jedes Mal) auszugeben und sie dann durch eine XOR-Operation zu übergeben, um die Bits zu durcheinander zu bringen und mir so scheinbar zufällige Zahlen zu geben. Natürlich sind sie nicht wirklich zufällig, aber sie sehen für die Augen der Benutzer so aus.
[Bearbeiten] Zusätzliche Informationen
Die Logik dieses Algorithmus geht so, dass Sie eine bekannte Sequenz verwenden erzeuge eindeutige Zahlen und manipuliere sie dann deterministisch, sie sehen also nicht mehr seriell aus. Die allgemeine Lösung ist zu verwenden irgendeine Form der Verschlüsselung, die in meinem Fall ein XOR-Flipflop war, weil es ist so schnell wie es nur geht, und es erfüllt die Garantie, dass Zahlen wird niemals kollidieren.
Sie können jedoch andere Formen der Verschlüsselung verwenden, wenn Sie noch mehr bevorzugen zufällig aussehende Zahlen, über die Geschwindigkeit (sagen Sie, dass Sie nicht viele generieren müssen IDs zu einem Zeitpunkt). Jetzt der wichtige Punkt bei der Auswahl eines Verschlüsselungsalgorithmus ist "die Garantie, dass Zahlen niemals kollidieren". Und eine Möglichkeit zu beweisen, ob ein Verschlüsselungsalgorithmus erfüllt werden kann Diese Garantie prüft, ob sowohl die ursprüngliche Anzahl als auch das Ergebnis von die Verschlüsselung hat die gleiche Anzahl von Bits, und das ist der Algorithmus reversibel (Bijektion).
[Danke an Adam Liss & amp; CesarB für die Lösung der Lösung]
Probieren Sie die Anweisung in mysql aus SELECT CAST (RAND () * 1000000 AS INT)
Ich denke, Sie werden feststellen, dass Sie das wirklich nicht tun wollen. Wenn die Zahlen in der Datenbank zunehmen, könnten Sie zu viel Zeit in der Schleife "Sicherstellen, dass diese Nummer nicht vergeben wurde" verbringen.
Ich persönlich hatte Glück mit Hashes als Alternative, aber um eine bessere Lösung zu finden, müsste ich wirklich wissen, warum Sie das so machen wollen.
Meine Erfahrung bestand einfach darin, den RNG in PHP zu verwenden. Ich habe festgestellt, dass eine bestimmte Größe der Nummer (Ich benutze ein int, so dass ich ein Maximum von 4G). Ich habe einige Tests durchgeführt und festgestellt, dass ich im Durchschnitt in 500.000 Iterationen 120 einzelne Duplikate erhielt. Ich habe nie ein Triplikat bekommen, nachdem ich die Schleife einige Male ausgeführt hatte. Meine "Lösung" war dann einfach einzufügen und zu prüfen, ob es fehlschlägt, dann eine neue ID zu generieren und erneut zu gehen.
Mein Rat ist, das Gleiche zu tun und zu sehen, wie hoch die Kollisionsrate ist und ob es für Ihren Fall akzeptabel ist.
Dies ist nicht optimal, also wenn jemand Vorschläge hat, schaue ich auch :)
EDIT: Ich war auf eine 5-stellige ID beschränkt ([a-zA-z0-9] {5,5}), je länger die ID (mehr Kombination, die wenigen Kollisionen). Ein MD5 der E-Mail würde fast nie in Konflikt geraten.
Angenommen:
Sie könnten etwas Einfaches tun, indem Sie die Zufallszahl als 64-Bit-Ganzzahl haben, wobei die oberen 32 Bits den Zeitstempel (bei Zeileneinfügung) und die unteren 32 Bits die Benutzer-ID enthalten. Dies wäre sogar für mehrere Zeilen mit demselben Benutzer eindeutig, vorausgesetzt, Sie verwenden eine geeignete Auflösung für Ihren Zeitstempel, je nachdem, wie oft Sie für denselben Benutzer neue Zeilen hinzufügen. Kombinieren Sie sie mit einer eindeutigen Einschränkung für die zufällige Spalte, und fangen Sie einen solchen Fehler in Ihrer Logik auf und versuchen Sie es dann einfach erneut.
Es ist einfach, einen Pseudozufallszahlengenerator mit einer langen Nichtwiederholung zu entwerfen; z.B. dieses , das für die gleiche Sache verwendet wird, für die Sie es wollen .
BTW, warum nicht einfach die Benutzer-IDs nacheinander ausgeben?
Das Problem ist, dass wenn Sie Zufallszahlen generieren, es sehr gut möglich ist, Duplikate infinately zu erzeugen.
jedoch:
%Vor%Während dies tun wird, was Sie wollen, ist es auch eine schlechte Idee, da diese nicht lange skalieren wird. Eventuell wird Ihr Array zu groß und es wird eine extrem lange Zeit brauchen, um ein zufälliges Ergebnis zu generieren in Ihrer Datenbank.
Ich mag Oddthinks Idee, aber anstatt die stärkste Hash-Funktion der Welt zu wählen, könntest du einfach:
MD5's sind schnell, und wenn Sie überprüfen, ob eine Zeichenkette zu einem Array gehört, vermeiden Sie eine SELECT.
Wenn Sie wirklich "zufällige" Zahlen von 0 bis 9 999 999 erhalten wollen, dann sollten Sie die "Randomisierung" einmal durchführen und dann das Ergebnis auf Ihrer Festplatte speichern.
Es ist nicht schwer, das gewünschte Ergebnis zu erhalten, aber ich denke eher an "mach eine lange Liste mit Zahlen" als an "bekomme eine Zufallszahl".
%Vor%Sie brauchen auch einen Zeiger auf die aktuelle Position in $ numbers (speichern Sie es in einer Datenbank); Beginnen Sie mit 0 und erhöhen Sie es jedes Mal, wenn Sie eine neue Nummer benötigen. (Oder Sie könnten array_shift () oder array_pop () verwenden, wenn Sie keine Zeiger verwenden möchten.)
Ein geeigneter PRNG (Pseudo-Random Number Generator) -Algorithmus hat eine Zykluszeit, während der er niemals im selben Zustand sein wird. Wenn Sie den gesamten Status des PRNG in der von ihm abgerufenen Nummer angeben, erhalten Sie eine Zahl, die für den Zeitraum des Generators eindeutig ist.
Eine einfache PRNG, die dies tut, wird als linearer kongruenter PRNG bezeichnet, der eine Formel iteriert:
%Vor%Unter Verwendung des richtigen Paares von Faktoren können Sie eine Periode von 2 ^ 30 (ungefähr 1 Milliarde) von einem einfachen PRNG mit einem 32-Bit-Akkumulator erhalten. Beachten Sie, dass Sie eine 64 Bit lange temporäre Variable benötigen, um den mittleren AX-Teil der Berechnung zu speichern. Die meisten, wenn nicht alle C-Compiler unterstützen diesen Datentyp. Sie sollten dies auch mit einem numerischen Datentyp in den meisten SQL-Dialekten tun können.
Mit den richtigen Werten von A und M können wir einen Zufallszahlengenerator mit guten statistischen und geometrischen Eigenschaften erhalten. Es gibt ein berühmtes Papier darüber geschrieben von Fishman und Moore.
Für M = 2 ^ 31 - 1 können wir die Werte von A unten verwenden, um eine PRNG mit einer schönen langen Periode (2 ^ 30 IIRC) zu erhalten.
Gute Werte von A:
%Vor%Beachten Sie, dass dieser Generatortyp per Definition nicht kryptografisch sicher ist. Wenn Sie die letzte generierte Nummer kennen, können Sie vorhersagen, was als nächstes zu tun ist. Leider glaube ich, dass Sie keine kryptografische Sicherheit und gleichzeitig garantierte Unwiederholbarkeit erhalten können. Damit ein PRNG kryptographisch sicher ist (z. B. Blum Blum Shub ), kann er nicht genügend Status in einer generierten Nummer verfügbar machen, um den nächsten zu erlauben Nummer in der Sequenz, die vorhergesagt werden soll. Daher ist der interne Zustand breiter als die erzeugte Zahl und (um eine gute Sicherheit zu haben) ist die Periode länger als die Anzahl der möglichen Werte, die erzeugt werden können. Dies bedeutet, dass die exponierte Nummer innerhalb des Zeitraums nicht eindeutig ist.
Aus ähnlichen Gründen gilt das auch für langperiodische Generatoren wie den Mersenne Twister
Ich habe Ihren Standpunkt wahrscheinlich nicht verstanden, aber was ist mit auto_increments?
PHP hat dafür bereits eine Funktion, uniqid . Es erzeugt eine Standard-UUID, die großartig ist, wenn Sie auf die Daten von anderswo zugreifen müssen. Erfinde das Rad nicht neu.
Ich habe vorher schon geschrieben Artikel dazu . Es verfolgt den gleichen Ansatz wie Robert Goulds Antwort, zeigt aber zusätzlich, wie man eine Blockchiffre auf eine geeignete Länge verkürzen kann, indem man x oder faltet, und dann die Permutationen über einen Bereich erzeugt, der keine Potenz von 2 ist Eindeutigkeitseigenschaft.
es gibt ein paar Wege, um über diese eine Möglichkeit zu gehen, ein Array mit den Zahlen 0000000 bis 9999999 zu konstruieren und dann eine zufällige Auswahl dieser Zahlen in diesem Array auszuwählen und tausche die gewählten Zahlenwerte mit dem höchsten Wert Max Reduziere dann max um 1 und wähle ein anderes zufälliges Mitglied dieses Arrays bis zum neuen Maximum aus
bei jeder Reduzierung von Max um eins
zum Beispiel (in basic): (rechts sind Kommentare, die im eigentlichen Programm entfernt werden sollen) Rndfunc ist ein Aufruf an die von Ihnen verwendete Zufallsgeneratorfunktion
%Vor%Machen Sie das für jede Nummer, die Sie auswählen möchten, aber Sie müssen die Möglichkeit haben, sehr große Arrays zu verwenden
Die andere Methode wäre wie folgt: Erzeugen Sie eine Zahl und speichern Sie sie in einem Array, das dynamisch wachsen kann Wählen Sie dann eine neue Zahl aus und vergleichen Sie sie mit dem Wert, der auf halbem Weg zwischen dem ersten und dem letzten Element im Array liegt. In diesem Fall wäre es die erste ausgewählte Nummer Wenn es eine andere Zufallszahl auswählt, sortiere das Array nach der Größe und wenn es keine Übereinstimmung gibt, dann ist es abhängig von der Wetterlage größer oder kleiner als die Zahl, mit der du es verglichen hast Jedes Mal, wenn es nicht übereinstimmt und größer oder kleiner ist als das, mit dem Sie es vergleichen.
Jedes Mal, wenn Sie es halbiert haben, bis Sie eine Lückengröße von eins erreichen, dann checken Sie einmal und halten an, da es keine Übereinstimmung gibt, und dann wird die Nummer zur Liste hinzugefügt und die Liste wird in aufsteigender Reihenfolge neu sortiert, und so weiter bis du fertig bist, zufällige Zahlen zu wählen ... hoffe das hilft ..
Wenn Sie sicherstellen möchten, dass sich die Zufallszahlen nicht wiederholen, benötigen Sie einen sich nicht wiederholenden Zufallsgenerator (wie beschrieben). hier ).
Der Grundgedanke ist, dass die folgende Formel %code% nicht-wiederholende Zufallszahlen für jede Eingabe erzeugt %code% und %code% erzeugt alle anderen Zufallszahlen, die sich nicht wiederholen, aber nur wenn %code% . Alles was du brauchst ist eine Primzahl, die so nah wie möglich an %code% ist. Auf diese Weise kann der Aufwand auf ein einzelnes Lesefeld reduziert werden, aber mit dem Nachteil, dass entweder zu große IDs generiert werden oder zu wenige IDs generiert werden.
Dieser Algorithmus lässt sich nicht sehr gut vertauschen, daher würde ich empfehlen, ihn entweder mit XOR oder Addition oder einem anderen Ansatz zu kombinieren, um den genauen Wert zu ändern, ohne die 1-zu-1-Beziehung zwischen den Seeds und ihrem generierten Wert zu zerstören.
Ich mag Oddthinks Idee, aber anstatt die stärkste Hash-Funktion der Welt zu wählen, könntest du einfach:
MD5's sind schnell, und wenn Sie überprüfen, ob eine Zeichenkette zu einem Array gehört, vermeiden Sie eine SELECT.
Wenn Sie wirklich "zufällige" Zahlen von 0 bis 9 999 999 erhalten wollen, dann sollten Sie die "Randomisierung" einmal durchführen und dann das Ergebnis auf Ihrer Festplatte speichern.
Es ist nicht schwer, das gewünschte Ergebnis zu erhalten, aber ich denke eher an "mach eine lange Liste mit Zahlen" als an "bekomme eine Zufallszahl".
%Vor%Sie brauchen auch einen Zeiger auf die aktuelle Position in $ numbers (speichern Sie es in einer Datenbank); Beginnen Sie mit 0 und erhöhen Sie es jedes Mal, wenn Sie eine neue Nummer benötigen. (Oder Sie könnten array_shift () oder array_pop () verwenden, wenn Sie keine Zeiger verwenden möchten.)
Ein geeigneter PRNG (Pseudo-Random Number Generator) -Algorithmus hat eine Zykluszeit, während der er niemals im selben Zustand sein wird. Wenn Sie den gesamten Status des PRNG in der von ihm abgerufenen Nummer angeben, erhalten Sie eine Zahl, die für den Zeitraum des Generators eindeutig ist.
Eine einfache PRNG, die dies tut, wird als linearer kongruenter PRNG bezeichnet, der eine Formel iteriert:
%Vor%Unter Verwendung des richtigen Paares von Faktoren können Sie eine Periode von 2 ^ 30 (ungefähr 1 Milliarde) von einem einfachen PRNG mit einem 32-Bit-Akkumulator erhalten. Beachten Sie, dass Sie eine 64 Bit lange temporäre Variable benötigen, um den mittleren AX-Teil der Berechnung zu speichern. Die meisten, wenn nicht alle C-Compiler unterstützen diesen Datentyp. Sie sollten dies auch mit einem numerischen Datentyp in den meisten SQL-Dialekten tun können.
Mit den richtigen Werten von A und M können wir einen Zufallszahlengenerator mit guten statistischen und geometrischen Eigenschaften erhalten. Es gibt ein berühmtes Papier darüber geschrieben von Fishman und Moore.
Für M = 2 ^ 31 - 1 können wir die Werte von A unten verwenden, um eine PRNG mit einer schönen langen Periode (2 ^ 30 IIRC) zu erhalten.
Gute Werte von A:
%Vor%Beachten Sie, dass dieser Generatortyp per Definition nicht kryptografisch sicher ist. Wenn Sie die letzte generierte Nummer kennen, können Sie vorhersagen, was als nächstes zu tun ist. Leider glaube ich, dass Sie keine kryptografische Sicherheit und gleichzeitig garantierte Unwiederholbarkeit erhalten können. Damit ein PRNG kryptographisch sicher ist (z. B. Blum Blum Shub ), kann er nicht genügend Status in einer generierten Nummer verfügbar machen, um den nächsten zu erlauben Nummer in der Sequenz, die vorhergesagt werden soll. Daher ist der interne Zustand breiter als die erzeugte Zahl und (um eine gute Sicherheit zu haben) ist die Periode länger als die Anzahl der möglichen Werte, die erzeugt werden können. Dies bedeutet, dass die exponierte Nummer innerhalb des Zeitraums nicht eindeutig ist.
Aus ähnlichen Gründen gilt das auch für langperiodische Generatoren wie den Mersenne Twister
Ich habe vorher schon geschrieben Artikel dazu . Es verfolgt den gleichen Ansatz wie Robert Goulds Antwort, zeigt aber zusätzlich, wie man eine Blockchiffre auf eine geeignete Länge verkürzen kann, indem man x oder faltet, und dann die Permutationen über einen Bereich erzeugt, der keine Potenz von 2 ist Eindeutigkeitseigenschaft.
es gibt ein paar Wege, um über diese eine Möglichkeit zu gehen, ein Array mit den Zahlen 0000000 bis 9999999 zu konstruieren und dann eine zufällige Auswahl dieser Zahlen in diesem Array auszuwählen und tausche die gewählten Zahlenwerte mit dem höchsten Wert Max Reduziere dann max um 1 und wähle ein anderes zufälliges Mitglied dieses Arrays bis zum neuen Maximum aus
bei jeder Reduzierung von Max um eins
zum Beispiel (in basic): (rechts sind Kommentare, die im eigentlichen Programm entfernt werden sollen) Rndfunc ist ein Aufruf an die von Ihnen verwendete Zufallsgeneratorfunktion
%Vor%Machen Sie das für jede Nummer, die Sie auswählen möchten, aber Sie müssen die Möglichkeit haben, sehr große Arrays zu verwenden
Die andere Methode wäre wie folgt: Erzeugen Sie eine Zahl und speichern Sie sie in einem Array, das dynamisch wachsen kann Wählen Sie dann eine neue Zahl aus und vergleichen Sie sie mit dem Wert, der auf halbem Weg zwischen dem ersten und dem letzten Element im Array liegt. In diesem Fall wäre es die erste ausgewählte Nummer Wenn es eine andere Zufallszahl auswählt, sortiere das Array nach der Größe und wenn es keine Übereinstimmung gibt, dann ist es abhängig von der Wetterlage größer oder kleiner als die Zahl, mit der du es verglichen hast Jedes Mal, wenn es nicht übereinstimmt und größer oder kleiner ist als das, mit dem Sie es vergleichen.
Jedes Mal, wenn Sie es halbiert haben, bis Sie eine Lückengröße von eins erreichen, dann checken Sie einmal und halten an, da es keine Übereinstimmung gibt, und dann wird die Nummer zur Liste hinzugefügt und die Liste wird in aufsteigender Reihenfolge neu sortiert, und so weiter bis du fertig bist, zufällige Zahlen zu wählen ... hoffe das hilft ..
Warum verwenden Sie nicht einfach eine GUID? Die meisten Sprachen sollten eine eingebaute Möglichkeit haben, dies zu tun. Es ist garantiert einzigartig (mit sehr vernünftigen Grenzen).
Ich möchte eine Zufallszahl generieren und sie an eine Tabelle in einer Datenbank für eine bestimmte Benutzer-ID ausgeben. Der Haken ist, die gleiche Nummer kann nicht zweimal verwendet werden. Es gibt eine Million Möglichkeiten, dies zu tun, aber ich hoffe, dass jemand, der sehr scharf auf Algorithmen ist, einen cleveren Weg hat, das Problem in einer eleganten Lösung zu lösen, indem die folgenden Kriterien erfüllt werden:
1) Die geringste Anzahl von Abfragen an die Datenbank wird gemacht. 2) Die geringste Menge an Crawling durch eine Datenstruktur im Speicher wird gemacht.
Im Wesentlichen ist die Idee, das Folgende zu tun
1) Erstellen Sie eine Zufallszahl von 0 bis 9999999
2) Überprüfen Sie die Datenbank, um festzustellen, ob die Nummer vorhanden ist
ODER
2) Abfrage der Datenbank nach allen Zahlen
3) Sehen Sie, ob das zurückgegebene Ergebnis mit dem übereinstimmt, was von db
kam
4) Wenn es übereinstimmt, wiederholen Sie Schritt 1, wenn nicht, ist das Problem gelöst.
Danke.
Wollen Sie eine übertriebene Lösung?
Ich gehe davon aus, dass Zufälligkeit nicht als Verschlüsselungsqualität gedacht ist, sondern gerade genug, um zu verhindern, dass die Nutzungsdauer eines Benutzers nach user_id geschätzt wird.
Generieren Sie während der Entwicklung eine Liste aller 10 Millionen Zahlen in Zeichenfolgenform.
Führen Sie optional eine einfache Transformation aus, z. B. das Hinzufügen einer konstanten Zeichenfolge zur Mitte. (Dies ist nur für den Fall, dass das Ergebnis zu vorhersehbar ist.)
Übergeben Sie sie an ein Werkzeug, das Perfect Hash-Funktionen generiert, z. B. gperf .
Der resultierende Code kann verwendet werden, um die ID des Benutzers zur Laufzeit schnell in einen eindeutigen Hash-Wert zu codieren, der garantiert nicht mit anderen Hash-Werten kollidiert.
Nein, Ihr Algorithmus ist nicht skalierbar. Was ich vorher gemacht habe, ist, Zahlen seriell (+1 jedes Mal) auszugeben und sie dann durch eine XOR-Operation zu übergeben, um die Bits zu durcheinander zu bringen und mir so scheinbar zufällige Zahlen zu geben. Natürlich sind sie nicht wirklich zufällig, aber sie sehen für die Augen der Benutzer so aus.
[Bearbeiten] Zusätzliche Informationen
Die Logik dieses Algorithmus geht so, dass Sie eine bekannte Sequenz verwenden erzeuge eindeutige Zahlen und manipuliere sie dann deterministisch, sie sehen also nicht mehr seriell aus. Die allgemeine Lösung ist zu verwenden irgendeine Form der Verschlüsselung, die in meinem Fall ein XOR-Flipflop war, weil es ist so schnell wie es nur geht, und es erfüllt die Garantie, dass Zahlen wird niemals kollidieren.
Sie können jedoch andere Formen der Verschlüsselung verwenden, wenn Sie noch mehr bevorzugen zufällig aussehende Zahlen, über die Geschwindigkeit (sagen Sie, dass Sie nicht viele generieren müssen IDs zu einem Zeitpunkt). Jetzt der wichtige Punkt bei der Auswahl eines Verschlüsselungsalgorithmus ist "die Garantie, dass Zahlen niemals kollidieren". Und eine Möglichkeit zu beweisen, ob ein Verschlüsselungsalgorithmus erfüllt werden kann Diese Garantie prüft, ob sowohl die ursprüngliche Anzahl als auch das Ergebnis von die Verschlüsselung hat die gleiche Anzahl von Bits, und das ist der Algorithmus reversibel (Bijektion).
[Danke an Adam Liss & amp; CesarB für die Lösung der Lösung]
Probieren Sie die Anweisung in mysql aus SELECT CAST (RAND () * 1000000 AS INT)
Ich denke, Sie werden feststellen, dass Sie das wirklich nicht tun wollen. Wenn die Zahlen in der Datenbank zunehmen, könnten Sie zu viel Zeit in der Schleife "Sicherstellen, dass diese Nummer nicht vergeben wurde" verbringen.
Ich persönlich hatte Glück mit Hashes als Alternative, aber um eine bessere Lösung zu finden, müsste ich wirklich wissen, warum Sie das so machen wollen.
Meine Erfahrung bestand einfach darin, den RNG in PHP zu verwenden. Ich habe festgestellt, dass eine bestimmte Größe der Nummer (Ich benutze ein int, so dass ich ein Maximum von 4G). Ich habe einige Tests durchgeführt und festgestellt, dass ich im Durchschnitt in 500.000 Iterationen 120 einzelne Duplikate erhielt. Ich habe nie ein Triplikat bekommen, nachdem ich die Schleife einige Male ausgeführt hatte. Meine "Lösung" war dann einfach einzufügen und zu prüfen, ob es fehlschlägt, dann eine neue ID zu generieren und erneut zu gehen.
Mein Rat ist, das Gleiche zu tun und zu sehen, wie hoch die Kollisionsrate ist und ob es für Ihren Fall akzeptabel ist.
Dies ist nicht optimal, also wenn jemand Vorschläge hat, schaue ich auch :)
EDIT: Ich war auf eine 5-stellige ID beschränkt ([a-zA-z0-9] {5,5}), je länger die ID (mehr Kombination, die wenigen Kollisionen). Ein MD5 der E-Mail würde fast nie in Konflikt geraten.
Angenommen:
Sie könnten etwas Einfaches tun, indem Sie die Zufallszahl als 64-Bit-Ganzzahl haben, wobei die oberen 32 Bits den Zeitstempel (bei Zeileneinfügung) und die unteren 32 Bits die Benutzer-ID enthalten. Dies wäre sogar für mehrere Zeilen mit demselben Benutzer eindeutig, vorausgesetzt, Sie verwenden eine geeignete Auflösung für Ihren Zeitstempel, je nachdem, wie oft Sie für denselben Benutzer neue Zeilen hinzufügen. Kombinieren Sie sie mit einer eindeutigen Einschränkung für die zufällige Spalte, und fangen Sie einen solchen Fehler in Ihrer Logik auf und versuchen Sie es dann einfach erneut.
Es ist einfach, einen Pseudozufallszahlengenerator mit einer langen Nichtwiederholung zu entwerfen; z.B. dieses , das für die gleiche Sache verwendet wird, für die Sie es wollen .
BTW, warum nicht einfach die Benutzer-IDs nacheinander ausgeben?
Das Problem ist, dass wenn Sie Zufallszahlen generieren, es sehr gut möglich ist, Duplikate infinately zu erzeugen.
jedoch:
%Vor%Während dies tun wird, was Sie wollen, ist es auch eine schlechte Idee, da diese nicht lange skalieren wird. Eventuell wird Ihr Array zu groß und es wird eine extrem lange Zeit brauchen, um ein zufälliges Ergebnis zu generieren in Ihrer Datenbank.
Ich mag Oddthinks Idee, aber anstatt die stärkste Hash-Funktion der Welt zu wählen, könntest du einfach:
MD5's sind schnell, und wenn Sie überprüfen, ob eine Zeichenkette zu einem Array gehört, vermeiden Sie eine SELECT.
Wenn Sie wirklich "zufällige" Zahlen von 0 bis 9 999 999 erhalten wollen, dann sollten Sie die "Randomisierung" einmal durchführen und dann das Ergebnis auf Ihrer Festplatte speichern.
Es ist nicht schwer, das gewünschte Ergebnis zu erhalten, aber ich denke eher an "mach eine lange Liste mit Zahlen" als an "bekomme eine Zufallszahl".
%Vor%Sie brauchen auch einen Zeiger auf die aktuelle Position in $ numbers (speichern Sie es in einer Datenbank); Beginnen Sie mit 0 und erhöhen Sie es jedes Mal, wenn Sie eine neue Nummer benötigen. (Oder Sie könnten array_shift () oder array_pop () verwenden, wenn Sie keine Zeiger verwenden möchten.)
Ein geeigneter PRNG (Pseudo-Random Number Generator) -Algorithmus hat eine Zykluszeit, während der er niemals im selben Zustand sein wird. Wenn Sie den gesamten Status des PRNG in der von ihm abgerufenen Nummer angeben, erhalten Sie eine Zahl, die für den Zeitraum des Generators eindeutig ist.
Eine einfache PRNG, die dies tut, wird als linearer kongruenter PRNG bezeichnet, der eine Formel iteriert:
%Vor%Unter Verwendung des richtigen Paares von Faktoren können Sie eine Periode von 2 ^ 30 (ungefähr 1 Milliarde) von einem einfachen PRNG mit einem 32-Bit-Akkumulator erhalten. Beachten Sie, dass Sie eine 64 Bit lange temporäre Variable benötigen, um den mittleren AX-Teil der Berechnung zu speichern. Die meisten, wenn nicht alle C-Compiler unterstützen diesen Datentyp. Sie sollten dies auch mit einem numerischen Datentyp in den meisten SQL-Dialekten tun können.
Mit den richtigen Werten von A und M können wir einen Zufallszahlengenerator mit guten statistischen und geometrischen Eigenschaften erhalten. Es gibt ein berühmtes Papier darüber geschrieben von Fishman und Moore.
Für M = 2 ^ 31 - 1 können wir die Werte von A unten verwenden, um eine PRNG mit einer schönen langen Periode (2 ^ 30 IIRC) zu erhalten.
Gute Werte von A:
%Vor%Beachten Sie, dass dieser Generatortyp per Definition nicht kryptografisch sicher ist. Wenn Sie die letzte generierte Nummer kennen, können Sie vorhersagen, was als nächstes zu tun ist. Leider glaube ich, dass Sie keine kryptografische Sicherheit und gleichzeitig garantierte Unwiederholbarkeit erhalten können. Damit ein PRNG kryptographisch sicher ist (z. B. Blum Blum Shub ), kann er nicht genügend Status in einer generierten Nummer verfügbar machen, um den nächsten zu erlauben Nummer in der Sequenz, die vorhergesagt werden soll. Daher ist der interne Zustand breiter als die erzeugte Zahl und (um eine gute Sicherheit zu haben) ist die Periode länger als die Anzahl der möglichen Werte, die erzeugt werden können. Dies bedeutet, dass die exponierte Nummer innerhalb des Zeitraums nicht eindeutig ist.
Aus ähnlichen Gründen gilt das auch für langperiodische Generatoren wie den Mersenne Twister
Ich habe Ihren Standpunkt wahrscheinlich nicht verstanden, aber was ist mit auto_increments?
PHP hat dafür bereits eine Funktion, uniqid . Es erzeugt eine Standard-UUID, die großartig ist, wenn Sie auf die Daten von anderswo zugreifen müssen. Erfinde das Rad nicht neu.
Ich habe vorher schon geschrieben Artikel dazu . Es verfolgt den gleichen Ansatz wie Robert Goulds Antwort, zeigt aber zusätzlich, wie man eine Blockchiffre auf eine geeignete Länge verkürzen kann, indem man x oder faltet, und dann die Permutationen über einen Bereich erzeugt, der keine Potenz von 2 ist Eindeutigkeitseigenschaft.
es gibt ein paar Wege, um über diese eine Möglichkeit zu gehen, ein Array mit den Zahlen 0000000 bis 9999999 zu konstruieren und dann eine zufällige Auswahl dieser Zahlen in diesem Array auszuwählen und tausche die gewählten Zahlenwerte mit dem höchsten Wert Max Reduziere dann max um 1 und wähle ein anderes zufälliges Mitglied dieses Arrays bis zum neuen Maximum aus
bei jeder Reduzierung von Max um eins
zum Beispiel (in basic): (rechts sind Kommentare, die im eigentlichen Programm entfernt werden sollen) Rndfunc ist ein Aufruf an die von Ihnen verwendete Zufallsgeneratorfunktion
%Vor%Machen Sie das für jede Nummer, die Sie auswählen möchten, aber Sie müssen die Möglichkeit haben, sehr große Arrays zu verwenden
Die andere Methode wäre wie folgt: Erzeugen Sie eine Zahl und speichern Sie sie in einem Array, das dynamisch wachsen kann Wählen Sie dann eine neue Zahl aus und vergleichen Sie sie mit dem Wert, der auf halbem Weg zwischen dem ersten und dem letzten Element im Array liegt. In diesem Fall wäre es die erste ausgewählte Nummer Wenn es eine andere Zufallszahl auswählt, sortiere das Array nach der Größe und wenn es keine Übereinstimmung gibt, dann ist es abhängig von der Wetterlage größer oder kleiner als die Zahl, mit der du es verglichen hast Jedes Mal, wenn es nicht übereinstimmt und größer oder kleiner ist als das, mit dem Sie es vergleichen.
Jedes Mal, wenn Sie es halbiert haben, bis Sie eine Lückengröße von eins erreichen, dann checken Sie einmal und halten an, da es keine Übereinstimmung gibt, und dann wird die Nummer zur Liste hinzugefügt und die Liste wird in aufsteigender Reihenfolge neu sortiert, und so weiter bis du fertig bist, zufällige Zahlen zu wählen ... hoffe das hilft ..
Wenn Sie sicherstellen möchten, dass sich die Zufallszahlen nicht wiederholen, benötigen Sie einen sich nicht wiederholenden Zufallsgenerator (wie beschrieben). hier ).
Der Grundgedanke ist, dass die folgende Formel %code% nicht-wiederholende Zufallszahlen für jede Eingabe erzeugt %code% und %code% erzeugt alle anderen Zufallszahlen, die sich nicht wiederholen, aber nur wenn %code% . Alles was du brauchst ist eine Primzahl, die so nah wie möglich an %code% ist. Auf diese Weise kann der Aufwand auf ein einzelnes Lesefeld reduziert werden, aber mit dem Nachteil, dass entweder zu große IDs generiert werden oder zu wenige IDs generiert werden.
Dieser Algorithmus lässt sich nicht sehr gut vertauschen, daher würde ich empfehlen, ihn entweder mit XOR oder Addition oder einem anderen Ansatz zu kombinieren, um den genauen Wert zu ändern, ohne die 1-zu-1-Beziehung zwischen den Seeds und ihrem generierten Wert zu zerstören.
Ich habe Ihren Standpunkt wahrscheinlich nicht verstanden, aber was ist mit auto_increments?
Wenn Sie sicherstellen möchten, dass sich die Zufallszahlen nicht wiederholen, benötigen Sie einen sich nicht wiederholenden Zufallsgenerator (wie beschrieben). hier ).
Der Grundgedanke ist, dass die folgende Formel seed * seed & p nicht-wiederholende Zufallszahlen für jede Eingabe erzeugt x such that 2x < p und p - x * x % p erzeugt alle anderen Zufallszahlen, die sich nicht wiederholen, aber nur wenn p = 3 mod 4 . Alles was du brauchst ist eine Primzahl, die so nah wie möglich an 9999999 ist. Auf diese Weise kann der Aufwand auf ein einzelnes Lesefeld reduziert werden, aber mit dem Nachteil, dass entweder zu große IDs generiert werden oder zu wenige IDs generiert werden.
Dieser Algorithmus lässt sich nicht sehr gut vertauschen, daher würde ich empfehlen, ihn entweder mit XOR oder Addition oder einem anderen Ansatz zu kombinieren, um den genauen Wert zu ändern, ohne die 1-zu-1-Beziehung zwischen den Seeds und ihrem generierten Wert zu zerstören.
Tags und Links algorithm php mysql random pseudocode