On 14 May 2018 at 14:07, Steven D'Aprano <steve+comp.lang.pyt...@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 -- https://mail.python.org/mailman/listinfo/python-list
