Linearly "smoothed" function using lookup table

Question

If I want to write a function (probably also a class) which returns linearly "smoothed" data from an immutable lookup table (fixed when calling constructor) like this:

For example func(5.0) == 0.5.

---

1. What is the best way of storing the lookup table?

   • I am thinking of using two arrays.
   • Could there be other better ways?
      

2. What is the best way of calculating the required value? (In terms of real-time efficiency, excluding preparation time)

   • I am thinking of pre-sorting the lookup table on arg and using a binary search to find the nearest two points.
   • Or should I build a binary tree to simplify searching?
   • Or could there be other better ways?
      

3. (Minor) What would one call this kind of function/class/data-structure/algorithms? Is there any formal names for this in Computer Science?

I think I may need to write my own class. The class, at best, should be immutable because there is no need to change it after initialization and probably multiple threads will be using it. I may also need to get keys and values by the index.

Answer 1

Looks like you are trying to linearly interpolate a set of points. I'd use java.util.NavigableMap. It provides functions such as higherEntry(K key) and lowerEntry(K key) which facilitates getting the neighboring points.

You put into the map your (x,y)s. When queried for f(x_i), you'd first check if the mapping is contained in your map, if it is, return it. If not you'd call higherKey(x_i) and lowerKey(x_i) to find the neighboring two points. Then use the formula to interpolate those two points (see Wikipedia's Linear Interpolation Page).

I'd also implement the interpolation logic in a different class, and pass it in as a constructor argument to your function class in case you want to use different interpolation methods (i.e. polynomial interpolation) later.