[issue18844] allow weights in random.choice

Changes by Donald Stufft : -- pull_requests: +1022 ___ Python tracker ___ ___

[issue18844] allow weights in random.choice

Roundup Robot added the comment: 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 -- ___ Python tracker

[issue18844] allow weights in random.choice

Roundup Robot added the comment: New changeset 32bfc8b6 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/32bfc8b6 -- ___ Python

[issue18844] allow weights in random.choice

Roundup Robot added the comment: New changeset d4e715e725ef by Raymond Hettinger in branch '3.6': Issue #18844: Add more tests https://hg.python.org/cpython/rev/d4e715e725ef -- ___ Python tracker

[issue18844] allow weights in random.choice

Roundup Robot added the comment: 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 -- ___ Python tracker

[issue18844] allow weights in random.choice

Raymond Hettinger added the comment: ### # Flipping a biased coin from collections import Counter from random import choices print(Counter(choices(range(2), [0.9, 0.1], k=1000)))

[issue18844] allow weights in random.choice

Raymond Hettinger added the comment: 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:

[issue18844] allow weights in random.choice

Roundup Robot added the comment: 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 -- ___ Python

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: Using a generator doesn't prevents state to be saved and restored. -- ___ Python tracker ___

[issue18844] allow weights in random.choice

Raymond Hettinger added the comment: 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

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: 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

[issue18844] allow weights in random.choice

Raymond Hettinger added the comment: Thanks Davin. -- resolution: -> fixed status: open -> closed ___ Python tracker ___

[issue18844] allow weights in random.choice

Roundup Robot added the comment: New changeset a5856153d942 by Raymond Hettinger in branch 'default': Issue #18844: Add random.weighted_choices() https://hg.python.org/cpython/rev/a5856153d942 -- nosy: +python-dev ___ Python tracker

[issue18844] allow weights in random.choice

Davin Potts added the comment: I've gone through the patch -- looks good to me. -- nosy: +davin ___ Python tracker ___

[issue18844] allow weights in random.choice

Changes by Raymond Hettinger : Added file: http://bugs.python.org/file44407/weighted_choice2.diff ___ Python tracker ___

[issue18844] allow weights in random.choice

Raymond Hettinger added the comment: 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.

[issue18844] allow weights in random.choice

Raymond Hettinger added the comment: 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

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: Raymond, any chance to get weighted random choices generator in 3.6? Less than month is left to feature code freeze. -- ___ Python tracker

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: Raymond, do you have a time for this issue? -- ___ Python tracker ___ ___

[issue18844] allow weights in random.choice

Steven Basart added the comment: Left in a line of code that was supposed to be removed. Fixed. -- Added file: http://bugs.python.org/file42393/weighted_choice_v5.patch ___ Python tracker

[issue18844] allow weights in random.choice

Changes by Steven Basart : Removed file: http://bugs.python.org/file42392/weighted_choice_v5.patch ___ Python tracker ___

[issue18844] allow weights in random.choice

Steven Basart added the comment: 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

[issue18844] allow weights in random.choice

Antoine Pitrou added the comment: > 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 --

[issue18844] allow weights in random.choice

Mark Dickinson added the comment: > 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

[issue18844] allow weights in random.choice

Mark Dickinson added the comment: > 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

[issue18844] allow weights in random.choice

Steven Basart added the comment: I reuploaded the file. The spacing on the if amount < 1 was off. Hopefully its fixed now. -- Added file: http://bugs.python.org/file42386/weighted_choice_v4.patch ___ Python tracker

[issue18844] allow weights in random.choice

Changes by Steven Basart : Removed file: http://bugs.python.org/file42385/weighted_choice_v4.patch ___ Python tracker ___

[issue18844] allow weights in random.choice

Steven Basart added the comment: 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

[issue18844] allow weights in random.choice

Westley Martínez added the comment: 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

[issue18844] allow weights in random.choice

Christian Kleineidam added the comment: 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

[issue18844] allow weights in random.choice

Steven Basart added the comment: 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

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: 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

[issue18844] allow weights in random.choice

Steven Basart added the comment: 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

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: What is wrong with generators? -- ___ Python tracker ___ ___

[issue18844] allow weights in random.choice

Raymond Hettinger added the comment: Thanks for the patch. Can I get you to fill out a contributor agreement? -- ___ Python tracker ___

[issue18844] allow weights in random.choice

Steven Basart added the comment: 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. -- Added file: http://bugs.python.org/file42323/weighted_choice_v3.patch

[issue18844] allow weights in random.choice

Steven Basart added the comment: Reopen this idea but removing the generator from weighted choice. -- nosy: +progressive-o Added file: http://bugs.python.org/file42322/weighted_choice_v3.diff ___ Python tracker

