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

[Paul Moore]

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. Better
documentation might be worthwhile (although I don't personally find
the current docs confusing, so suggestions for improvements would be
helpful).

Paul


On 14 May 2018 at 12:36, Steven D'Aprano
<steve+comp.lang.python at pearwood.info> wrote:
> Hi Paul, and welcome!
>
> On Sun, 13 May 2018 17:48:47 -0700, Paul wrote:
>
>> Hi,
>>   I just learned how to use random.choices().
> [...]
>> Consequently, I specified 'cum_weights' with a sequence which wasn't in
>> ascending order.  I got back k results but I determined that they
>> weren't correct (eg, certain population values were never returned).
>>
>>   Since the non-ascending sequence, which I had supplied, could not
>> possibly be valid input, why isn't this checked (and an error returned)?
>>  Returning incorrect results (which could be hard to spot as being
>> incorrect) is much more dangerous.  Also, checking that the list is in
>> ascending order need only be done once, and seems like it would be
>> inexpensive.
>
> Sounds like a reasonable feature request to me.
>
>
> https://bugs.python.org/issue33494
>
>
>
> --
> Steve
>
> --
> https://mail.python.org/mailman/listinfo/python-list