random.choices() Suggest that the code confirm that cum_weights sequence is in ascending order

[Steven D'Aprano]

On Mon, 14 May 2018 12:59:28 +0100, Paul Moore wrote:

> The problem is that supplying cum_weights allows the code to run in
> O(log n) by using bisection. This is significantly faster on large
> populations. Adding a test that the cumulative weights are nondecreasing
> would add an O(n) step to the code.
> 
> So while I understand the OP's problem, I don't think it's soluble
> without making the cum_weights argument useless in practice.

How does O(N) make it "useless"? There are lots of O(N) algorithms, even 
O(N**2) and O(2**N) which are nevertheless still useful.

Besides, might this be "premature optimization"? I get it that everyone 
wants their code to be faster rather than unnecessarily slower, but how 
often is random.choices() the bottleneck in your application?



> Better
> documentation might be worthwhile (although I don't personally find the
> current docs confusing, so suggestions for improvements would be
> helpful).

Indeed.

Hopefully the OP is still reading and is willing to sign up on the bug 
tracker.



-- 
Steve