[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
- binary lookup, Jaroslav Hajek, 2008/03/13
- binary lookup,
John W. Eaton <=