classification
Title: allow weights in random.choice
Type: enhancement Stage: patch review
Components: Library (Lib) Versions: Python 3.6
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: Christian.Kleineidam, aisaac, davin, dkorchem, madison.may, mark.dickinson, neil.g, pitrou, python-dev, rhettinger, serhiy.storchaka, tim.peters, westley.martinez, xksteven
Priority: normal Keywords: needs review, patch

Created on 2013-08-26 17:23 by aisaac, last changed 2016-10-30 00:43 by python-dev. This issue is now closed.

Files
File name Uploaded Description Edit
weighted_choice.diff madison.may, 2013-08-26 23:25 Preliminary implementation of random.choice optional arg "weights" review
weighted_choice_v2.diff madison.may, 2013-09-01 14:47 Move cumulative distribution calculation to separate function that returns an index generator review
weighted_choice_generator.patch serhiy.storchaka, 2013-09-11 22:29 review
wcg_bench.py serhiy.storchaka, 2013-09-12 20:32 Benchmarking different methods
weighted_choice_generator_2.patch serhiy.storchaka, 2014-08-10 08:48 review
weighted_choice_v3.diff xksteven, 2016-03-29 20:39 a new implementation of weighted choice
weighted_choice_v3.patch xksteven, 2016-03-29 21:04 weighted choice function
weighted_choice_v4.patch xksteven, 2016-04-06 22:49
weighted_choice_v5.patch xksteven, 2016-04-07 16:25 weighted choice function v5
weighted_choice.diff rhettinger, 2016-09-06 08:03 review
weighted_choice2.diff rhettinger, 2016-09-06 22:50 Add docs and test review
Messages (69)
msg196229 - (view) Author: Alan Isaac (aisaac) Date: 2013-08-26 17:23
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.
msg196234 - (view) Author: Madison May (madison.may) * Date: 2013-08-26 18:55
+1. I've found myself in need of this feature often enough to wonder why it's not part of the stdlib.
msg196235 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-08-26 19:09
Agreed with the feature request. The itertools dance won't be easy to understand, for many people.
msg196252 - (view) Author: Madison May (madison.may) * Date: 2013-08-26 23:25
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?
msg196551 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2013-08-30 14:43
[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.
msg196567 - (view) Author: Madison May (madison.may) * Date: 2013-08-30 18:16
[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.
msg196709 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-09-01 05:38
+1 for the overall idea.  I'll take a detailed look at the patch when I get a chance.
msg196711 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-09-01 05:43
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().
msg196716 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-09-01 08:43
> 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.
msg196721 - (view) Author: Madison May (madison.may) * Date: 2013-09-01 14:37
[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?
msg196728 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-09-01 19:16
> Would these distribution generators be implemented internally (see attached patch) or publicly exposed?

See issue18900. 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.
msg196731 - (view) Author: Madison May (madison.may) * Date: 2013-09-01 19:47
> 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.
msg196741 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-09-01 21:17
> I like the idea about adding a family of distribution generators

Let's stay focused on the OP's feature request for a weighted version of choice().

For the most part, it's not a good idea to "just add" a family of anything to the standard library.  We wait for user requests and use cases to guide the design and error on the side of less, rather than more.  This helps avoid bloat.   Also, it would be a good idea to start something like this as a third-party to module to let it iterate and mature before deciding whether there was sufficient user uptake to warrant inclusion in the standard library.

For the current request, we should also do some research on existing solutions in other languages.  This isn't new territory.  What do R, SciPy, Fortran, Matlab or other statistical packages already do?  Their experiences can be used to inform our design.  Alan Kay's big criticism of Python developers is that they have a strong propensity invent from scratch rather than taking advantage of the mountain of work done by the developers who came before them.
msg196750 - (view) Author: Madison May (madison.may) * Date: 2013-09-01 23:08
> What do R, SciPy, Fortran, Matlab or other statistical packages already do? 

Numpy avoids recalculating the cumulative distribution by introducing a 'size' argument to numpy.random.choice().  The cumulative distribution is calculated once, then 'size' random choices are generated and returned.

Their overall implementation is quite similar to the method suggested in the python docs.  

>>> choices, weights = zip(*weighted_choices)
>>> cumdist = list(itertools.accumulate(weights))
>>> x = random.random() * cumdist[-1]
>>> choices[bisect.bisect(cumdist, x)]

The addition of a 'size' argument to random.choice() has already been discussed (and rejected) in Issue18414, but this was on the grounds that the standard idiom for generating a list of random choices ([random.choice(seq) for i in range(k)]) is obvious and efficient.
msg196761 - (view) Author: Westley Martínez (westley.martinez) * Date: 2013-09-02 00:31
Honestly, I think adding weights to any of the random functions are trivial enough to implement as is.  Just because something becomes a common task does not mean it ought to be added to the stdlib.

Anyway, from a user point of view, I think it'd be useful to be able to send a sequence to a function that'll weight the sequence for use by random.
msg196767 - (view) Author: Madison May (madison.may) * Date: 2013-09-02 03:00
Just ran across a great blog post on the topic of weighted random generation from Eli Bendersky for anyone interested:
http://eli.thegreenplace.net/2010/01/22/weighted-random-generation-in-python/
msg197507 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-09-11 22:29
The proposed patch add two methods to the Random class and two module level functions: weighted_choice() and weighted_choice_generator().

weighted_choice(data) accepts either mapping or sequence and returns a key or index x with probability which is proportional to data[x].

If you need several elements with same distribution, use weighted_choice_generator(data) which returns an iterator which produces random keys or indices of the data. It is more faster than calling weighted_choice(data) repeatedly and is more flexible than generating a list of random values at specified size (as in NumPy).
msg197512 - (view) Author: Neil Girdhar (neil.g) * Date: 2013-09-12 02:57
Should this really be implemented using the cumulative distribution and binary search algorithm?  Vose's Alias Method has the same initialization and memory usage cost (O(n)), but is constant time to generate each sample.

An excellent tutorial is here: http://www.keithschwarz.com/darts-dice-coins/
msg197540 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-09-12 20:32
Thank you Neil. It is interesting.

Vose's alias method has followed disadvantages (in comparison with the roulette wheel selection proposed above):

1. It operates with probabilities and uses floats, therefore it can be a little less accurate.

2. It consumes two random number (an integer and a float) for generating one sample. It can be fixed however (in the cost of additional precision lost).

3. While it has same time and memory O(n) cost for initialization, it has larger multiplication, Vose's alias method requires several times larger time and memory for initialization.

4. It requires more memory in process of generating samples.

However it has an advantage. It really has constant time cost to generate each sample.

Here are some benchmark results. "Roulette Wheel" is proposed above implementation. "Roulette Wheel 2" is its modification with normalized cumulative sums. It has twice more initialization time, but 1.5-2x faster generates each sample. "Vose's Alias" is an implementation of Vose's alias method directly translated from Java. "Vose's Alias 2" is optimized implementation which uses Python specific.

Second column is a size of distribution, third column is initialization time (in milliseconds), fourth column is time to generate each sample (in microseconds), fifth column is a number of generated samples after which this method will overtake "Roulette Wheel" (including initialization time).

Roulette Wheel          10     0.059     7.165         0
Roulette Wheel 2        10     0.076     4.105         5
Vose's Alias            10     0.129    13.206         -
Vose's Alias 2          10     0.105     6.501        69
Roulette Wheel         100     0.128     8.651         0
Roulette Wheel 2       100     0.198     4.630        17
Vose's Alias           100     0.691    12.839         -
Vose's Alias 2         100     0.441     6.547       148
Roulette Wheel        1000     0.719    10.949         0
Roulette Wheel 2      1000     1.458     5.177       128
Vose's Alias          1000     6.614    13.052         -
Vose's Alias 2        1000     3.704     6.531       675
Roulette Wheel       10000     7.495    13.249         0
Roulette Wheel 2     10000    14.961     6.051      1037
Vose's Alias         10000    69.937    13.830         -
Vose's Alias 2       10000    37.017     6.746      4539
Roulette Wheel      100000    73.988    16.180         0
Roulette Wheel 2    100000   148.176     8.182      9275
Vose's Alias        100000   690.099    13.808    259716
Vose's Alias 2      100000   391.367     7.095     34932
Roulette Wheel     1000000   743.415    19.493         0
Roulette Wheel 2   1000000  1505.409     8.930     72138
Vose's Alias       1000000  7017.669    13.798   1101673
Vose's Alias 2     1000000  4044.746     7.152    267507

As you can see Vose's alias method has very large initialization time. Non-optimized version will never overtake "Roulette Wheel" with small distributions (<100000), and even optimized version will never overtake "Roulette Wheel" with small distributions (<100000). Only with very large distributions Vose's alias method has an advantage (when you needs very larger number of samples).

Because for generating only one sample we need a method with fastest initialization we need "Roulette Wheel" implementation. And because large distributions are rare, I think there is no need in alternative implementation. In worst case for generating 1000000 samples from 1000000-elements distribution the difference between "Roulette Wheel" and "Vose's Alias 2" is a difference between 20 and 11 seconds.
msg197862 - (view) Author: Madison May (madison.may) * Date: 2013-09-16 02:20
Serhiy, from a technical standpoint, your latest patch looks like a solid solution.  From an module design standpoint we still have a few options to think through, though. What if random.weighted_choice_generator was moved to random.choice_generator and refactored to take an array of weights as an optional argument?  Likewise, random.weighted_choice could still be implemented with an optional arg to random.choice.  Here's the pros and cons of each implementation as I see them.

Implementation: weighted_choice_generator + weighted_choice
Pros: 
Distinct functions help indicate that weighted_choice should be used in a different manner than choice -- [weighted_choice(x) for _ in range(n)] isn't efficient.
Can take Mapping or Sequence as argument.
Has a single parameter
Cons:
Key, not value, is returned
Requires two new functions
Dissimilar to random.choice
Long function name (weighted_choice_generator)

Implementation: choice_generator + optional arg to choice
Pros: 
Builds on existing code layout
Value returned directly
Only a single new function required
More compact function name

Cons:
Difficult to support Mappings
Two args required for choice_generator and random.choice
Users may use [choice(x, weights) for _ in range(n)] expecting efficient results
msg197865 - (view) Author: Westley Martínez (westley.martinez) * Date: 2013-09-16 04:00
I think Storchaka's solution is more transparent and I agree with him on the point that the choice generator should be exposed.
msg197866 - (view) Author: Madison May (madison.may) * Date: 2013-09-16 04:14
>  I think Storchaka's solution is more transparent and I agree with him on the point that the choice generator should be exposed.

Valid point -- transparency should be priority #1
msg198367 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-09-24 21:26
Most existing implementation produce just index. That is why weighted_choice() accepts singular weights list and returns index. On the other hand, I think working with mapping will be wished feature too (especially because Counter is in stdlib). Indexable sequences and mappings are similar. In both cases weighted_choice() returns value which can be used as index/key of input argument.

If you need choice an element from some sequence, just use seq[weighted_choice(weights)]. Actually weighted_choice() has no common code with choice() and has too different use cases. They should be dissimilar as far as possible. Perhaps we even should avoid the "choice" part in function names (are there any ideas?) to accent this.
msg198372 - (view) Author: Madison May (madison.may) * Date: 2013-09-24 22:36
You have me convinced, Serhiy.  I see the value in making the two functions distinct.

For naming purposes, perhaps weighted_index() would be more descriptive.
msg223750 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2014-07-23 17:21
Closed issue 22048 as a duplicate of this one.
msg224947 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2014-08-06 16:12
Raymond, what is your opinion?
msg224949 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2014-08-06 16:21
I don't want to speak for Raymond, but the proposed API looks good, and it seems "Roulette Wheel 2" should be the implementation choice given its characteristics (simple, reasonably good and balanced performance).
msg224953 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2014-08-06 17:26
"Roulette Wheel 2" has twice slower initializations than "Roulette Wheel", but then generates every new item twice faster.

It is possible to implement hybrid generator, which yields first item using "Roulette Wheel", and then rescales cumulative_dist and continues with "Roulette Wheel 2". It will be so fast as "Roulette Wheel" for generating only one item and so fast as "Roulette Wheel 2" for generating multiple items.
msg224954 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2014-08-06 17:52
The setup cost of RW2 should always be within a small constant multiplier of RW's, so I'm not sure it's worth the hassle to complicate things. But it's your patch :)
msg224957 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2014-08-06 18:25
Non-generator weighted_choice() function is purposed to produce exactly one item. This is a use case for such optimization.
msg225128 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2014-08-10 08:48
Updated patch. Synchronized with tip and added optimizations.
msg225133 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-08-10 09:45
I'm adverse to adding the generator magic and the level of complexity in this patch.  Please aim for the approach I outlined above (one function to build cumulative weights and another function to choose the value).

Since this isn't a new problem, please take a look at how other languages and packages have solved the problem.
msg225137 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2014-08-10 10:32
Other languages have no such handly feature as generators. NumPy provides the size parameter to all functions and generates a bunch of random numbers at time. This doesn't look pythonic (Python stdlib prefers iterators).

I believe a generator is most Pythonic and most handly solution of this issue on Python. And it is efficient enough.
msg225140 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2014-08-10 14:06
I agree with Serhiy. There is nothing "magic" about generators in Python. Also, the concept of an infinite stream of random numbers (or random whatevers) is perfectly common (/dev/urandom being an obvious example); it is not a notion we are inventing.

By contrast, the two-function approach only makes things clumsier for people since they have to remember to combine them.
msg225148 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-08-10 17:26
When I get a chance, I'll work up an approach that is consistent with the rest of the module in terms of implementation, restartability, and API.
msg226891 - (view) Author: Christian Kleineidam (Christian.Kleineidam) Date: 2014-09-15 00:39
I like the idea of adding a weights keyword to choice and creating an additional choice_generator() that also takes weights.

A choice_generator() could take a further argument to allow unique choices and be a generator version of sample().

In some cases you want to draw randomly from a sequence till you draw an item that fulfills certain criteria. At the moment neither the sample nor the shuffle method seems to be optimal for that use case.

Given that items are commonly drawn from an urn in math, urn seems a good alternative for choice_generator().

random.urn(data, *, weights=None, unique=False)
msg262625 - (view) Author: Steven Basart (xksteven) * Date: 2016-03-29 20:39
Reopen this idea but removing the generator from weighted choice.
msg262626 - (view) Author: Steven Basart (xksteven) * Date: 2016-03-29 21:04
The entire function of weighted choice. I removed the generator and replaced it by adding an optional argument to specify an amount by which you want to call this function.
msg262642 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-03-30 01:15
Thanks for the patch.   Can I get you to fill out a contributor agreement?
msg262649 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-03-30 05:02
What is wrong with generators?
msg262652 - (view) Author: Steven Basart (xksteven) * Date: 2016-03-30 07:11
Hello rhettinger.  I filled out the form thanks for letting me know about it.  Is there anything else I have to do?

Hey serhiy.storchaka

There were several things "wrong" with the previous implementation in my opinion. 

1st they tried to add too much.  Which would if allowed would clutter up the random library if every function had both it's implementation as well as an accompanied generator.  The other problem being that both were attempted to be made as callable to the public API.  I would prefer the generator if present to be hidden and would also have to be more sophisticated to be able to check if it was being called with new input.

2nd by adding in the generator to the pulbic API of the random library it makes it far more confusing and obfuscates the true purpose of this function anyways which is to get a weighted choice.  

So basically there is nothing wrong with generators but they don't necessarily belong here so I removed it to try to get back to the core principles of what the function should be doing, by making it simpler.
msg262656 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-03-30 08:56
I disagree.

My patch adds two functions because they serve two different purposes. weighted_choice() returns one random value as other functions in the random module. weighted_choice_generator() provides more efficient way to generate random values, since startup cost is more significant than for other random value generators. Generators are widely used in Python, especially in Python 3. If they considered confusing, we should deprecate builtins map(), filter(), zip() and the itertools module at first place.

Your function, Steven, returns a list containing one random value by default. It does not match the interface of other functions in the random module. It matches the interface of NumPy random module. In Python you need two separate functions, one that returns single value,  and other that returns a list of values. But returning iterator and generating values by demand is more preferable in Python 3. Generatorsa are more flexible. With weighted_choice_generator() it is easy to get the result of your function: list(islice(weighted_choice_generator(data), amount)). But generating dynamic amount of values with your interface is impossible.

Raymond, if you have now free time, could you please make a review of weighted_choice_generator_2.patch?
msg262678 - (view) Author: Steven Basart (xksteven) * Date: 2016-03-30 18:48
Hey serhiy.storchaka

I can edit the code to output just one value if called with simply a list and then return a list of values if called with the optional amount parameter.  My code also needs to check that amount >= 1.  

My code was mostly just to restart this discussion as I personally like the idea of the function for weighted choice and would like it to be standard in the random library. 

I have no qualms with adding both weighted_choice and weighted_choice_generator but my concern is mostly that you are asking too much and it won't go through by trying to add two functions at the same time.  The other thing is that I believe that weighted_choice could suffice with just one function call.

I just think my last concern is that generators are different from the other functions in random.py.  Whereas they are more intuitive and accepted in the builtins like map and zip etc.  There isn't any other functions in the random library that return that type of object when called. They instead return a numerical result.  

Those are my concerns and hence why I rewrote the code.
msg262744 - (view) Author: Christian Kleineidam (Christian.Kleineidam) Date: 2016-04-01 15:43
A user can use map(), filter(), zip() without knowing anything about generators. In most cases those function will do their magic and provide a finite number of outputs. 

The weighted_choice_generator on the other hand isn't as easy to use. If the user wants 5 values from it, they need to know about `take()` from itertools or call `next()`.
msg262967 - (view) Author: Westley Martínez (westley.martinez) * Date: 2016-04-06 22:11
I still like Serhiy's implementation more. A function that returns a list instead of the item is unnatural and doesn't fit with the rest of the module.

I think there's need to be some discussion about use cases. What do users actually want? Maybe post this on the ideas list.
msg262970 - (view) Author: Steven Basart (xksteven) * Date: 2016-04-06 22:46
Okay so I added a few lines of code.  One to make it return a single number if amount == 1 and the other to check that the amount > 1.

The main difference I've noticed between this implementation and previous versions compared to say R is that in R they provide a boolean flag to ask if sampling with replacement.

Here's there documentation and source code:
https://github.com/wch/r-source/blob/e5b21d0397c607883ff25cca379687b86933d730/src/library/base/man/sample.Rd

https://github.com/wch/r-source/blob/e5b21d0397c607883ff25cca379687b86933d730/src/library/base/R/sample.R

Maybe someone else can comment more on the use cases.  I can only say for myself that I've needed this function plenty of times when working with samples that have a non uniform distribution.
msg262971 - (view) Author: Steven Basart (xksteven) * Date: 2016-04-06 22:49
I reuploaded the file.  The spacing on the if amount < 1 was off.  Hopefully its fixed now.
msg262981 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-04-07 07:21
> One to make it return a single number if amount == 1 and the other to check that the amount > 1.

I think that's a dangerous API. Any code making a call to "weighted_choice(..., amount=n)" for variable n now has to be prepared to deal with two possible result types. It would be easy to introduce buggy code that fails in the corner case n = 1.
msg262982 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2016-04-07 07:43
> One to make it return a single number if amount == 1 and the other to check that the amount > 1.

Suggestion: if you want to go that way, return a single number if `amount` is not provided (so make the default value for `amount` None rather than 1). If `amount=1` is explicitly given, a list containing one item should be returned.

I also think there's no reason to raise an exception when `amount = 0`: just return an empty list.

For comparison, here's NumPy's "uniform" generator, which generates a scalar if the "size" parameter is not given, and an array if "size" is given, even if it's 1.

>>> np.random.uniform()
0.4964992470265117
>>> np.random.uniform(size=1)
array([ 0.64817717])
>>> np.random.uniform(size=0)
array([], dtype=float64)
msg262983 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2016-04-07 07:47
> Suggestion: if you want to go that way, return a single number if `amount` is not provided (so make the default value for `amount` None rather than 1). If `amount=1` is explicitly given, a list containing one item should be returned.

+1
msg262994 - (view) Author: Steven Basart (xksteven) * Date: 2016-04-07 16:23
Re-implemented with suggested improvements taken into account. Thanks @mark.dickinson and @pitrou for the suggestions.  

I also removed the redundant "fast path" portion for this code since it doesn't deal with generators anyways.

Let me know additional thoughts about it.
msg262995 - (view) Author: Steven Basart (xksteven) * Date: 2016-04-07 16:25
Left in a line of code that was supposed to be removed. Fixed.
msg267782 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-06-08 05:10
Raymond, do you have a time for this issue?
msg272767 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-08-15 15:13
Raymond, any chance to get weighted random choices generator in 3.6? Less than month is left to feature code freeze.
msg272785 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-08-15 17:29
FWIW, I have four full days set aside for the upcoming pre-feature release sprint which is dedicated to taking time to thoughtfully evaluate pending feature requests.  In the meantime, I'm contacting Alan Downey for a consultation for the best API for this.  As mentioned previously, the generator version isn't compatible with the design of the rest of the module that allows streams to have their state saved and restored at arbitrary points in the sequence.  One API would be to create a list all at once (like random.sample does).  Another would be to have two steps (like str.maketrans and str.translate).  Ideally, the API should integrate neatly with collections.Counter as a possible input for the weighting.  Hopefully, Alan can also comment on the relative frequency of small integer weightings versus the general case (the former benefits from a design using random.choice() applied to Counter.elements() and the latter benefits from a design with accumulate() and bisect()).  Note, this is a low priority feature (no real demonstrated need, there is already a recipe for it in the docs, and once the best API have been determined, the code is so simple that any of us could implement it in only a few minutes).
msg274538 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-09-06 08:03
Latest draft patch attached (w/o tests or docs).
Incorporates consultation from Alan Downey and Jake Vanderplas.

* Population and weights are separate arguments (like numpy.random.choice() and sample() in R).  Matches the way data would arrive in Pandas.  Easily extracted from a Counter or dict using keys() and values().  Suitable for applications that sample the population multiple times but using different weights.  See https://stat.ethz.ch/R-manual/R-devel/library/base/html/sample.html and http://docs.scipy.org/doc/numpy/reference/generated/numpy.random.choice.html

* Excludes a replacement=False option. That use case necessarily has integer weights and may be better suited to the existing random.sample() rather than trying to recompute a CDF on every iteration as we would have to in this function.

* Allows cumulative_weights to be submitted instead of individual weights.  This supports uses cases where the CDF already exists (as in the ThinkBayes examples) and where we want to periodically reuse the same CDF for repeated samples of the same population -- this occurs in resampling applications, Gibbs sampling, and Monte Carlo Markov Chain applications.  Per Jake, "MCMC/Gibbs Sampling approaches generally boil down to a simple weighted coin toss at each step" and "It's definitely common to do aggregation of multiple samples, e.g. to compute sample statistics"

* The API allows the weights to be integers, fractions, decimals, or floats.  Likewise, the population and weights can be any Sequence.  Population elements need not be hashable.

* Returning a list means that the we don't have to save state in mid-stream (that is why we can't use a generator).  A list feeds nicely into Counters, mean, median, stdev, etc for summary statistics.  Returning a list parallels what random.sample() does, keeping the module internally consistent.

* Default uniform weighting falls back to random.choice() which would be more efficient than bisecting.

* Bisecting tends to beat other approaches in the general case.  See http://eli.thegreenplace.net/2010/01/22/weighted-random-generation-in-python

* Incorporates error checks for len(population)==len(cum_weights) and for conflicting specification of both weights and cumulative weights.

There API is not perfect and there are some aspects that give me heartburn.  1) Not saving the computed CDF is waste and forces the user to pre-build the CDF if they want to save it for later use (the API could return both the selections and the CDF but that would be awkward and atypical).  2) For the common case of having small integer weights on a small population, the bisecting approach is slower than using random.choice on a population expanded to include the selections multiple times in proportion to their weights (that said, short of passing in a flag, there is no cheap easy way for this function to detect that case and give it a fast path).  3) Outputting a list is inefficient if all you're doing with result is summarizing it with a Counter, histogram tool, mean, median, or stdev.  4)  There is no cheap way to check to see if the user supplied cum_weights is sorted or if the weights contain negative values.
msg274677 - (view) Author: Davin Potts (davin) * (Python committer) Date: 2016-09-07 00:00
I've gone through the patch -- looks good to me.
msg274684 - (view) Author: Roundup Robot (python-dev) Date: 2016-09-07 00:16
New changeset a5856153d942 by Raymond Hettinger in branch 'default':
Issue #18844: Add random.weighted_choices()
https://hg.python.org/cpython/rev/a5856153d942
msg274686 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-09-07 00:17
Thanks Davin.
msg274760 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-09-07 05:11
1. Returning a list instead of an iterator looks unpythonic to me. Values generated sequentially, there are no advantages of returning a list.

2. An implementation lacks optimizations used in my patch.

3. The documentation still contains a receipt for weighted choice. It is incompatible with new function.
msg274907 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-09-07 23:08
There isn't really an option to return a generator because it conflicts the rest of the module that uses lists elsewhere and that allows state to be saved and restored before and after any function call.  One of the design reviewers also said that the generator form would harder for students to use.

I left the text in the examples section unchanged because it is still valid (showing how to make a cumulative distribution and how to build a fast alternative for the special case of small integer weights). Before the 3.6 release, I expect to expand this section to provide recipes for a MCMC application (using choices() with a passed-in CDF) and some other examples suggested by the design reviewers.

The optimization hacks in the other patch don't seem worth it.  The current code is readable and runs fast (the principal steps are all C functions).
msg274964 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-09-08 05:01
Using a generator doesn't prevents state to be saved and restored.
msg277485 - (view) Author: Roundup Robot (python-dev) Date: 2016-09-27 04:46
New changeset 39a4be5e003d by Raymond Hettinger in branch '3.6':
Issue #18844: Make the number of selections a keyword-only argument for random.choices().
https://hg.python.org/cpython/rev/39a4be5e003d
msg277486 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-09-27 04:56
Equidistributed examples:
    
    choices(c.execute('SELECT name FROM Employees').fetchall(), k=20)
    choices(['hearts', 'diamonds', 'spades', 'clubs'], k=5)
    choices(list(product(card_facevalues, suits)), k=5)

Weighted selection examples:

  Counter(choices(['red', 'black', 'green'], [18, 18, 2], k=3800))   # american roulette
  Counter(choices(['hit', 'miss'], [5, 1], k=600))                   # russian roulette
  choices(fetch('employees'), fetch('years_of_service'), k=100)      # tenure weighted
  choices(cohort, map(cancer_risk, map(risk_factors, cohort)), k=50) # risk weighted

Star unpacking example:

   transpose = lambda s: zip(*s)
   craps = [(2, 1), (3, 2), (4, 3), (5, 4), (6, 5), (7, 6), (8, 5), (9, 4), (10, 3), (11, 2), (12, 1)]
   print(choices(*transpose(craps), k=10))

Comparative APIs from other languages:

    http://www.mathworks.com/help/stats/randsample.html
    http://docs.scipy.org/doc/numpy/reference/generated/numpy.random.choice.html
    https://stat.ethz.ch/R-manual/R-devel/library/base/html/sample.html
    https://reference.wolfram.com/language/ref/RandomChoice.html
msg277487 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-09-27 05:01
###################################################################
# Flipping a biased coin

from collections import Counter
from random import choices

print(Counter(choices(range(2), [0.9, 0.1], k=1000)))

###################################################################
# Bootstrapping

'From a small statistical sample infer a 90% confidence interval for the mean'
# http://statistics.about.com/od/Applications/a/Example-Of-Bootstrapping.htm

