Zufalls Generator
-
Um 6 aus 49 zu ermitteln, mache ich mir noch keine großen Gedanken über die Performance
(und bei größeren Mengen würde ich wohl random_shuffle() verwenden). Und bedenkst du auch, daß deine Variante deutlich mehr Speicherplatz (und Zeit) benötigt, um die Suche überhaupt vorzubereiten? (gerade wenn nur eine kleine Teilmenge der möglichen Werte gesucht wird, dürfte selbst O(n²) günstiger sein als O(n+m))
-
du solltest aber bedenken, dass dein verfahren mit etwas pech einfach ewig dauert (wenn man davon ausgeht, dass rand echte zufallszahlen liefert).. Relevant wird das besonders, wenn sich dein n dem Wertebereich m stark annähert. So z.b. wenn du jetzt 48 paarweise verschiedene Zufallszahlen zwischen 0 - 50 suchen möchtest..
random_shuffle ist für das Problem auch nicht unbedingt meine erste Wahl, da du damit einfach viel zu viel machst und dann nachher wieder ein Teil rausschmeißt (wobei random_shuffle dann besser wird wenn sich n m annähered (also genau umgekehrt))..
-
life schrieb:
das mit den doppelten zufallszahlen verhindern geht auch effektiver..
Wie, noch effektiver als wenn keine doppelten mehr drin sind? Also sozusagen *gar* keine doppelten mehr drin? Oder meinst Du vielleicht effizienter? :p
Aber ne schöne Lösung!Allerdings kann man die erwartete Anzahl an Schritten ausrechnen. Die Schätze ich mal auf knapp über 1, bei diesen Werten. Die Wahrscheinlichkeit, daß es terminiert liegt übrigens bei 1. Die für unendliches Weiterlaufen bei 0, es kann also eigentlich nicht unendlich lange laufen. Beliebig lange schon, aber halt nicht unendlich.
-
Jester schrieb:
Allerdings kann man die erwartete Anzahl an Schritten ausrechnen. Die Schätze ich mal auf knapp über 1, bei diesen Werten. Die Wahrscheinlichkeit, daß es terminiert liegt übrigens bei 1. Die für unendliches Weiterlaufen bei 0, es kann also eigentlich nicht unendlich lange laufen. Beliebig lange schon, aber halt nicht unendlich.
Beliebig lange kann aber schon ganz lange sein ;). Und im "worst-case" braucht der Algorithmus nunmal unendliche lange, obwohl die wahrscheinlichkeit für den "worst-case" bei 0 liegt (hört sich zugegebenermaßen irgendwie paradox an)
-
Nein, dieser worst-case tritt sicher nicht ein. Seine Wahrscheinlichkeit liegt nämlich bei 0.
-
Auch wenn der Fall nie auftritt, denke ich, kann man ihn als worst-case bezeichnen.. oder was ist dann deiner Meinung nach der worst-case bei dem Algorithmus? :p
-
life schrieb:
Auch wenn der Fall nie auftritt, denke ich, kann man ihn als worst-case bezeichnen.. oder was ist dann deiner Meinung nach der worst-case bei dem Algorithmus? :p
Das ist natürlich ne berechtigte Frage.
Aber wie relevant ist ein "worst-case", der nie eintritt?
-
"worst case" ist der schlechteste Fall, der eintreten KANN - von daher brauchst du etwas definitiv unmögliches nicht zu betrachten
-
Jester schrieb:
Wie, noch effektiver als wenn keine doppelten mehr drin sind? Also sozusagen *gar* keine doppelten mehr drin? Oder meinst Du vielleicht effizienter? :p
Da fällt mir zu ein, wie(*) einmal ein Prof süffisant zu mir sagte:
Ihre (Programm-)Lösung ist wirklch sehr effizient,
nur leider nicht effektivSeitdem hat sich der Unterschied zwischen effizient und effektiv bei
mir eingebranntP.S.: (*) Nein, in diesem Fall meine ich wirklich wie und nicht als
-
CStoll schrieb:
"worst case" ist der schlechteste Fall, der eintreten KANN - von daher brauchst du etwas definitiv unmögliches nicht zu betrachten
Dann gibt es allerdings auch Algorithmen, die garkeinen worst-case besitzen...
-
Es gibt nur eine Gute version
http://www.openbsd.org/de/crypto.html#prng
Musst mal schauen wo die die libs bekommst.
Ist glaube ich in glibc integriert *irrtum vorbehalten*gg