Случайный выбор, взвешенный против недавних предыдущих выборов

Question

Я бы хотел выбрать элемент списка, в котором вес каждого элемента равен времени, с которого он был выбран в последний раз.

Я мог бы создать список LRU (наименее использованный в последнее время) с функцией взвешивания на основе позиции в очереди, что было бы элегантно, за исключением того факта, что первоначально все элементы должны быть одинаково взвешены.

Простое вычитание или деление веса на определенную величину после его выбора не кажется интуитивно правильным. Есть ли лучший способ, возможно, с использованием математической концепции, такой как логарифмы или инверсии? (не моя сильная сторона)

Answer 1

Как насчет этого:

Пусть n = количество элементов , list = массив элементов , 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]

Здесь мы делим список на две части, взвешенные и однородные, с границей, отслеживаемой watermark. Первоначально взвешенная часть пуста, но постепенно она увеличивается, в конце концов занимая весь список.

random() - это функция, которая возвращает случайное число в [0.0, 1.0).

weight(x) - это функция из [0.0, 1.0) в [0.0, 1.0), которая определяет требуемое поведение при взвешивании.

"r * n / watermark" в качестве аргумента weight() служит для нормализации диапазона аргументов. Возможно, эта нормализация не нужна для некоторых вариантов весовой функции.