from statistics import mean
from random import choices

data = 1, 2, 4, 4, 10
means = sorted(mean(choices(data, k=5)) for i in range(20))
print('The sample mean of {:.1f} has a 90% confidence interval from {:.1f} to {:.1f}'.format(
  mean(data), means[1], means[-2]))
msg278516 - (view) Author: Roundup Robot (python-dev) Date: 2016-10-12 05:42
New changeset 433cff92d565 by Raymond Hettinger in branch '3.6':
Issue #18844:  Fix-up examples for random.choices().  Remove over-specified test.
https://hg.python.org/cpython/rev/433cff92d565
msg278633 - (view) Author: Roundup Robot (python-dev) Date: 2016-10-14 05:20
New changeset d4e715e725ef by Raymond Hettinger in branch '3.6':
Issue #18844:  Add more tests
https://hg.python.org/cpython/rev/d4e715e725ef
msg279701 - (view) Author: Roundup Robot (python-dev) Date: 2016-10-29 23:57
New changeset 32bfc81111b6 by Raymond Hettinger in branch '3.6':
Issue #18844: Make the various ways for specifing weights produce the same results.
https://hg.python.org/cpython/rev/32bfc81111b6
msg279702 - (view) Author: Roundup Robot (python-dev) Date: 2016-10-30 00:43
New changeset 09a87b16d5e5 by Raymond Hettinger in branch '3.6':
Issue #18844:  Strengthen tests to include a case with unequal weighting
https://hg.python.org/cpython/rev/09a87b16d5e5
History
Date User Action Args
2016-10-30 00:43:15python-devsetmessages: + msg279702
2016-10-29 23:57:18python-devsetmessages: + msg279701
2016-10-14 05:20:09python-devsetmessages: + msg278633
2016-10-12 05:42:49python-devsetmessages: + msg278516
2016-09-27 05:01:50rhettingersetmessages: + msg277487
2016-09-27 04:56:07rhettingersetmessages: + msg277486
2016-09-27 04:46:34python-devsetmessages: + msg277485
2016-09-08 05:01:14serhiy.storchakasetmessages: + msg274964
2016-09-07 23:08:24rhettingersetmessages: + msg274907
2016-09-07 05:11:22serhiy.storchakasetmessages: + msg274760
2016-09-07 00:17:01rhettingersetstatus: open -> closed
resolution: fixed
messages: + msg274686
2016-09-07 00:16:06python-devsetnosy: + python-dev
messages: + msg274684
2016-09-07 00:00:15davinsetnosy: + davin
messages: + msg274677
2016-09-06 22:50:59rhettingersetfiles: + weighted_choice2.diff
2016-09-06 08:03:46rhettingersetfiles: + weighted_choice.diff

