Add binary search based weighted choice
ccssmnn opened this issue · 0 comments
ccssmnn commented
GA and ACO use the weightedChoice method. Currently it uses a linear search strategy with O(N) performance. However a binary search with O(log(N)) could be used whenever multiple selections from the same weights are made.
I found a python implementation here
def prepare_binary_search(weights):
# Computing the running totals takes O(N) time
running_totals = list(itertools.accumulate(weights))
def weighted_random():
target_distance = random()*running_totals[-1]
low, high = 0, len(weights)
while low < high:
mid = int((low + high) / 2)
distance = running_totals[mid]
if distance < target_distance:
low = mid + 1
elif distance > target_distance:
high = mid
else:
return mid
return low
return weighted_random