lookup optimized version

[Jaroslav Hajek]

hello,
I have created an oct-file version of the "lookup" function currently
found in scripts/general/lookup.m,
that is used by several interpolation function.

The original lookup.m uses a clever "hack" algorithm of concatenating
the table and values
together, performing sort, and extracting the appropriate indices. As
noted in the original source,
the complexity is O((M+N)*log(M+N)), where M is the size of the table
and N the number of values,
(disregarding the fact that Octave's sort performs better on partially
sorted arrays).

My new version traverses the values being looked-up sequentially in a
single pass, and keeps
locating the right interval by binary bracketing followed by a binary
search. It is optimized for the
common case of downsampling an existing table onto a sorted (or nearly
sorted) denser grid.
The asymptotic complexity is O(N*log(M)) as noted in lookup.m, which
is thus faster for both
M >> N and N >> M cases.

I have also created a simple benchmark script to measure the speed-up effect.
In the pessimistic case when the values are completely random, the new
function is usually faster but
sometimes also slower (I've seen at most 30%), depending probably on
cache effects. In the almost
sorted and sorted case, as well as in the case of large table and
small amount of look-up values,
the oct-file version is much faster.

For example, on my Pentium-M 1.2GHz laptop, the m-version gives

bechmark lookup
table: 100000 sorted random numbers
y: 4000000 random numbers
y unsorted
Elapsed time is 6.16387 seconds.
y: nearly sorted (with fluctuations)
Elapsed time is 2.78983 seconds.
y: totally sorted
Elapsed time is 2.26132 seconds.

while the oct-version gives

bechmark lookup
table: 100000 sorted random numbers
y: 4000000 random numbers
y unsorted
Elapsed time is 1.40393 seconds.
y: nearly sorted (with fluctuations)
Elapsed time is 0.133232 seconds.
y: totally sorted
Elapsed time is 0.0783129 seconds.

can this function be included in Octave?


-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz

lookup.cc
Description: Text Data

bench_lookup.m
Description: Text Data