3. Keine doppelten Zufallszahlen aus großem Bereich

Keine doppelten Zufallszahlen aus großem Bereich

  • P

    Hallo,

    leider bringt mir die Suchfunktion nicht die Lösung die ich brauche.

    Ich möchte 14 Mio. mal eine Zufallszahl ziehen, aus einem 14 Mio. großen Bereich. Dabei darf die Zufallszahl sich nicht wiederholen. Also ein sehr großes Array zu nehmen, und dieses dann zufällig zu mischen (random_shuffle) ist eine nicht praktikable Lösung. Ich brauche also einen Zufallszahlengenerator, der aus einem Bereich mit x Zahlen genau x mal eine Zahl zieht, die sich nicht wiederholen.

    Bei Überblendeffekten von Bilder hab ich so etwas schon gesehen, denn es werden da zufällige Pixel ausgetauscht, ohne das es langsamer wird oder Pixel doppelt getauscht werden.

    Pronto451

    0

  • Pronto451 schrieb:

    Hallo,

    Bei Überblendeffekten von Bilder hab ich so etwas schon gesehen, denn es werden da zufällige Pixel ausgetauscht, ohne das es langsamer wird oder Pixel doppelt getauscht werden.

    Pronto451

    Dann nimm doch statt dessen ein 14 Mio. Bit großes Bitfeld und setze für jede ermittelte Zufallszahl das entsprechende Bit. Dann weiß dein Program, ob diese Zahl schon einmal vorkam.

    0
  • P

    Hallo Burkhi,

    aber dann brauche ich für die letzten Zufallszahlen enorm viel Zeit, bis sie ermittelt werden. Das ist keine praktikable Lösung. Es soll ja zum schluß genau so schnell eine Zahl ermittelt werden wie am Anfang.

    Pronto451

    0
  • ?

    Wenn ein Bitfeld gesetzt ist, dann setzte das darauffolgende (u.s.w). Im schlimmsten Fall wird erst das 14-Millionste gesetzt.

    0
  • V

    Pronto451 schrieb:

    Bei Überblendeffekten von Bilder hab ich so etwas schon gesehen, denn es werden da zufällige Pixel ausgetauscht, ohne das es langsamer wird oder Pixel doppelt getauscht werden.

    da fallen mir schon ein paar lösungen ein.

    du nimmst nen "zufallszahlengenerator", der in der tat 14Mio verschiedene zahlen produziert. wie wär's mit x=(x+k)%14000000 ? nimm als k einfach was in der nähe von i*14000000 und als i was fürchterlich irrationales. versuch's immer zuerst mit (sqrt(5)-1)/2, also 0.61803398874989484820458683436564 (siehe goldener schnitt). macht für k was um 8652475. leider sind k und 14000000 nicht prim zueinander. 8652477 müßte aber gehen.
    also

    x=(x+8652477)%14000000;

    so, tester das mal, und sag, ob es zufriedenstellend ist.

    nu könnten wir probleme mit der division haben. die ist evtl ein wenig zu lahm für unseren geschmack. kein problem. nehmen wir einfach mal

    do
 x=(x+k)%16777216;
while(x>=14000000);

    und freuen und drüber, daß %16777216 vom compiler zu nem &16777215 optimiert wird und daß wir keine divisionen mehr haben.

    an k können wir auch noch basteln. du hast natürlich für 16777216 schon ein feines k ausgerechnet, was auch ungerade ist?

    0
  • ?

    War zwar nicht meine Frage, habe aber die Antwort von Volkard gelesen. Wie löst du dann die Sache mit dem Ausschluß der bereits gezogenen Zahlen?

    0
  • V

    helfer 23 schrieb:

    War zwar nicht meine Frage, habe aber die Antwort von Volkard gelesen. Wie löst du dann die Sache mit dem Ausschluß der bereits gezogenen Zahlen?

    mein generator zieht keine zahlen doppelt.

    0
  • A

    @helfer 23 der Generator produziert eine Kette von Zahlen in der jede Zahl nur
    einmal verwendet wird. Genau das ist der Witz an der Sache. Wird z.B. häufig
    zum Selbsttest von IC's oder auf Prüfständen verwendet.

    0
  • C

    Dieser Thread wurde von Moderator/in Jansen aus dem Forum Borland C++ Builder (VCL/CLX) in das Forum Rund um die Programmierung verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.

    0
  • ?

    volkard schrieb:

    helfer 23 schrieb:

    War zwar nicht meine Frage, habe aber die Antwort von Volkard gelesen. Wie löst du dann die Sache mit dem Ausschluß der bereits gezogenen Zahlen?

    mein generator zieht keine zahlen doppelt.

    Und zwar genau dann wenn ggT(k,16777216) = 1. Da 16777216 = 2^24 reicht es wirklich wenn k ungerade ist.

    Interessant dazu vielleicht der allgemeine Ansatz:

    Dazu nehmen wir einen Linearen Kongruenzgenerator. Erstmal vier natürliche Zahlen (a,c,m,x(0)) mit a,m >=1 und c,x(0)>=0.
    Dann wird der Generator (d.h. die Folge der Zahlen) definiert durch

    x(n+1) = (a * x(n) + c) mod m

    Dann gibt es den Satz von Greenberger/Hull/Dobell:
    Der Lineare Kongruenzgenerator (a,c,m,x(0)) hat (volle) Periode m, genau dann wenn
    (i) ggT(c,m)=1
    (ii) p Primteiler von m so gilt p|(a-1)
    (iii) wenn 4|m so auch 4|(a-1)

    Volkard hatte gewählt a=1, c=k und m=2^24.
    Bedingung (ii) und (iii) sind erfüllt weil es ein rein additiver Generator ist. Bleibt also wie oben gesagt, dass ggT(k,2^24) = 1 erfüllt sein muss.

    Damit kann man ganz gut Generatoren mit bel. langer Periode bauen.

    space

    0
Anmelden zum Antworten