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 :stupid:

[gammatester]

Zitat:

Zitat von Bambuti2000 (Beitrag 1262675)

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:

Zitat von Uwe Raabe (Beitrag 1262681)

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:

Zitat von Dejan Vu (Beitrag 1262682)

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

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

[Uwe Raabe]

Zitat:

Zitat von Dejan Vu (Beitrag 1262682)

Zitat:

Zitat von Uwe Raabe (Beitrag 1262681)

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. :wink:
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? :stupid:

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 ...

[Jumpy]

Wenn du Random(10) sagst, können die Zahlen 0..9 rauskommen.

[Perlsau]

Zitat:

Zitat von Jumpy (Beitrag 1262706)

Wenn du Random(10) sagst, können die Zahlen 0..9 rauskommen.

Falsch! Da kommen die Zahlen 0..10 heraus, wie ich oben bereits dargestellt habe. Es ist eher so: wenn du Werte von 1 bis 10 haben willst, nimmst du Random(9) und zählst 1 dazu.

[Uwe Raabe]

Zitat:

Zitat von Perlsau (Beitrag 1262708)

Zitat:

Zitat von Jumpy (Beitrag 1262706)

Wenn du Random(10) sagst, können die Zahlen 0..9 rauskommen.

Falsch! Da kommen die Zahlen 0..10 heraus, wie ich oben bereits dargestellt habe. Es ist eher so: wenn du Werte von 1 bis 10 haben willst, nimmst du Random(9) und zählst 1 dazu.

Perlsau - Sie reden wirr!

[himitsu]

Zitat:

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

Das klingt ja fast so, als wenn du da irgendwo z.B. einen Integerüberlauf bekommst, wenn es bei großen Zahlen nicht mehr geht. :gruebel:
[edit] Oder eben ein Speicherproblem: Arbeitspeicher ist voller Strings und auch die StringList selbst besitzt eine maximale Anzahl an möglichen Einträgen, und zwar sind das ganz genau

Delphi-Quellcode:

Max(NativeInt) div (SizeOf(Pointer) * 2)

in Win32 sind das maximal 268.435.455 Einträge, wobei es effektiv (auf Grund des Arbeitsspeichers) vielleicht nur maximal 32.768.000 Zeilen sind (eher weniger, da ich davon ausgegangen bin, daß ein freier 250MB-Bereich zusammenhängend existiert und jede Zeile einen Leerstring enthält :stupid:).



Habt ihr über 2 Milliarden € (2.147.483.647) als Gesamt-Einlagen?

Wenn nicht, dann sollte es keinen Überlauf geben.
OK, wenn man die Extremwerte nimmt, dann schon (150000*1000000 = 150.000.000.000), aber in der durchschnittlichen Summe doch wohl nicht.

Annahme: pro 1€ gibt es eine Gewinnchance
- Maximum Bereich des Zufallswertes errechnen = Einlagen aller Leute (eventuell jeweils auf ganze € abgerundet)
- Zufallswert bestimmen = Random(Gesamteinlage)
- dann wieder die Kunden durchgehen und solange von dem Zusfallswert die jeweilige Einlage abziehen, bis der Wert unter 0 sinkt ... das ist dann der Gewinner.

[edit]
Also im Prinzip so, wie es schon genannt wurde.

Vom Vorgehen her ist es wie dein Code, nur das die "Liste" nicht in Real, sondern nur virtuell erstellt wird und es somit nahezu keinen Speicherverbrauch gibt.
Denn, wenn man diese Liste nicht auch noch vermischt, dann lässt sich mathematisch berechnen welche Person sich in jeder Zeile befindet.

[Perlsau]

Zitat:

Zitat von Uwe Raabe (Beitrag 1262711)

Perlsau - Sie reden wirr!

In der Tat! Und zwar äußerst :stupid:

[Bambuti2000]

Also,

nochmals vielen Dank für eure Beiträge.
Die +1 im Random hab ich jetzt auch verstanden.

Ich denke so können wir demnächst bestimmt ein paar iPads an unsere Kunden verlosen.

@himitsu
Du liegst mit all deinen Vermutungen richtig (bis auf die Gesamt-Einlagen).
Und somit hab ich es auch nach Dejan Vu's Erläuterung umgesetzt.

Danke nochmals. :thumb:

[himitsu]

Ich wollte schon fragen, ob wir jetzt auch einen Dankeschön-Einlageneuro gesponsort bekommen, aber dann müssen wir uns auch noch 'nen Mac kaufen, weil sich das iPad ohne ja nicht nutzen lässt (für die Entwicklung), also dann besser doch nicht. :stupid:

Wobei: Ist das so eigentlich "gerecht"?
Gut, wer mehr bezahlt, hat höhere Chancen, aber sind das dann nicht die Reichen, welche eh schon 5 iPads als eBookreader auf'm Klo liegen haben?

[Jumpy]

Wo du doch von Klo redest, so ist es doch eine bekannte Tatsache das Sch... auf den dicksten Haufen fällt. :-D

[Dejan Vu]

Zitat:

Zitat von Uwe Raabe (Beitrag 1262688)

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

Nur in der Implementierung.[/QUOTE] Lass ich gelten, obwohl 'Addieren bis Erreichen oder Überschreiten der Zahl' äquivalent mit 'abziehen, solange das Ergebnis >=0' ist. Meine Version benötigt eine Variable weniger, was wirklich extrem wichtig ist. ;-)