![]() ![]() Fortunately, when the weight size changes, it always gets smaller during the search, which means that there is a corresponding decrease in the probability that the search will need to progress further. The algorithm tends to quickly hop over runs of weights with similar size, but it sometimes makes overly conservative hops when the weight size changes. The size of hops is calculated based on the invariant that all weights after the current position are not larger than the current weight. The algorithm works by first sorting the weights in descending order, then hopping along the list to find the selected element. However, it’s possible to do even better by using the following algorithm that I’ve come up with. ![]() 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 low, high = 0, len(weights) while low target_distance: high = mid else: return mid return low return weighted_random Binary Search Demo Hopscotch Selection ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |