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

[Paul Moore]

On 14 May 2018 at 14:07, Steven D'Aprano
<steve+comp.lang.python at pearwood.info> wrote:
> 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.

Well, I've never seen an actual use case for this argument (I can't
think of a case where I'd even have cumulative weights rather than
weights, and obviously calculating the cumulative weights from the
actual weights is what we're trying to avoid). And if you have
cum_weights and O(n) is fine, then calculating weights from
cum_weights is acceptable (although pointless, as it simply duplicates
work). So the people who *really* need cum_weights are those who have
the cumulative weights already, and cannot afford an O(n)
precalculation step.

But yes, clearly in itself an O(n) algorithm isn't useless. And
agreed, in most cases whether random.choices() is O(n) or O(log n) is
irrelevant in practice.

Paul