messages: + msg274538
2016-08-15 17:29:20rhettingersetmessages: + msg272785
2016-08-15 15:13:33serhiy.storchakasetmessages: + msg272767
2016-06-08 05:10:30serhiy.storchakasetmessages: + msg267782
2016-04-07 16:25:19xkstevensetfiles: + weighted_choice_v5.patch

messages: + msg262995
2016-04-07 16:24:47xkstevensetfiles: - weighted_choice_v5.patch
2016-04-07 16:23:32xkstevensetfiles: + weighted_choice_v5.patch

messages: + msg262994
2016-04-07 07:47:20pitrousetmessages: + msg262983
2016-04-07 07:43:46mark.dickinsonsetmessages: + msg262982
2016-04-07 07:21:09mark.dickinsonsetmessages: + msg262981
2016-04-06 22:49:33xkstevensetfiles: + weighted_choice_v4.patch

messages: + msg262971
2016-04-06 22:48:05xkstevensetfiles: - weighted_choice_v4.patch
2016-04-06 22:46:02xkstevensetfiles: + weighted_choice_v4.patch

messages: + msg262970
2016-04-06 22:11:45westley.martinezsetmessages: + msg262967
2016-04-01 15:43:11Christian.Kleineidamsetmessages: + msg262744
2016-03-30 18:48:14xkstevensetmessages: + msg262678
2016-03-30 08:56:22serhiy.storchakasetkeywords: + needs review

