[HaBo]

Eydeet

Anzeige

Hallo,
Ich suche eine möglichst performante Möglichkeit, um einen zufälligen Wert zu finden (z.B. im Bereich von 0-10000), der noch nicht in einer Datenbank (z.B. MySQL) gespeichert ist. Dieser Wert soll der Datenbank dann hinzugefügt werden.

Was ich mir überlegt habe, ist folgendes:
1. Einfach per Zufall durchprobieren, bis etwas gefunden ist
2. Eine zweite Tabelle anlegen, in der die Werte gespeichert sind, die noch nicht vergeben sind
3. Alle vergebenen Werte aus der Datenbank holen und an einer zufälligen Position anfangen zu suchen.

Bei Möglichkeit 1 findet man entweder sofort etwas, oder man sucht sich zu Tode (vor Allem, wenn kein Wert mehr frei ist).

Bei Möglichkeit 2 braucht man u.U. Massen von zusätzlichem Speicherplatz, und bei Möglichkeit 3 u.U. eine Menge Memory.

Fällt vielleicht jemandem unter euch eine intelligentere Lösung ein? Bis jetzt gefällt mir Möglichkeit 3 am Besten.

Mfg, Eydeet

Elderan

Hallo,
die erste Frage: Ist das wirklich notwendig?


Ansonsten würde ich für eine abgeänderte Variante 1 tendieren, stellst erst per count() fest, wieviele Zahlen vorhanden sind.
Ist diese klein genug, nimmst du Möglichkeit 1.

Sollte die Zahl zu groß sein, dann nimm Variante 3.
Dies kann man noch abändern. Du gehst z.B. in 100er Schritten vorwärts, beginnst bei einer zufälligen Zahl x und lässt dir alle Zufallswerte zwischen x und x+100 ausgeben.
Sollte eine Lücke vorhanden sein, wähle diese.
Ansonsten erhöhe x um 100 (modulo 10 000) und beginne von vorne.

Dies lässt sich noch schöner Implementieren, mit einer abgeänderten Variante des binären Suchens:
Du schränkst den Bereich auf z.B. x+1000 ein und ermittelst per count(), wieviele Elemente du hast. Wenn das zufallsfeld indiziert ist, geht das recht schnell.
Sollte count() 1000 liefern, fahre fort wie oben (x + 1000 mod 10k)
Sollte count() < 1000, dann schaue die Differenz an. Sollte diese groß sein, kann man wieder Möglichkeit 1 nehmen, mit einem Zufallswert zwischen x und x+1000.
Wenn diese Diff zu klein ist, überprüfe x und x+500, wieviele freie Zahlen dadrin stehen. Sollte es keine Zahl sein, dann teste x+500 bis x+1000.
Dies kann man dann entsprechend weit einschränken.


Aber dies sind alles keine schönen Lösungen und wahrscheinlich lässt sich dein Problem auch besser lösen.

CDW

Darf man fragen, wozu das ganze dienen soll (eventuell ist der ganze Ansatz dann überflüssig )

Ansonsten würde ich Lösung 1 bevorzugen, allerdings:
den Seed sowie die Nummer der Zahl (Index der Folge) speichern (ok, könnte man auch durch Select COUNT(spalten) from zufallstabelle usw lösen). Sowie darauf achten, dass die Tabelle nie zu voll wird (Richtwert 75% sollte reichen, kommt von den Hashtabellen"defaultfüllwert", sollte aber genauso gut hier funktionieren). Übertragen auf DB würde das heißen: wenn z.B von 1 bis 100 000 Zufallszahlen generiert werden sollen und schon 75 000 Einträge in der Tabelle vorhanden sein, sollte entweder die Grenze nach oben verschoben werden oder ernsthafte Gedanken darüber gemacht, ob man nicht gleich alles normal durchnummeriert

Wenn eine neue Zufallszahl generiert werden sollte - den Zufallsgenerator mit dem gespeicherten Seedwert initialisieren, erstmal X Werte generieren lassen und ab da die 1. Strategie anwenden. Sofern der Zufallsgenerator mehr oder weniger anständig ist, sollte die Suche nach dem Wert nicht allzulange dauern. Denn der Zufallsgenerator sollte im Nu 10 000 Durchgänge durchlaufen können und anschließend irgendeine Zahl generieren, die noch nicht dran war.
Oder Du achtest allgemein auf den Füllwert (wie gesagt, Richtwert von 75% halte ich für ok, man kann es aber auch leicht nach oben verschieben) - dann dürften auch mit 1. keine Probleme auftreten.

__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.

LX

Du könntest auch einfach bereits alle Werte in die Datenbank eintragen und als weitere Spalte in der Tabelle ein Flag hinzufügen, ob dieser Wert bereits verwendet wurde. Dann selektierst du einfach auf Werte, bei denen dieses Flag nicht gesetzt ist. Das frisst Speicher, aber ist vermutlich das performanteste. Das entspricht etwa deiner Version 2, kommt aber ohne zweite Tabelle aus (und vereinfacht so die Abfragen und macht es einfacher, das ganze konsistent zu halten).

__________________
"Ever tried. Ever failed. No matter.
Try again. Fail again. Fail better."
- Samuel Beckett

JS BB LX UP

Eydeet

Es geht bei der ganzen Sache um eine Art Online-Spiel. Jeder Spieler soll am Anfang eine Stadt bekommen, die aber nicht einfach der Reihe nach vergeben werden sollen.
Alternativ zu dem Weg mit den Zufallszahlen ist mir noch ein Weg eingefallen, da die Zahlen eigentlich nicht wirklich streng zufällig sein müssen: (FixPrimzahl * i) mod 10000. Das ist wahrscheinlich für meinen Fall am Sinnvollsten.
Ich werde aber auch mal mit den Zufallszahlen rumexperimentieren, also vielen Dank an euch drei!

Heinzelotto

such doch einfach zufällig eine stadt aus uns schau, ob sie schon vergeben ist. Zumindest im Anfangsstadium des Spieles, wenn erst wenige Städte vergeben sind, sollte das die effektivste Methode sein.

Elderan

Hallo,
@Eydeet: Den Ansatz hat CDW oben schon beschrieben. Entweder die internen PHP Funktionen benutzen oder selber einen linearen Kongruenzgenerator bauen:
$x = 1103515245*$x + 12345 & 0x7fffffff;
Dann return $x mod 10000;

(siehe hier)


Allerdings solltest du wirklich überlegen, ob du die Zufallszahlen brauchst. Man kann Städte auch inkrementell verteilen und es nur bei der Ausgabe zufällig aussehen lassen, dazu müsste man aber mehr über deine Motivationen wissen

Serow

Wie wärs wenn du dir aus der DB die Städte holst, die noch nicht vergeben sind und wählst aus der Menge dann eine zufällig aus !?!!?