Banner per "Zufall" auswählen

[faux]

Hallo!

Ich habe in PHP (eigentlich egal), ein Skript geschrieben, dass aus einer Liste von Banner per Zufall einen auswählt. Weiter nicht schwer. Jetzt will ich jedoch jedem Banner Punkte zwischen 0 und 999 vergeben. Je höher die Punktezahl, desto öfter soll der Banner ausgewählt werden.
Jetzt hätte ich die Möglichkeit, einfach jeden Banner sooft in eine Liste zu tragen, wie er Punkte hat, und dann per Zufall ein Element der Liste ermitteln, jeodoch ist das imho keine wirkliche Lösung und 2. ist das bei mehreren Banners sehr Performance raubend.
Fällt jemanden eine brauchbare Lösung bzw ein Lösungsansatz ein?

Noch was: Ich habe die Bannerdaten samt Punktezahl in einer SQL-Tabelle, falls das weiterhelfen sollte, zu einer Lösung zu gelangen.

Danke für jeden Tipp...
Grüße
Faux

Stelle ich mich nur so dumm an, oder ist das wirklich komplizierter als es auf den ersten Blick erscheint?

[flomei]

Könnte wirklich schwerer sein als es scheint aber ich hab grad folgende, vielleicht nutzlose, Idee gehabt:

Du hast x Banner in deiner Liste.
Aus dieser Liste lässt du dir jetzt zufällig y Banner geben (10 / 20 / 50 ).
Diese Banner sortierst du nach Anzahl der Punkte.
Der mit den meisten Punkten ist oben und wird genommen, dann Punkt abgezogen (Bannertauschprogramm?)

Jo, das wär so meine Idee...

MfG Florian

[faux]

Vom Prinzip her, mal keine Schlechte Idee. Meinst du y ebenfalls als Zufallszahl oder als vorher bestimmte fixe Zahl?
Ist bei diesem Prinzip wirklich sichergestellt, dass der Banner mit der höchsten Punktezahl am öftesten vorkommt?

[flomei]

y könntest du festlegen, macht wahrscheinlich Sinn.
Wenn y sich x annähert, dann erhöht sich auch die Wahrscheinlichkeit das wirklich das Banner mit der größten Punktzahl ausgewählt wird.
Ansonsten wird halt das zufällige Banner mit der größten Punktzahl ausgewählt...

MfG Florian

[faux]

Ja, da hast du eigentlich recht, jedoch ist mir ein Problem aufgefallen: Der Banner mit der kleinsten Punktezahl wird nie aufgerufen.

[flomei]

Stimmt... hm...
Das ist natürlich wirklich nen Problem.

Wäre es nicht schon so spät dann hätte ich vielleicht noch ne Idee aber so ist das vergebens...

MfG Florian

[faux]

Naja, dann kann man nur hoffen, dass dir morgen noch was einfällt..

Auf eine Idee hoffend,
Faux

[alzaimar]

Zufällige Auswahl mit Gewichtung:
Sei B die Liste der Banner, und P die der dazugehörigen Punkte. B[i] (0<=i<n) ist das i.te Banner und P[i] seine Punktzahl.
Dann liefert folgende Funktion einen Index i (0<=i<n), bei dem die Gewichtung P berücksichtigt wird:

Delphi-Quellcode:

Function WeighedIndex (P : Array Of Integer) : Integer;
Var
  I,J,S : Integer;

Begin
  S := 0;
  For i:= Low (P) to High(P) do // Alle Gewichte summieren
    Inc(S,P[i]);
  J := Random (S);              // Zufallszahl wählen
  S := 0;
  For i:= Low (P) to High(P) do begin // In welchem Bereich liegt sie
    Inc(S, P[i]);
    if J < S Then Begin          // Abschnitt gefunden und fertig
      Result := i;
      Exit;
    End;
  End;
End;

Stell Dir die einzelnen Punkte als verschieden lange Rechtecke vor, die Du übereinanderstapelst. Dann wählst Du mit verbundenen Augen irgendeine Stelle von dem Stapel aus. Das Rechteck, das sich dort befindet, ist dein zufällig ausgewählter Kandidat. Je größer ein Recheck ist, desto größer die Wahrscheinlichkeit, das dieses Rechteck getroffen wird. Umgekehrt werden kleine Rechtecke entsprechend seltener getroffen.

Wenn du aber sichergehen willst, das wirklich alle Banner ausgewählt werden, musst Du eine Liste erstellen und diese zufällig permutieren. Anschließend gehst Du die Liste einfach von vorne nach hinten durch.

Die Liste wird einfach so erstellt, das für jeden Banner B[i] mit der Punktezahl P[i] genau P[i] mal der Index I in die Liste geschrieben wird:

Delphi-Quellcode:

  For i:= Low (P) to High(P) do     // Alle Gewichte summieren
    Inc(S,P[i]);
  SetLength (L, S);                 // L wird unsere Liste
  k := 0;
  For i:= Low (P) to High(P) do     // Liste mit Werten füllen
    For j:=0 to P[i]-1 do Begin     // Je höher die Punktzahl dest
      L[k] := i;                    // häufiger der Index
      inc (k);
    End
  End;
// Beispiel: Drei Banner (5,3,1). 
// Die Liste sieht so aus (0,0,0,0,0,1,1,1,2). 
// Diese Liste muss nun noch 'durcheinandergewürfelt' werden, z.B. so:
// Algorithmus nach Fisher-Yates (ja, auch sowas Banales bekommt einen Namen)
  Randomize; // reicht 1x beim Programmstart, hier nur zur Erinnerung
  For i := 0 to S-1 do  begin  
    J := i + random(S-I);  
    K := L[j];  
    L[J] := L[I];  
    L[I] := K;  
  end;

Nun ist die Liste durcheinander, z.B. So (0,0,1,2,1,0,0,1,0). Wenn du nun einfach die Banner entsprechend dieser Liste auswählst, wird das Banner #0 garantiert 5x, das Banner #1 3x und das Banner #2 1x ausgewählt, genauso, wie Du es wolltest, mathematisch korrekt und beweisbar. Falls du mit der Bannerauswahl Geld verdienen willst, hätte o.g. Verfahren (vorausgesetzt, es enthält keine Schusselfehler) auch vor Gericht Bestand.

[edit]Erste Version verbessert [/edit]

[faux]

Hallo!

Danke für die Antwort!
Zur 2. Möglichkeit:
Ja, so habe ich mir das auch schon gedacht, aber das wird in PHP nicht so wirklich realisierbar sein, ohne die ganze Tabelle in einen Array einzulesen - ich weiß leider nicht, ob das dann nicht sehr langsam wird.

Die erste Möglichkeit finde ich schon mal nicht schlecht..
Werds gleich mal testen...

Danke.
Grüße
Faux

NACHTRAG: Eine Frage noch:
Ist es absicht, dass du im 1. Bsp. i als Schleifenvariable UND als Lösungsspeicherung verwendest?

[alzaimar]

Zitat von faux:

NACHTRAG: Eine Frage noch:
Ist es absicht, dass du im 1. Bsp. i als Schleifenvariable UND als Lösungsspeicherung verwendest?

Absicht nicht, nur morgentliche Demenz... Werd ich gleich mal verbessern