5 ms·
If your data is uniformly distributed, you wouldn't expect higher order approximations to reduce error. You would have to weigh the cost of that approximation a
by pvansandt 3y ago
If your data is uniformly distributed, you wouldn't expect higher order approximations to reduce error. You would have to weigh the cost of that approximation against using an interpolation to get more local data. So, a linear equation is appropriate here.
If your data is non-linear, then polynomials will require a lot of terms to have low enough error, eg. on zipf. You also need to be able to fit the curve efficiently, so hyperbolic interpolation was a viable option.
With respect to finding the pivot beforehand, by choosing the end points, you can have confidence that you won't need to saturate at the end points in the first step. You might get better error by finding a better slope, but that is accepting a much higher cost to choosing the parameters.
I'd be curious to learn about related approaches which you've measured to be a big improvement, although I didn't understand all the terms you used.
- rurban 3y agoAs I said, a non-linear distribution can easily be fit into a quadratic curve, if logarithmic. Multidimensional curves, ie lots of holes in the data, do make no sense to model for the initial pivot calc. Binary search finds them much better then. The cost is similar to a hash table, almost constant with 2-4 branches, and mostly into cached data.