On Sat, 13 Oct 2007, Frank Barknecht wrote:
Mathieu Bouchard hat gesagt: // Mathieu Bouchard wrote:
If ever you need a much larger table, then it may become too slow, and if so, then write again and I'll explain how to accelerate it.
You made me curious: How would you recommend to make it faster for large lists?
You make a binary search in the array. Suppose every element could be what you look for. Look at the value in the middle element. You know that elements are already sorted (because they are cumulative of a nonnegative function) so you can eliminate all possibilities on one of the sides of the middle element. Then you pick a new middle... You can go through a 1024-element array in 10 steps using just [<].
So, this is the real reason for cumulating: you can't use that trick if you don't cumulate.
_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal QC Canada