Wie wählt man eine Zeile nach dem Zufallsprinzip unter Berücksichtigung einer Gewichtung aus?

Question

Ich habe eine Tabelle, die so aussieht:

id: primary key
content: varchar
weight: int

Ich möchte eine Zeile aus dieser Tabelle nach dem Zufallsprinzip auswählen, jedoch unter Berücksichtigung des Gewichts. Zum Beispiel, wenn ich 3 Zeilen habe:

id, content, weight
1, "some content", 60
2, "other content", 40
3, "something", 100

Die erste Reihe hat eine Wahrscheinlichkeit von 30 %, die zweite Reihe eine Wahrscheinlichkeit von 20 % und die dritte Reihe eine Wahrscheinlichkeit von 50 %, ausgewählt zu werden.

Gibt es eine Möglichkeit, dies zu tun? Wenn ich 2 oder 3 Abfragen ausführen muss, ist das kein Problem.

Answer 1

Ich denke, am einfachsten ist es, die gewichtete Reservoirstichprobe zu verwenden:

SELECT
  id,
  -LOG(RAND()) / weight AS priority
FROM
  your_table
ORDER BY priority
LIMIT 1;

Es ist eine großartige Methode, mit der Sie M aus N Elementen auswählen können, wobei die Wahrscheinlichkeit, dass jedes Element ausgewählt wird, proportional zu seinem Gewicht ist. Sie funktioniert genauso gut, wenn man nur ein Element haben möchte. Die Methode wird beschrieben in dieser Artikel . Man beachte, dass sie die größten Werte von POW(RAND(), 1/Gewicht) wählen, was der Wahl der kleinsten Werte von -LOG(RAND()) / Gewicht entspricht.

Answer 2

Dies funktioniert in MSSQL und ich bin sicher, dass es möglich sein sollte, ein paar Schlüsselwörter zu ändern, damit es auch in MySQL funktioniert (vielleicht sogar noch besser):

SELECT      TOP 1 t.*
FROM        @Table t
INNER JOIN (SELECT      t.id, sum(tt.weight) AS cum_weight
            FROM        @Table t
            INNER JOIN  @Table tt ON  tt.id <= t.id
            GROUP BY    t.id) tc
        ON  tc.id = t.id,
           (SELECT  SUM(weight) AS total_weight FROM @Table) tt,
           (SELECT  RAND() AS rnd) r
WHERE       r.rnd * tt.total_weight <= tc.cum_weight
ORDER BY    t.id ASC

Die Idee ist, eine kumulative Gewichtung für jede Zeile zu haben (subselect-1) und dann die Position des übergreifenden RAND() in diesem kumulativen Bereich zu finden.

Answer 3

Ich habe die Lösung von Van ausprobiert, und obwohl sie funktioniert, geht es nicht schnell.

Meine Lösung

Ich löse dieses Problem, indem ich eine separate, verknüpfte Tabelle für die Gewichtung verwalte. Die Grundstruktur der Tabelle ist ähnlich wie diese:

CREATE TABLE `table1` (
  `id` int(11) UNSIGNED AUTO_INCREMENT PRIMARY KEY,
  `name` varchar(100),
  `weight` tinyint(4) NOT NULL DEFAULT '1',
);

CREATE TABLE `table1_weight` (
  `id` bigint(20) UNSIGNED AUTO_INCREMENT PRIMARY KEY,
  `table1_id` int(11) NOT NULL
);

Wenn ich einen Datensatz in table1 mit einer Gewichtung von 3, dann erstelle ich 3 Datensätze in table1_weight , verknüpft mit table1 über die table1_id Feld. Was auch immer der Wert von weight ist in table1 , so viele verknüpfte Datensätze erstelle ich in table1_weight .

Prüfung

Bei einem Datensatz mit 976 Datensätzen in table1 mit einem Gesamtgewicht von 2031 und somit 2031 Einträgen in table1_weight habe ich die folgenden zwei SQLs ausgeführt:

1. Eine Version von Van's Lösung

   SELECT t.*
   FROM table1 t
   INNER JOIN
     ( SELECT t.id,
          SUM(tt.weight) AS cum_weight
      FROM table1 t
      INNER JOIN table1 tt ON tt.id <= t.id
      GROUP BY t.id) tc ON tc.id = t.id,
     ( SELECT SUM(weight) AS total_weight
      FROM table1) tt,
     ( SELECT RAND() AS rnd) r
   WHERE r.rnd * tt.total_weight <= tc.cum_weight
   ORDER BY t.id ASC
   LIMIT 1

