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

Mon May 14 08:59:12 EDT 2018

On 2018年5月14日 22:27:24 +1000, Chris Angelico wrote:
> On Mon, May 14, 2018 at 9:59 PM, Paul Moore <p.f.moore at gmail.com> 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.
>>>>> Hang on - are the 'n' and 'log n' there referring to the same n?

Yes -- the number of values you are choosing from, hence the number of 
weights.
If there are N values (and N weights), an upfront check would need to 
look at all N of them in the worst case that they were already in non-
descending order. (Of course it can bail out early if the check fails.)
Whereas the choice itself can use bisect to do a binary search of the 
values, which on average takes only log N comparisons.
-- 
Steve