binary lookup

[Jaroslav Hajek]

On Thu, Mar 13, 2008 at 3:47 PM, John W. Eaton <jwe at bevo.che.wisc.edu> wrote:
> On 13-Mar-2008, Jaroslav Hajek wrote:
>
>  | please consider applying the attached changeset. It implements a
>  | generic sequential binary lookup (optimized for dense downsampling)
>  | in liboctave/oct-lookup.h and wraps it in src/DLD-FUNCTIONS/lookup.cc
>  | instead of the current scripts/general/lookup.m which is implemented
>  | using sort. Also, the new lookup can search cell arrays of strings.
>  | At least one more DEFUN can benefit from including the algorithm in
>  | liboctave: DLD-FUNCTIONS/__lin_interpn__.cc. This is not part of this
>  | changeset - I'll create it later if this one is accepted.
>  |
>  | Also attached is the benchmark script I've used last time. With the
>  | improved sort the results are less impressive; still, in the optimized
>  | "dense downsampling" case there is an order of magnitude performance
>  | improvement (at least on my system).
>
>  | +              Cell y = argy.cell_value ();
>  | +              ArrayN<octave_idx_type> idx (y.dims ());
>  | +
>  | +              [...]
>  | +
>  | +              for (int i = 0; i < y.numel (); i++)
>  | +                {
>  | +                  octave_lookup (table.data (), table.length (),
>  | +                                 &y(i), 1, &idx(i),
>  | +                                 ov_str_comp, is_descending);
>  | +                }
>
>  I think this should use
>
>   const octave_value *py = y.data ();
>   const octave_idx_type *pidx = idx.fortran_vec ();
>
>   for (int i = 0; i < y.numel (); i++)
>     {
>       octave_lookup (table.data (), table.length (),
>                      &py[i], 1, &pidx[i],
>                      ov_str_comp, is_descending);
>     }
>

OK (except I think pidx should not be const)

>  Otherwise, I'm not familiar with this code, so someone else will have
>  to comment about whether this change should be included.
>
>  jwe
>

In any case, I think that at least the O(N) performance of current
lookup in a single (or several) lookup case is something that deserves
to be addressed (after all, it's listed as TODO in the current
implementation). Since there is at least one more DEFUN using lookup
(__lin_interpn__), I guess it's a good idea to move the algorithm into
liboctave somewhere.
What would be your preferred design of such a change?



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