messages: + msg262656
versions: + Python 3.6, - Python 3.5
2016-03-30 07:11:55xkstevensetmessages: + msg262652
2016-03-30 05:02:04serhiy.storchakasetmessages: + msg262649
2016-03-30 01:15:24rhettingersetmessages: + msg262642
2016-03-29 21:04:47xkstevensetfiles: + weighted_choice_v3.patch

messages: + msg262626
2016-03-29 20:39:37xkstevensetfiles: + weighted_choice_v3.diff
nosy: + xksteven
messages: + msg262625

2014-09-15 00:39:05Christian.Kleineidamsetnosy: + Christian.Kleineidam
messages: + msg226891
2014-08-10 17:26:08rhettingersetmessages: + msg225148
2014-08-10 14:06:02pitrousetmessages: + msg225140
2014-08-10 10:32:42serhiy.storchakasetmessages: + msg225137
2014-08-10 09:45:12rhettingersetmessages: + msg225133
2014-08-10 08:48:30serhiy.storchakasetfiles: + weighted_choice_generator_2.patch

messages: + msg225128
2014-08-06 18:25:02serhiy.storchakasetmessages: + msg224957
2014-08-06 17:52:11pitrousetmessages: + msg224954
2014-08-06 17:27:00serhiy.storchakasetmessages: + msg224953
2014-08-06 16:21:49pitrousetmessages: + msg224949
2014-08-06 16:12:45serhiy.storchakasetmessages: + msg224947
versions: + Python 3.5, - Python 3.4
2014-07-23 17:22:32mark.dickinsonsetnosy: + dkorchem
2014-07-23 17:21:10mark.dickinsonsetmessages: + msg223750
2014-07-23 17:20:44mark.dickinsonlinkissue22048 superseder
2013-09-24 22:36:07madison.maysetmessages: + msg198372
2013-09-24 21:26:04serhiy.storchakasetmessages: + msg198367
2013-09-16 04:14:48madison.maysetmessages: + msg197866
2013-09-16 04:00:25westley.martinezsetmessages: + msg197865
2013-09-16 02:20:10madison.maysetmessages: + msg197862
2013-09-13 13:38:53eli.benderskysetnosy: - eli.bendersky
2013-09-12 20:32:18serhiy.storchakasetfiles: + wcg_bench.py

