Generic solution for mapping values to array

Question

What is the common way to "map" arbitrary values (of within a certain range) to discrete values of an array?

Basically what I'd like to do is precompute a complex function x = f(x) for a range of discrete input values x and store each output value f(x) in another array fx, so that there are two vectors:

• x - discrete input values and
• fx - corresponding discrete output values

Now for an arbitrary value with the range of x I'd like to get the corrsponding output from fx, e. g. for a value x1 = 42 and vectors

x  = [ 30,  35,  40,  45,  50];
fx = [1.3, 1.8, 2.9, 4.5, 7.3];

the function possibly could return

1. fx1 = 4.5 - mapping to fx by taking x as an upper bound
2. fx1 = 2.9 - mapping to fx taking the nearest value from x
3. fx1 = 3.54 - mapping to fx doing a simple linearization
   
   • fx1 = fxa + (fxb-fxa)/(xb-xa) * (x1-xa)
   • fx1 = 2.9 + (4.5-2.9)/(45-40) * (42-40)

The function* should be really fast, as it substitutes the calling of the "real" function in a tight loop. A first try which is used to put into practive the case one of the upper listing is the following:

%% GET AT
% Retrieve f(x).
%
% * Synopsis: getAt (x, input_map, output_map)
% * Input   : x           - function input
%           : input_map   - array with precomputed input values
%           : output_map  - array with precomputed output values
%
% * Output  : fx          - function output
%                   
function fx = getAt (x, input_map, output_map)
    n = length(input_map);
    jj = length(find(input_map < x));

    if (jj >= n)
        fx = 0;
    else
        fx = output_map(jj+1);
    end
end

However I'm more looking for a C solution, because the loop also will be in C.

*.. Just looking for the way to do it not for a function as in language construct.

Answer 1

I would use linear interpolation (your solution 3) with constant extrapolation, i.e everything below 30 maps to 1.3 and everything beyond 50 to 7.3. The time-critical part will probably be finding the right array index.

The exact implementation depends on how big your sampled arrays are and on how your input values are distributed. For example:

• If your arrays are small or if you expect many values at the lower end of the input range, linear search may be fast enough.
• If your arrays are large and your input is evenly distributed over the range, binary search may be better.
• If your input samples are equidistant, lookup ist just one division with a floor function or integer conversion, so this may be the best approach.
• You could precalculate the slope of each segment in advance, so you don't have to calculate the constant (fxb-fxa)/(xb-xa) * (x1-xa) every time.

Lots of "mays". Profiling some implementations with your use case should help you decide how to implement your lookup function exactly.

Answer 2

Do a binary search on your x array to find either an exact match or the two entries that give an interval containing your input. For an exact match, the result is the corresponding (with the same index) fx element as the x element. For a non-exact match, do your linear interpolation based on where the input lies in the x0 ... x1 interval and apply that to the two corresponding fx elements. Alternatively to having two parallel arrays, you can have one array of elements that contain both the x and fx value.

There are numerous sources on the web for how to do a binary search of an array, e.g.,

Binary Search in Array

It's easy to adapt these to yield the correct pair of entries when there's no exact match. You have to be careful about the boundaries though ... input values less than the first element of the x array or greater than the last element.

You can also consider interpolation search:

http://en.wikipedia.org/wiki/Interpolation_search

rather than binary search since it requires linear interpolation between the low and high bounds anyway. Once you're down to just two x entries and haven't found an exact match, just apply the interpolation to the corresponding fx values.