Wählen Sie eine zufällige Zeile, aber mit Quoten

Question

Ich habe einen Datensatz mit Zeilen, die jeweils eine "Quoten"-Zahl zwischen 1 und 100 enthalten. Ich möchte dies auf möglichst effiziente Weise tun. Die Quoten addieren sich nicht unbedingt zu 100.

Ich habe ein paar Ideen gehabt.

a) Wählen Sie den gesamten Datensatz aus, addieren Sie dann alle Quoten und erzeugen Sie eine Zufallszahl zwischen 1 und dieser Zahl. Ziehen Sie dann in einer Schleife die Quoten von der Zahl ab, bis sie 0 ist.

Ich wollte die Auswirkungen auf die Datenbank so gering wie möglich halten und habe daher überlegt, ob ich nur die Zeilen auswählen sollte, die ich benötige.

b)

SELECT * FROM table WHERE (100*RAND()) < odds

Ich habe überlegt LIMIT 0,1

Aber wenn die Elemente die gleiche Wahrscheinlichkeit haben, wird nur eines von ihnen zurückgegeben

Alternativ kann man den gesamten Datensatz nehmen und einen Zufallswert daraus auswählen... aber dann werden die Quoten beeinflusst, da es ein Zufallswert mit Quoten und dann ein Zufallswert ohne Quoten wird, so dass die Quoten zugunsten der höheren Quoten geneigt werden (sogar noch mehr).

Ich denke, ich könnte order by odds ASC nimmt dann den gesamten Datensatz und wählt dann mit PHP eine zufällige Zeile mit der gleichen Quote wie der erste Datensatz (die niedrigste) aus.

Das scheint mir eine ungeschickte Lösung zu sein.

Hat jemand eine bessere Lösung? Wenn nicht, welche der oben genannten Lösungen ist die beste?

Answer 1

Hm. Mir ist nicht ganz klar, welches Ergebnis Sie wollen, also haben Sie Verständnis, wenn das ein bisschen verrückt ist. Davon abgesehen, wie wäre es mit:

Erstellen Sie eine neue Tabelle. Die Tabelle ist eine Tabelle mit festen Daten und sieht wie folgt aus:

Odds
====
   1
   2
   2
   3
   3
   3
   4
   4
   4
   4
etc, 
etc.

Verknüpfen Sie dann Ihren Datensatz mit dieser Tabelle über die Quotenspalte. Sie erhalten für jede Zeile in Ihrer Tabelle so viele Zeilen zurück, wie Quoten für diese Zeile angegeben sind.

Wählen Sie dann einfach eine dieser Gruppen nach dem Zufallsprinzip aus.

Answer 2

Eine allgemeine Lösung, die für O(log(n))-Updates geeignet ist, sieht in etwa so aus:

• Objekte als Blätter eines (ausgewogenen) Baumes speichern.
• Speichern Sie an jedem Verzweigungsknoten die Gewichte aller darunter liegenden Objekte.
• Beim Hinzufügen, Entfernen oder Ändern von Knoten werden die Gewichte der übergeordneten Knoten aktualisiert.

Wähle dann eine Zahl zwischen 0 und (Gesamtgewicht - 1) und navigiere den Baum hinunter, bis du das richtige Objekt gefunden hast.

Da Sie sich nicht um die Reihenfolge der Dinge im Baum kümmern, können Sie sie als ein Array von N Zeigern und N-1 Zahlen speichern.