allow weights in random.choice

[aisaac]

BPO	18844
Nosy	@tim-one, @rhettinger, @mdickinson, @pitrou, @serhiy-storchaka, @NeilGirdhar, @applio
PRs	[Do Not Merge] Convert Misc/NEWS so that it is managed by towncrier #552
Files	weighted_choice.diff: Preliminary implementation of random.choice optional arg "weights" weighted_choice_v2.diff: Move cumulative distribution calculation to separate function that returns an index generator weighted_choice_generator.patch wcg_bench.py: Benchmarking different methods weighted_choice_generator_2.patch weighted_choice_v3.diff: a new implementation of weighted choice weighted_choice_v3.patch: weighted choice function weighted_choice_v4.patch weighted_choice_v5.patch: weighted choice function v5 weighted_choice.diff weighted_choice2.diff: Add docs and test

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2016-09-07.00:17:01.460>
created_at = <Date 2013-08-26.17:23:45.101>
labels = ['type-feature', 'library']
title = 'allow weights in random.choice'
updated_at = <Date 2017-03-31.16:36:29.131>
user = 'https://bugs.python.org/aisaac'

bugs.python.org fields:

activity = <Date 2017-03-31.16:36:29.131>
actor = 'dstufft'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2016-09-07.00:17:01.460>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2013-08-26.17:23:45.101>
creator = 'aisaac'
dependencies = []
files = ['31479', '31547', '31732', '31734', '36331', '42322', '42323', '42386', '42393', '44394', '44407']
hgrepos = []
issue_num = 18844
keywords = ['patch', 'needs review']
message_count = 69.0
messages = ['196229', '196234', '196235', '196252', '196551', '196567', '196709', '196711', '196716', '196721', '196728', '196731', '196741', '196750', '196761', '196767', '197507', '197512', '197540', '197862', '197865', '197866', '198367', '198372', '223750', '224947', '224949', '224953', '224954', '224957', '225128', '225133', '225137', '225140', '225148', '226891', '262625', '262626', '262642', '262649', '262652', '262656', '262678', '262744', '262967', '262970', '262971', '262981', '262982', '262983', '262994', '262995', '267782', '272767', '272785', '274538', '274677', '274684', '274686', '274760', '274907', '274964', '277485', '277486', '277487', '278516', '278633', '279701', '279702']
nosy_count = 14.0
nosy_names = ['tim.peters', 'rhettinger', 'mark.dickinson', 'pitrou', 'aisaac', 'westley.martinez', 'python-dev', 'serhiy.storchaka', 'NeilGirdhar', 'madison.may', 'dkorchem', 'Christian.Kleineidam', 'davin', 'xksteven']
pr_nums = ['552']
priority = 'normal'
resolution = 'fixed'
stage = 'patch review'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue18844'
versions = ['Python 3.6']

[aisaac]

The need for weighted random choices is so common that it is addressed as a "common task" in the docs:
http://docs.python.org/dev/library/random.html

This enhancement request is to add an optional argument to random.choice, which must be a sequence of non-negative numbers (the weights) having the same length as the main argument.

[MadisonMay]

+1. I've found myself in need of this feature often enough to wonder why it's not part of the stdlib.

[pitrou]

Agreed with the feature request. The itertools dance won't be easy to understand, for many people.

[MadisonMay]

I realize its probably quite early to begin putting a patch together, but here's some preliminary code for anyone interested. It builds off of the "common task" example in the docs and adds in validation for the weights list.

There are a few design decisions I'd like to hash out.
In particular:

• Should negative weights cause a ValueError to be raised, or should they be converted to 0s?
• Should passing a list full of zeros as the weights arg raise a ValueError or be treated as if no weights arg was passed?

[mdickinson]

[Madison May]

• Should negative weights cause a ValueError to be raised, or should they be converted to 0s?
• Should passing a list full of zeros as the weights arg raise a ValueError or be treated as if no weights arg was passed?

Both those seem like clear error conditions to me, though I think it would be fine if the second condition produced a ZeroDivisionError rather than a ValueError.

I'm not 100% sold on the feature request. For one thing, the direct implementation is going to be inefficient for repeated sampling, building the table of cumulative sums each time random.choice is called. A more efficient approach for many use-cases would do the precomputation once, returning some kind of 'distribution' object from which samples can be generated. (Walker's aliasing method is one route for doing this efficiently, though there are others.) I agree that this is a commonly needed and commonly requested operation; I'm just not convinced either that an efficient implementation fits well into the random module, or that it makes sense to add an inefficient implementation.

[MadisonMay]

[Mark Dickinson]

Both those seem like clear error conditions to me, though I think it would be fine if the second condition produced a ZeroDivisionError rather than a ValueError.

Yeah, in hindsight it makes sense that both of those conditions should raise errors. After all: "Explicit is better than implicit".

As far as optimization goes, could we potentially use functools.lru_cache to cache the cumulative distribution produced by the weights argument and optimize repeated sampling?

Without @lru_cache:
>>> timeit.timeit("x = choice(list(range(100)), list(range(100)))", setup="from random import choice", number=100000)
36.7109281539997

With @lru_cache(max=128):
>>> timeit.timeit("x = choice(list(range(100)), list(range(100)))", setup="from random import choice", number=100000)
6.6788657720007905

Of course it's a contrived example, but you get the idea.

Walker's aliasing method looks intriguing. I'll have to give it a closer look.

I agree that an efficient implementation would be preferable but would feel out of place in random because of the return type. I still believe a relatively inefficient addition to random.choice would be valuable, though.

[rhettinger]

+1 for the overall idea. I'll take a detailed look at the patch when I get a chance.

[rhettinger]

The sticking point is going to be that we don't want to recompute the cumulative weights for every call to weighted_choice.

So there should probably be two functions:

  cw = make_cumulate_weights(weight_list) 
  x = choice(choice_list, cw)

This is similar to what was done with string.maketrans() and str.translate().

[serhiy-storchaka]

A more efficient approach for many use-cases would do the precomputation once, returning some kind of 'distribution' object from which samples can be generated.

I like the idea about adding a family of distribution generators. They should check input parameters and make a precomputation and then generate infinite sequence of specially distributed random numbers.

[MadisonMay]

[Raymond Hettinger]

The sticking point is going to be that we don't want to recompute the
cumulative weights for every call to weighted_choice.

So there should probably be two functions:

cw = make_cumulate_weights(weight_list)
x = choice(choice_list, cw)

That's pretty much how I broke things up when I decided to test out optimization with lru_cache. That version of the patch is now attached.

[Serhiy Storchaka]

I like the idea about adding a family of distribution generators.
They should check input parameters and make a precomputation and then > generate infinite sequence of specially distributed random numbers.

Would these distribution generators be implemented internally (see attached patch) or publicly exposed?

[serhiy-storchaka]

Would these distribution generators be implemented internally (see attached patch) or publicly exposed?

See bpo-18900. Even if this proposition will be rejected I think we should publicly expose weighted choice_generator(). A generator or a builder which returns function are only ways how efficiently implement this feature. Use lru_cache isn't good because several choice generators can be used in a program and because it left large data in a cache long time after it was used.

[MadisonMay]

Use lru_cache isn't good because several choice generators can be used in a program and because it left large data in a cache long time after it was used.

Yeah, I just did a quick search of the stdlib and only found one instance of lru_cache in use -- another sign that lru_cache is a bad choice.