bearophile wrote:
Andrei Alexandrescu:
(I also have a cool idea for statistically checking sortedness
without deteriorating complexity. Essentially assumeSorted(r) could
check that r is sorted by tossing a rigged coin with
P(head)=1.0/r.length and deciding to check if head comes up. That
way, the amortized complexity of the check is O(1)).
But the safety (reliability) of such test is low, and it can increase
a lot the variance of the running time of a piece of code... So it's
a cute idea, but I am not sure it's a good one.
Some reliability is considerably to have than patently none especially
when approached in a principled manner (i.e. engineered to not influence
complexity), and I don't think the variance argument holds except for
synthetic cases (very few searches in very large ranges). Anyway, I
think I'll insert the checks only in the debug version.
Andrei
