From: Christos Dimitrakakis <olethros@fa...>  20100621 07:29:42

On 21/06/10 09:21, Christos Dimitrakakis wrote: > On 21/06/10 07:46, W.D. Beelitz wrote: >> The value of rpms is changing "slowly" in most cases. PS2. So, the ideal way to implement this is as follows: 1. Assume we have r_1, ..., r_n rpm points on the spline, with values T_1, ..., T_n. 2. Let r be the last rpm value and [r_i, r_j] be the smallest interval containing r (i.e. so that j = i + 1) 3. Let r' be the current rpm value. 4. If r' > r, do binary search on the interval [r_i, r_n], else do binary search on the interval [r_1, r_j]. 5. Obtain a new interval [r'_i, r'_j]. As you can see, this reduces computation by a factor of 2. So, original complexity: O(n), binary search O(log n), and this O(log sqrt(n)). Again, I wouldn't do a linear search because once the number of points n increases, the amount of search increases with rate O(n). 