[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Tim Chase wrote: > On 2014-02-16 04:12, Terry Reedy wrote: >> On 2/15/2014 11:41 PM, Tim Chase wrote: >> > data = ( >> > ("apple", 20), >> > ("orange", 50), >> > ("grape", 30), >> > ) > > To Ben, yes, this was just some sample data; the original gets built > from an external (i.e., client-supplied, thus the need to gracefully > support crazy-large numbers) data source and is indeed actually a list > rather than a tuple. When entering static data like this, I often > default to an outer tuple (rather than list) just as a hint/reminder > to myself that I don't expect this to change at runtime (and have > Python yell at me if I accidentally try). > >> If you actually start with date in this form, write the few lines >> needed to produce the form below. >> >> import bisect >> import random >> >> data = [ >> (0, 'apple'), >> (20, 'orange'), >> (70, 'grape'), >> ] >> >> for i in range(10): >> r = random.randrange(0, 100) >> i = bisect.bisect(data, (r, 'zzzzz')) - 1 >> print(data[i][1]) > > Trying to read what may be implicit assumptions in your code: > > 1) your code calculates "100" as sum(item[0] for item in data) > > 2) the data has to be sorted for bisect to work > > 3) you meant to write "(10, 'apple')" rather than 0. With my original > example code, a 0-probability shouldn't ever show up in the sampling, > where it looks like it might when using this sample code. In my > particular use case, I can limit/ensure that 0-probability items never > appear in the list, filtering them upon loading. > > 4) that "zzzzzz" is some arbitrary value that should come after any > string that could appear in the data; perhaps using some custom > "InfinityString" class where everything compared to it is always less > than it. > > So it would be > > class InfinityString: > def __gt__(self, other): True > __ge__ = __gt__ > def __lt__(self, other): False > __eq__ = __le__ = __ne__ = __lt__ > infinity_string = InfinityString() > data = load_data() # list of (quantity, value) tuples > data.sort() > total = sum(qty for qty, value in data) > for i in range(num_to_sample): > r = random.randrange(0, total) > i = bisect.bisect(data, (r, infinity_string)) - 1 > use(data[i][1]) > > Some long-running testing on this code seems to show that if two > items have the same probability, bisect only appears to find the last > one. Tested with > > data = [ > (10, "apple"), > (20, "banana"), # I never get any bananas, even after thousands of > iterations (20, "grape"), > (50, "orange"), > ] I think it becomes simpler if you make an intermediate list with the cumulated probabilities. You can then avoid the InfinityString gymnastics: import random, bisect def cumulated(probs): sigma = 0 cumprobs = [] for p in probs: sigma += p cumprobs.append(sigma) return cumprobs def pick(cumprobs): return bisect.bisect(cumprobs, random.randrange(cumprobs[-1])) data = [ (10, "apple"), (20, "banana"), (20, "grape"), (50, "orange"), ] cumprobs = cumulated(p for p, k in data) # check for off-by-one bugs bins = [0] * len(cumprobs) for i in range(cumprobs[-1]): bins[bisect.bisect(cumprobs, i)] += 1 assert bins == [p for p, k in data] # use it bins = [0] * len(cumprobs) for i in range(10000): bins[pick(cumprobs)] += 1 for item, bin in zip(data, bins): print("{} --> {}".format(item, bin))

- Prev by Date:
**random.sample with large weighted sample-sets?** - Next by Date:
**How to answer questions from newbies** - Previous by thread:
**random.sample with large weighted sample-sets?** - Next by thread:
**random.sample with large weighted sample-sets?** - Index(es):