가중치 적용 항목 알고리즘

Question

가중치 적용 항목을 선택하는 방법을 배우고 싶습니다. 예를 들면 : 수영장에서 질문을 가져오고 싶지만 질문에 정답을 줄 수없는 사람이 있으면 그 질문은 무게를 두 배로하고 나중에 다시 선택 될 확률을 높입니다.

Answer 1

해시 테이블에서 가중치 쌍 (키 = 항목 : 값 = 가중치)을 유지하는 클래스가 있습니다.

또한 클래스는 해시 테이블의 모든 가중치의 합인 total_weight 변수를 유지해야합니다. 항목의 add_item, remove_item 및 에 대한 클래스의 메소드는 total_weight를 업데이트 된 상태로 유지해야합니다. 이렇게하면 모든 선택에 대해 총계를 다시 계산하지 않아도됩니다.

항목을 선택하려면 1<=random_number<=total_weight과 같은 임의의 숫자를 사용하십시오. 항목을 반복합니다. 해시 테이블의 가중치 쌍. 난수가 < = 누적 합계가 될 때까지 가중치를 합산합니다. 그러면 상대방의 키가 선택한 항목이됩니다.

크기가 모든 무게의 합계 인 가상의 다이를 굴리는 것과 같습니다. 모든 목록마다 각 항목의 다이의 숫자 범위가 각 범위의 항목 크기와 동일합니다. 롤 결과가 항목 범위 내에 있으면 해당 항목이 선택된 항목입니다.

아래 주석에 다음 샘플 코드를 추가하여 편집하십시오.

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() 

을 그리고 여기 출력은 다음과 같습니다 :이 파이썬 2.5.2로 테스트

당신이 최대로 선택할 수 있습니다 대략 몇 질문

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 번 입력하십시오. 그런 다음 배열에서 임의의 요소를 선택하십시오. Ta-daaa.

Answer 3

this (코드 아래로 스크롤)을 살펴보십시오. 비평가에 대한

편집 :

내가 어떻게 사실을 달성하기 위해 배열의 요소 저장하지 질량을 무게 작동하지 이진 트리 접근 방법을 구현하는 프로그램을 연결이 스레드의 코드 가중 확률. 다시, 체중이 바뀔 때마다 이진 트리를 다시 만들어야하기 때문에 가중치가 자주 변경 될 때도 꽤 비효율적입니다.

EDIT2 :

자기 균형 나무를 사용하는 방법에 대한 참조 토드 오웬의 게시물

. 나무는 분명히 체중이 바뀔 때마다 이 아니라이 다시 만들어 져야합니다. 이 부분은 링크 된 구현에 포함되지 않았으며 가중치가 많이 변경되는 경우 추가해야합니다.

Answer 4

@ André Hoffmann의 이진 트리 사용 아이디어는 모든 리프 노드가 질문에 해당하며 모든 중간 노드는 하위 노드의 가중치 합을 저장합니다. 그러나 그는 체중이 바뀔 때마다 나무를 다시 만들어야한다고 말했습니다.

사실,이 경우 일 필요는 없습니다! 주어진 리프의 가중치를 변경하면 트리의 루트와 루트 사이의 노드의 가중치 만 업데이트하면됩니다. 그러나 ... 수정하려는 경우 트리 내의 노드를 찾는 방법이 필요합니다.

내 제안은 질문 ID로 정렬 된 자체 균형 트리 (예 : 빨강 검정 나무, AVL 트리 등)를 사용하는 것입니다. 트리에 대한 작업은 노드의 가중치가 해당 노드의 가중치의 합과 같은 속성을 유지해야합니다.

이 데이터 구조에서 루트 노드의 가중치 W은 모든 질문의 가중치 합계와 같습니다. 질문 ID 또는 임의의 가중치 (0과 W 사이)로 질문을 검색 할 수 있습니다. 이 작업은 질문의 삽입, 삭제 또는 가중치 업데이트와 마찬가지로 모두 O (로그 n)입니다.