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

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

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

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


random selection weighting lru
person hippietrail    schedule 15.12.2010    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

Пусть 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() служит для нормализации диапазона аргументов. Возможно, эта нормализация не нужна для некоторых вариантов весовой функции.

person atzz    schedule 15.12.2010
comment
atzz Я собираюсь попробовать ваш алгоритм и посмотреть, как он себя ведет, спасибо! - person hippietrail; 15.12.2010
comment
@hippietrail - Добро пожаловать! подскажите как это сделать, мне тоже интересно :) - person atzz; 15.12.2010
comment
одна вещь, о которой я беспокоюсь, это то, что, если список станет огромным, я могу использовать много ресурсов ЦП, пересчитывая точки останова после каждого выбора, тогда как со строгим LRU и весом как функцией позиции в очереди эти точки останова никогда не изменятся. . - person hippietrail; 15.12.2010
comment
@hippietrail - я думаю, что самая сложная операция здесь - это модификация списка, которая составляет O (n). Но ведь нужно же и поддерживать простой LRU? Водяной знак — это всего лишь одно простое целое число, оно ни на что не должно влиять. - person atzz; 16.12.2010