Zufallsgenerator mit Gewichtung (aber mit sehr großen Datenmengen)

[Bambuti2000]

Hallo Communnity,

ich hab mal wieder ein Problem.
Wir haben vor die Gewinner einer Verlosung per Zufallsgenerator zu ermitteln. (Haha, kein Problem)
Jetzt soll aber eine Gewichtung mit einfließen. Und zwar soll sich für jeden Euro(€) Einzahlung auf's Konto die Gewinnchance um 1 erhöhen.
Damit es nicht so einfach ist, mal ein paar Randdaten:
- ca. 150000 Kunden
- Einlagen zwischen 1€ & 1000000€

Hier mal mein Code der zwar funktioniert, aber nur wenn ich die Summen um den Faktor 100 dividiere.

Delphi-Quellcode:

      Randomize;
      srcFile := TStringStream.Create;
      srcStrings := TStringList.Create;
      randList := TStringList.Create;

      try
        WriteLn('Lade Quelle ...');
        srcFile.LoadFromFile('source.csv');
        srcStrings.LoadFromStream(srcFile);
        WriteLn('Erstelle Zufallsliste nach Gewichtung ...');
        for I := 0 to srcStrings.Count - 1 do
        begin
          Write(#13, Format('[%d%%]', [(100 * I) div srcStrings.Count]));
          for J := 1 to srcStrings.Count - 1 do
          begin
            randList.Add(Explode(srcStrings.Strings[I], ';', 1));
          end;
        end;
        WriteLn;

        for I := 0 to 9 do
          WriteLn('Gewinner: ' + randList.Strings[Random(randList.Count)]);
        ReadLn;
      finally
        FreeAndNil(srcFile);
        srcStrings.Free;
        randList.Free;
      end;

Mit den gekürzten Summen, habe ich allerdings schon eine Speicherbelegung von mehr als 6GB und es wird ausgelagert.
Versuche ich das ganze mit den Originaldaten, friert mein System nach etwa 30 Sekunden ein und ... ich brauch' gar nicht weiter reden.

Also, über eure Hilfe wie ich diese Daten vernünftig verarbeiten kann wäre ich echt dankbar.

Ach so, die Funktion "Explode" holt mir die Komma-Separierten Daten aus der CSV (Kunde;Summe [oder auch Gewichtung]).

Gruß
Stefan

[Dejan Vu]

Ok. Angenommen, Du hast 3 Kunden (A,B,C), mit 1,2 und 3 Euronen. Die einfachste Lösung wäre ja die, einfach eine Liste zu erstellen, in der ein Kunde so oft vorkommt, wie er Geld eingezahlt hat (wasndas für ein Deutsch?). Egal. Also die Liste wäre: A,B,B,C,C,C. Das sind 6 Einträge. Nun eine Zufallszahl z zwischen 1 und 6 und dann einfach den Kunden an der Stelle z in der Liste auslesen.

Bei deiner Anzahl ist das vielleicht ein wenig viel. Also machen wir es einfacher. Sei K die Liste der Kunden und E die Liste der Einzahlungen, sodass Kunde K[i] E[i] Euro eingezahlt hat. Sei ferner S die Summe aller Einzahlungen. Dann bildest Du eine Zufallszahl Z im Bereich (1..S). Gewonnen hat der Kunde K[i], für denn die Summe der Einzahlungen E[1]..E[i-1] < Z mit maximalem i ist. D.h. E[1]+...+E[i-1]<Z aber E[1]+...+E[i]>=Z

Beispiel: siehe oben:
Z=1. Gewonnen hat A, denn E[1]>=1;
Z=2. Gewonnen hat B, denn E[1]<2 aber E[1]+E[2] >= 2;
Z=3. Gewonnen hat B, denn E[1]<3 aber E[1]+E[2] >= 3;
Z=4. Gewonnen hat C, denn E[1]+E[2]<4 aber E[1]+E[2]+E[3] >= 4;
Z=5. Gewonnen hat C, denn E[1]+E[2]<5 aber E[1]+E[2]+E[3] >= 5;
Z=6. Gewonnen hat C, denn E[1]+E[2]<6 aber E[1]+E[2]+E[3] >= 6;

Wie man sieht, entspricht die Gewinnwahrscheinlichkeit eines Kunden exakt seiner eingezahlten Summe.

Delphi-Quellcode:

Function AndTheWinnerIs (K : KundeListe; E : EinzahlungsListe) : TKunde;
Var
  i, theWinner, Summe : Integer;
  
Begin
  Summe := E.Summe; // Summe aller Einzahlungen 
  theWinner := Random (Summe) + 1; 
  i := 0;
  While theWinner>E[i] do begin
     dec (theWinner, E[i]);
     inc(i);
  end;
  result := K[i]
End;

Noch besser ist jedoch dieses Verfahren:

Delphi-Quellcode:

Function AndTheWinnerIs(K : KundeListe; E : EinzahlungsListe) : TKunde;
Begin
  Result := 'Dejan Vu';
End;

Ich schicke Dir meine Kontoverbindung per PN

[gammatester]

Zitat von Bambuti2000:

Hier mal mein Code der zwar funktioniert, aber nur wenn ich die Summen um den Faktor 100 dividiere.

Summen? Wo sind da Summen? Außerdem sehe ich noch nicht einmal Zahlen, sondern bis auf die Schleifenindices nur Strings.

Zahlen werden als Zahlen gespeichert und verarbeitet! Alles andere ist Zeit- und Speicherplatzverschwendung.

PS1: Man dividiert nicht um Faktoren, noch nicht einmal durch Faktoren. Faktoren sind Teile von Produkten.

PS2: Bei (Fließkomma-)Zahlen belegen übrigens die Zahlen selbst und die durch 100 dividierten den gleichen Platz, nämlich 4 bzw. 8 Byte.

[Klaus01]

Hallo Stefan,

so wie ich das sehe, hälts Du die Daten dreimal im Speicher.
Als srcFile (TStringStream) als srcStrings (TStringList) and
als randlist (TStringList).

Warum liest Du die Datei nicht direkt in die StringList ein?
Warum gibts Du nicht srcFile frei nachdem Du die Daten an die StringList übergeben hast?


Grüße
Klaus

[Uwe Raabe]

Was bedeutet: "die Gewinnchance um 1 erhöhen"?

Soll jeder eingezahlte Euro von allen Kunden die gleiche Gewinnchance haben?

Dann würde ich erstmal die Gesamtsumme der Euros (G) ermitteln. Dabei musst du nur aufpassen, daß du beim Addieren keinen Integer-Überlauf erzeugst. Aus dieser Gesamtsumme ermittelst du dann eine Gewinnzahl (1..G). Danach durchläufst du die Eingabedatei nochmal, addierst alle Einzahlungen auf bis die Gewinnzahl erreicht bzw. überschritten wird. Der gerade eingelesene Kunde ist dann der Gewinner.

Wenn du mehrere (z.B. 10) Gewinner brauchst, kommt es darauf an, ob ein Kunde mehrmals gewinnen kann. Ist dies der Fall, kannst du gleich 10 Gewinnzahlen ermitteln und sortieren und das in einem Durchlauf erledigen. Andernfalls nimmst du nach jedem Gewinn den Kunden aus der Liste und führst das gesamte Verfahren mit den verbleibenden Kunden nochmal durch.

Das ist in etwa damit vergleichbar, als wenn jeder Kunde für jeden Euro ein Los in die Trommel geworfen hat.

[Dejan Vu]

Zitat von Uwe Raabe:

Dann würde ich erstmal die Gesamtsumme der Euros (G) ermitteln. Dabei musst du nur aufpassen, daß du beim Addieren keinen Integer-Überlauf erzeugst. Aus dieser Gesamtsumme ermittelst du dann eine Gewinnzahl (1..G). Danach durchläufst du die Eingabedatei nochmal, addierst alle Einzahlungen auf bis die Gewinnzahl erreicht bzw. überschritten wird. Der gerade eingelesene Kunde ist dann der Gewinner.

Inwieweit unterscheidet sich das von meiner Lösung (Post #2)?

[Perlsau]

Zitat von Dejan Vu:

Inwieweit unterscheidet sich das von meiner Lösung (Post #2)?

Ist doch offensichtlich: Uwe bittet nicht darum, als Gewinner eingetragen zu werden

[Uwe Raabe]

Zitat von Dejan Vu:

Zitat von Uwe Raabe:

Dann würde ich erstmal die Gesamtsumme der Euros (G) ermitteln. Dabei musst du nur aufpassen, daß du beim Addieren keinen Integer-Überlauf erzeugst. Aus dieser Gesamtsumme ermittelst du dann eine Gewinnzahl (1..G). Danach durchläufst du die Eingabedatei nochmal, addierst alle Einzahlungen auf bis die Gewinnzahl erreicht bzw. überschritten wird. Der gerade eingelesene Kunde ist dann der Gewinner.

Inwieweit unterscheidet sich das von meiner Lösung (Post #2)?

Nur in der Implementierung.

[Bambuti2000]

Wunderbar, danke für die schnellen Antworten.

Besonderen Dank an Dejan Vu.
Wenn man sich das dann mal richtig überlegt, wird es auch klar und simpel.

Ich habe natürlich umgehend die Berechnung umgesetzt.
Das einzige was ich noch nicht so ganz verstehe ist

Zitat:

theWinner := Random (Summe) + 1;

warum +1 addiert wird.

Gruß
Stefan

[Perlsau]

Schau dir doch einfach mal die Online-Hilfe zu Random an:

In Delphi gibt Random eine Zufallszahl im Bereich 0 <= X < Range zurück.

Na, leuchtet's bereits?

Wenn nicht, dann schau dir mal im Debugger die Resultate an, wenn du bei Random als X-Wert z.B. 1 eingibst ... Jetzt sollte es aber deutlich leuchten bei dir ...