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

fx1 = 4.5 - mapping to fx by taking x as an upper bound
fx1 = 2.9 - mapping to fx taking the nearest value from x
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.

Note: IMO the equivalent mathematical form = (fxa*xb - fxb*xa + (fxb-fxa)*x1)/(xb-xa) to fxa + (fxb-fxa)/(xb-xa) * (x1-xa) (approach #3) is computationally more stable. To make the "The function* should be really fast", code could add 2 pre-computed fields: slope (fxb-fxa)/(xb-xa) and offset (fxa*xb - fxb*xa)/(xb-xa), then use fx1 = slope*x1 + offset. — chux
– chux, Commented Sep 13, 2014 at 12:51
@chux Why is it more stable? The pre-computation works, even though I not yet figured out completely how. — embert
– embert, Commented Sep 15, 2014 at 6:47
@luismendo I'did. For general purpose interp1 is fine, for specific task, however, a self made function can be significantly faster even if implemented in matlab. — embert
– embert, Commented Oct 21, 2014 at 12:35

M Oehm · Accepted Answer · 2014-09-13 06:39:55Z

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.

answered Sep 13, 2014 at 6:39

M Oehm

29.2k3 gold badges36 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

embert Over a year ago

I wrote a binary and interpolation search in matlab and made a test with evenly distributed queries on an evenly distributed array x. Interpolation was in average about 8 times faster, i. e. a single query on that array of 1k elements took 14 us / 108 us (Int vs Bin). Only then I recognized as you suggest in #3 that if the values are equidistant the index can be retrieved by the step and offset. Concerning integer conversion or floor division: Any recommendation? Would converting 3.6 to int result in 4? That would give the nearest index in one step then, right?

embert Over a year ago

Come to think of it since the functions are mapped prior to a big deeply nested loop (depth: 4) it is better to map equidistant inputs and do division by step width + truncation. Even if that requires to map more input values (provided the distribution is more or less constant), it outweights searching an array by far.

Community · Accepted Answer · 2017-05-23 10:33:37Z

1

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.

edited May 23, 2017 at 10:33

CommunityBot

11 silver badge

answered Sep 13, 2014 at 6:44

Jim Balter

16.5k3 gold badges46 silver badges70 bronze badges

2 Comments

Jens Gustedt Over a year ago

The easiest way to get binary search started is probably just to use the C library function that implements it, bsearch.

Jim Balter Over a year ago

@JensGustedt Er, no. Aside from that being grossly inefficient whereas the OP is looking for speed, it doesn't give any result when there's no exact match. You seem to have made no effort to read or understand what I wrote: "It's easy to adapt these to yield the correct pair of entries when there's no exact match" ... obviously there's no way to do that with bsearch. And the goal here isn't to "get binary search started", it's to address the OP's problem.

Collectives™ on Stack Overflow

Generic solution for mapping values to array

2 Answers 2

2 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related