octave-maintainers
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

binary lookup


From: John W. Eaton
Subject: binary lookup
Date: Thu, 13 Mar 2008 10:47:54 -0400

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);
    }

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

jwe


reply via email to

[Prev in Thread] Current Thread [Next in Thread]