[issue18844] allow weights in random.choice

Christian Kleineidam added the comment: 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

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: Updated patch. Synchronized with tip and added optimizations. -- Added file: http://bugs.python.org/file36331/weighted_choice_generator_2.patch ___ Python tracker rep...@bugs.python.org

[issue18844] allow weights in random.choice

Raymond Hettinger added the comment: 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

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: 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

[issue18844] allow weights in random.choice

Antoine Pitrou added the comment: 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

[issue18844] allow weights in random.choice

Raymond Hettinger added the comment: 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. -- ___ Python tracker rep...@bugs.python.org

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: Raymond, what is your opinion? -- versions: +Python 3.5 -Python 3.4 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844 ___

[issue18844] allow weights in random.choice

Antoine Pitrou added the comment: 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). --

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: 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

[issue18844] allow weights in random.choice

Antoine Pitrou added the comment: 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 :) -- ___ Python tracker rep...@bugs.python.org

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: Non-generator weighted_choice() function is purposed to produce exactly one item. This is a use case for such optimization. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844

[issue18844] allow weights in random.choice

Mark Dickinson added the comment: Closed issue 22048 as a duplicate of this one. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844 ___ ___

[issue18844] allow weights in random.choice

Changes by Mark Dickinson dicki...@gmail.com: -- nosy: +dkorchem ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844 ___ ___ Python-bugs-list

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: 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

[issue18844] allow weights in random.choice

Madison May added the comment: 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. -- ___ Python tracker rep...@bugs.python.org

[issue18844] allow weights in random.choice

Madison May added the comment: 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

[issue18844] allow weights in random.choice

Westley Martínez added the comment: I think Storchaka's solution is more transparent and I agree with him on the point that the choice generator should be exposed. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844

[issue18844] allow weights in random.choice

Madison May added the comment: 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 -- ___ Python tracker

[issue18844] allow weights in random.choice

Changes by Eli Bendersky eli...@gmail.com: -- nosy: -eli.bendersky ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844 ___ ___ Python-bugs-list

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: 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

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: 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

[issue18844] allow weights in random.choice

Changes by Serhiy Storchaka storch...@gmail.com: -- stage: - patch review ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844 ___ ___

[issue18844] allow weights in random.choice

Neil Girdhar added the comment: 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:

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: 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

[issue18844] allow weights in random.choice

Madison May added the comment: [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)

[issue18844] allow weights in random.choice

Changes by Madison May madison@students.olin.edu: Removed file: http://bugs.python.org/file31546/weighted_choice_v2.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844 ___

[issue18844] allow weights in random.choice

Changes by Madison May madison@students.olin.edu: Added file: http://bugs.python.org/file31547/weighted_choice_v2.diff ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844 ___

[issue18844] allow weights in random.choice

Serhiy Storchaka added the comment: 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

[issue18844] allow weights in random.choice

Madison May added the comment: 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

[issue18844] allow weights in random.choice

Raymond Hettinger added the comment: 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

[issue18844] allow weights in random.choice

Madison May added the comment: 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

[issue18844] allow weights in random.choice

Westley Martínez added the comment: 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

[issue18844] allow weights in random.choice

Madison May added the comment: 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/ -- nosy: +eli.bendersky

[issue18844] allow weights in random.choice

Raymond Hettinger added the comment: +1 for the overall idea. I'll take a detailed look at the patch when I get a chance. -- assignee: - rhettinger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844

[issue18844] allow weights in random.choice

Raymond Hettinger added the comment: 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

[issue18844] allow weights in random.choice

Changes by Westley Martínez aniko...@gmail.com: -- nosy: +anikom15 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844 ___ ___ Python-bugs-list

[issue18844] allow weights in random.choice

Mark Dickinson added the comment: [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

[issue18844] allow weights in random.choice

Madison May added the comment: [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

[issue18844] allow weights in random.choice

New submission from Alan Isaac: 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

[issue18844] allow weights in random.choice

Changes by Serhiy Storchaka storch...@gmail.com: -- components: +Library (Lib) nosy: +mark.dickinson, rhettinger, serhiy.storchaka versions: +Python 3.4 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844

[issue18844] allow weights in random.choice

Madison May added the comment: +1. I've found myself in need of this feature often enough to wonder why it's not part of the stdlib. -- nosy: +madison.may ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844

[issue18844] allow weights in random.choice

Antoine Pitrou added the comment: Agreed with the feature request. The itertools dance won't be easy to understand, for many people. -- nosy: +pitrou ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue18844

[issue18844] allow weights in random.choice

Madison May added the comment: 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