Zufallsauswahl, gewichtet mit den letzten vorherigen Auswahlen

Question

Ich möchte ein Element aus einer Liste auswählen, in der jedes Element nach der letzten Auswahl gewichtet ist.

Ich könnte eine LRU-Liste (least recently used) mit der Gewichtung einer Funktion basierend auf der Position in der Warteschlange machen, die elegant wäre mit Ausnahme der Tatsache, dass zunächst alle Elemente gleichmäßig gewichtet werden sollten.

Das Subtrahieren oder Teilen des Gewichts um einen bestimmten Betrag nach der Auswahl scheint nicht intuitiv richtig zu sein. Gibt es einen besseren Weg, vielleicht ein mathematisches Konzept wie Logarithmen oder Inversen? (Nicht meine Stärke)

Answer 1

Wie wäre es damit so etwas wie:

Lassen n = Anzahl der Elemente, list = Anordnung von Elementen, watermark: = 0.

r := random() 
i := floor(r * n) 

if i >= watermark : 
    index := i 
    watermark := watermark + 1 // weighted part grows 
else : 
    index := floor(weight(r * n/watermark) * watermark) 
endif 

move list[index] to list[0]  // shifting elements list[0..index-1] up one place 
result := list[0] 

Hier Wir teilen die Liste in zwei Teile, gewichtet und einheitlich, wobei die Grenze von watermark verfolgt wird. Anfangs ist der gewichtete Teil leer, aber allmählich wächst er und verbraucht am Ende die gesamte Liste.

random() ist eine Funktion, die eine Zufallszahl in [0.0, 1.0] zurückgibt.

weight(x) ist eine Funktion von [0.0, 1.0) in [0.0, 1.0], die das erforderliche Gewichtungsverhalten definiert.

Das "r * n/watermark" als Argument von weight() dient zur Normalisierung des Argumentbereichs. Vielleicht ist diese Normalisierung für einige Auswahlmöglichkeiten der Gewichtungsfunktion nicht erforderlich.