Взвешенный элементный алгоритм

Question

Я хотел бы узнать, как выбрать взвешенные элементы. Например: я хочу получать вопросы из пула, но если кто-то не может дать правильный ответ на вопрос, это заставляет этот вопрос удвоить свой вес и увеличить вероятность повторного выбора позже.

Answer 1

Имейте класс, который сохраняет элемент: весовые пары (key = item: value = weight) в хеш-таблице.

Класс должен также содержать переменную total_weight, которая является суммой всех весов в хеш-таблице. Методы класса до add_item, remove_item и для элемента должны содержать обновленный total_weight. Это позволяет избежать пересчета суммы за каждый выбор.

Чтобы выбрать пункт: Используйте случайное число, такое как 1<=random_number<=total_weight. Перейдите по элементу: весовые пары в хеш-таблице, суммируя весы до случайного числа < = эта текущая сумма. Когда это произойдет, ключом пары, в которой вы находитесь, является выбранный элемент.

Это похоже на прокрутку воображаемой матрицы, размер которой является суммой всех весов. Для каждого рулона каждый элемент имеет свой собственный диапазон чисел на матрице, причем размер каждого диапазона равен весу его предмета. Если результат свертки попадает в диапазон предмета, этот элемент является выбранным.

Редактирование для добавления следующего образца кода после запроса в комментарии ниже. Испытано это с Python 2.5.2:

from random import randint # Import randint function from random module. 

class WeightedCollection(object): 
    def __init__(self): 
     self.total_weight = 0 
     self.items = {} # This is a python dictionary == a hash table 
    def add_item(self, item, weight): 
     self.items[item] = weight 
     self.total_weight += weight 
    def remove_item(self, item): 
     self.total_weight -= self.items[item] # Subtracts the weight. 
     del(self.items[item]) 
    def update_weight(self, item, new_weight): 
     self.total_weight += (new_weight - self.items[item]) 
     self.items[item] = new_weight 
    def get_random_item(self): 
     ''' Returns random selection but weighted by item weights. ''' 
     # Result of call below is 1 <= random_number <= self.total_weight... 
     random_number = randint(1, self.total_weight) 
     sum_so_far = 0 
     # For every item and its weight... 
     for item, weight in self.items.iteritems(): 
      sum_so_far += weight 
      if random_number <= sum_so_far: 
       return item 

# Usage demo... 

questions = WeightedCollection() 

questions.add_item('What is your name?', 1) 
questions.add_item('What is your favorite color?', 50) 
questions.add_item('What is the meaning to life?', 100) 

print 'Here is what the dictionary looks like:' 
print questions.items 
print '' 
print "Total weight:", questions.total_weight 
print '' 
print 'Some sample random picks...' 
for i in range(5): 
    print questions.get_random_item() 

А вот выход:

Here is what the dictionary looks like: 
{'What is the meaning to life?': 100, 'What is your name?': 1, 'What is your favorite color?': 50} 

Total weight: 151 

Some sample random picks... 
What is your favorite color? 
What is the meaning to life? 
What is the meaning to life? 
What is your favorite color? 
What is the meaning to life? 

Answer 2

Охватывайте массив элементов-кандидатов. Если один элемент имеет вес 2, поместите его в массив дважды, как правило, если у вас есть вес n, введите его там n раз. Затем выберите случайный элемент из массива. Та-дааа.

Answer 3

Посмотрите на это this (прокрутите вниз для кода).

EDIT для критики :)

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

EDIT2:

после знакомства Тодда Оуэна об использовании самобалансирующихся дерев. Дерево, очевидно, не должно быть создано заново при каждом изменении веса. Эта часть просто не включена в реализацию, которую я связал, и ее необходимо добавить, если ваши веса сильно меняются.

Answer 4

Мне нравится идея Андре Хоффмана использовать двоичное дерево, в котором каждый листовой узел соответствует вопросу, а каждый промежуточный узел хранит сумму веса своих дочерних узлов. Но он говорит, что дерево нужно воссоздавать каждый раз, когда вес меняется.

Собственно, этого не может быть! Когда вы изменяете вес данного листа, вам нужно только обновить веса этих узлов между ним и корнем дерева. Но ... вам также нужен способ найти узел в дереве, если вы хотите его изменить.

Так что я предлагаю использовать самобалансирующееся двоичное дерево (например, дерево красного дерева, дерево AVL и т. Д.), Которое упорядочивается идентификатором вопроса. Операции над деревом должны поддерживать свойство, что вес любого узла равен сумме весов его детей.

С этой структурой данных вес корневого узла W равен сумме весов всех вопросов. Вы можете получить вопрос либо по ID вопроса, либо случайным весом (от нуля до W). Эта операция, а также вставки, удаления или обновление веса вопроса - все O (log n).