Hallo zusammen,
ich habe mir gestern Abend ein Problem näher angesehen, zu dem ich keine bessere Lösung gefunden habe, als die, die hier gepostet. Aufgabe: Es sollen N Zufallszahlen generiert werden, die nich gleich sind. Hintergrund ist, dass ich aus einem Array N, zufällig ausgewählte Werte extrahieren will und da brauche ich eben verschiedene Zufallszahlen. Ja, ich weiß, man kann das Problem auch anders angehen, es geht hier aber um eine allgemeine Lösung, da man diese dann z.B. auch für Lotto einsetzen könnte.
Hier mal ein wenig Pseudocode, wie ich es im Moment machen würde:
Code:
Zufallszahlen := []
While Length(Zufallszahlen) < N do
ZZ := GeneriereZufallszahl(Range)
if (not ZufallszahlVorhanden(Zufallszahlen, ZZ))
Zufallszahlen.Add(ZZ)
Sollten Fragen dies bzgl. auftauchen, ann einfach sagen, aber ich denke es sollte einigermaßen klar sein. Der Range-Parameter entspricht dem aus der
Delphi-Random()-Funktion.
Das Problem hierbei ist ja, dass vor allem für kleine Range-Werte der Algorithmus sehr oft laufen kann, da je kleiner Range ist, die Wahrscheinlichkeit für eine Kollision steigt. Ich sehe einzig und allein bei der Funktion ZufallszahlVorhanden() Optimierungspotential und zwar in Form einer sehr effizienten Suche. Meine Idee ist hier, dass Zufallszahlen eine Hashmap ist und so die Suche in O(1) statt findet.
Kann man das noch besser gestalten?
»Remember, the future maintainer is the person you should be writing code for, not the compiler.« (Nick Hodges)