messages: + msg197540
2013-09-12 02:57:46neil.gsetnosy: + neil.g
messages: + msg197512
2013-09-11 22:29:56serhiy.storchakasetstage: patch review
2013-09-11 22:29:41serhiy.storchakasetfiles: + weighted_choice_generator.patch

messages: + msg197507
2013-09-02 03:00:51madison.maysetnosy: + eli.bendersky
messages: + msg196767
2013-09-02 00:31:23westley.martinezsetmessages: + msg196761
2013-09-01 23:08:54madison.maysetmessages: + msg196750
2013-09-01 21:17:48rhettingersetmessages: + msg196741
2013-09-01 19:47:51madison.maysetmessages: + msg196731
2013-09-01 19:16:37serhiy.storchakasetmessages: + msg196728
2013-09-01 14:47:16madison.maysetfiles: + weighted_choice_v2.diff
2013-09-01 14:45:49madison.maysetfiles: - weighted_choice_v2.diff
2013-09-01 14:37:04madison.maysetfiles: + weighted_choice_v2.diff

messages: + msg196721
2013-09-01 08:43:40serhiy.storchakasetmessages: + msg196716
2013-09-01 05:50:01westley.martinezsetnosy: + westley.martinez
2013-09-01 05:43:42rhettingersetmessages: + msg196711
2013-09-01 05:38:28rhettingersetassignee: rhettinger
messages: + msg196709
2013-08-30 18:16:30madison.maysetmessages: + msg196567
2013-08-30 14:43:41mark.dickinsonsetnosy: + tim.peters
messages: + msg196551
2013-08-26 23:25:58madison.maysetfiles: + weighted_choice.diff
keywords: + patch
messages: + msg196252
2013-08-26 19:09:04pitrousetnosy: + pitrou
messages: + msg196235
2013-08-26 18:55:35madison.maysetnosy: + madison.may
messages: + msg196234
2013-08-26 17:47:20serhiy.storchakasetnosy: + rhettinger, mark.dickinson, serhiy.storchaka

components: + Library (Lib)
versions: + Python 3.4
2013-08-26 17:23:45aisaaccreate