2. Verknüpfung mit einer sekundären Tabelle für die Gewichtung

   SELECT t.* FROM table1 t INNER JOIN table1_weight w ON w.table1_id = t.id ORDER BY RAND() LIMIT 1

SQL 1 benötigt durchweg 0,4 Sekunden.

SQL 2 dauert zwischen 0,01 und 0,02 Sekunden.

Schlussfolgerung

Wenn die Geschwindigkeit der Auswahl eines zufälligen, gewichteten Datensatzes keine Rolle spielt, dann ist das von van vorgeschlagene SQL für eine einzige Tabelle in Ordnung und hat nicht den Overhead der Pflege einer separaten Tabelle.

Wenn, wie in meinem Fall, eine kurze Auswahlzeit entscheidend ist, dann würde ich die Methode mit zwei Tabellen empfehlen.

Answer 4

Ein einfacher Ansatz (ohne Joins oder Unterabfragen) besteht darin, das Gewicht mit einer Zufallszahl zwischen 0 und 1 zu multiplizieren, um ein temporäres Gewicht für die Sortierung zu erhalten:

SELECT t.*, RAND() * t.weight AS w 
FROM table t 
ORDER BY w DESC
LIMIT 1

Um dies zu verstehen, bedenken Sie, dass RAND() * 2x wird ein größerer Wert sein als RAND() * x etwa zwei Drittel der Zeit. Folglich sollte jede Zeile im Laufe der Zeit mit einer Häufigkeit ausgewählt werden, die proportional zu ihrem relativen Gewicht ist (z. B. wird eine Zeile mit dem Gewicht 100 etwa 100 Mal häufiger ausgewählt als eine Zeile mit dem Gewicht 1 usw.).

Aktualisierung: Diese Methode führt nicht zu den richtigen Verteilungen also vorerst Verwenden Sie es nicht! (siehe die Kommentare unten). Ich denke, es sollte immer noch eine einfache Methode ähnlich der obigen geben, die funktionieren wird, aber im Moment ist die komplexere Methode unten, die Joins beinhaltet, vielleicht besser. Ich lasse diese Antwort offen, weil: (a) es eine relevante Diskussion in den Kommentaren unten gibt, und (b) ich bei Gelegenheit versuchen werde, sie zu korrigieren.

Answer 5

Das hier scheint zu funktionieren, aber ich bin mir nicht sicher, wie es rechnerisch zu verstehen ist.

SELECT RAND() / t.weight AS w, t.* 
FROM table t 
WHERE t.weight > 0
ORDER BY 1
LIMIT 1

Ich vermute, der Grund dafür ist, dass die aufsteigende Reihenfolge nach den kleinsten Ergebnissen sucht und durch die Division durch das Gewicht bei höheren Gewichten das zufällige Ergebnis dichter in der Nähe von Null geclustert wird.

Ich habe ihn (eigentlich den gleichen Algorithmus in Postgresql) mit 209000 Abfragen über 3000 Zeilen getestet und die Gewichtsdarstellung war korrekt.

meine Eingabedaten:

select count(*),weight from t group by weight
 count | weight 
-------+--------
  1000 |     99
  1000 |     10
  1000 |    100
(3 rows)

meine Ergebnisse:

jasen=# with g as ( select generate_series(1,209000) as i )
,r as (select (  select t.weight as w 
    FROM  t 
    WHERE t.weight > 0
    ORDER BY ( random() / t.weight ) + (g.i*0)  LIMIT 1 ) from g)

select r.w, count(*), r.w*1000 as expect from r group by r.w;

  w  | count | expect 
-----+-------+--------
  99 | 98978 |  99000
  10 | 10070 |  10000
 100 | 99952 | 100000
(3 rows)

En +(g.i*0) hat keine Auswirkung auf das arithmetische Ergebnis, aber eine externe Referenz ist erforderlich, um den Planer zu zwingen, die Unterauswahl für jede der 209K Eingabezeilen, die in in erzeugt werden, neu zu bewerten. g