On Mon, 14 May 2018 22:27:24 +1000, Chris Angelico wrote: > On Mon, May 14, 2018 at 9:59 PM, Paul Moore <p.f.mo...@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 -- https://mail.python.org/mailman/listinfo/python-list
