On Mon, May 14, 2018 at 11:54:32AM +0000, Paul Moore wrote:

> Requiring a pre-check on cum_weights (for example, the obvious check 
> that the sequence is nondecreasing) would add an O(n) step, and so 
> significantly impact performance for that case.

You may very well be right, but we should at least think about ways to 
mitigate this. After all, it doesn't matter how fast a function is if it 
returns the wrong value.

If an ahead-of-time check is too slow, can we make it just-in-time? 
Perhaps bisect can be made to fail if it finds values in the wrong 
order. That might not detect all out-of-order input (perhaps it only 
checks the values it actually looks at), it might be "good enough" to at 
least catch some bad input.