Re: review needed: binary lookup

[Jaroslav Hajek]

On Thu, Mar 27, 2008 at 6:15 PM, John W. Eaton <address@hidden> wrote:
> On 27-Mar-2008, Jaroslav Hajek wrote:
>
>  | On Thu, Mar 27, 2008 at 12:00 PM, David Bateman
>  | <address@hidden> wrote:
>  | > Jaroslav Hajek wrote:
>  | >  > hello,
>  | >  >
>  | >  > I would like to implement a compiled binary search for Octave that
>  | >  > would replace the current lookup m-file implementation.
>  | >  > Dr. Eaton asked for an independent review of this code.
>  | >  >
>  | >  I avoided trying to comment on this code in the past as the existing
>  | >  lookup function isn't mine, but rather Paul Kienzle's ... However, I'd
>  | >  say that it makes sense to accelerate the lookup function as its needed
>  | >  for nearest and linear interpolation in all of the interpX functions and
>  | >  these are used relatively often... If the code passes all of the
>  | >  existing tests in use in the interpX functions, then I'd say accept it.
>  |
>  | David,
>  |
>  | I've followed your suggestion and tried these tests. Attached is a new 
> changeset
>  | that includes all the changes, i.e. the new lookup implementation
>  | (with 2 minor corrections) as well as corrected buggy lookup calls in
>  | interp1, interp2, interpn and ppval.
>  | I've also added a new test for the bug corrected by this change to 
> interp1.m.
>  | (`assert (interp1 ([3 2 1], [3 2 2], 2.5), 2.5)')
>
>  Will you please address the comments below and resubmit the patch?
>
>  | +  return
>  | +    std::upper_bound (table, table + size, val) - table;
>
>  To be consistent with the rest of the Octave sources, please write
>
>   return std::upper_bound (table, table + size, val) - table;
>
>  |
>  | +
>  | +// a unary functor that checks whether a value is outside [a,b) range
>  | +template<class T, class bpred>
>  | +class out_range : public std::unary_function<T, bool>
>  | +{
>  | +  T a, b;
>  | +  bpred comp;
>
>  Please use an explicit "private:" tag.  In the Octave sources, private
>  sections should normally appear last in the class declaration.  It's
>  also best if each private data member has a comment stating what it
>  is.  Though this is not always true, it would be good if more were
>  documented.
>
>  | +public:
>  | +  out_range (const T& aa, const T& bb, const bpred& ccomp)
>  | +    : a(aa), b(bb), comp(ccomp) {}
>  | +  inline bool operator() (const T& x)
>  | +    { return comp (x, a) || ! comp (x, b); }
>
>  I don't think inline is needed here since this declaration appears in
>  a header file.  Or is it?  If it is needed, then we should probably
>  mark more functions this way.  But I think compilers can inline these
>  functions without needing the hint, so I'd rather avoid the clutter.
>
>  | +  using namespace std;
>
>  In the Octave sources, we prefer to use explicit std:: tags.
>
>  | +// overload using < operator
>  | +template<typename T, typename bpred>
>  | +void seq_lookup (const T* table, octave_idx_type offset, octave_idx_type 
> size,
>
>  Please write
>
>   // overload using < operator
>   template<typename T, typename bpred>
>   void
>   seq_lookup (const T* table, octave_idx_type offset, octave_idx_type size,
>
>  so that the function name appears in the first column.  That way it is
>  easier to find function definitions by doing something like
>
>   grep ^function_name ...
>
>  | +
>  | +2008-03-17  Jaroslav Hajek <address@hidden>
>  | +
>  | +     * linear-algebra/subspace.m: New function.
>
>  This looks like a stray entry from another change..
>
>  | @@ -86,6 +86,8 @@
>  |  ##    check for proper table lengths
>  |  ## 2002-01-23 Paul Kienzle
>  |  ##    fixed extrapolation
>  | +## 2008-03-27 Jaroslav Hajek
>  | +##    fixed buggy lookup calls + added new test
>
>  We prefer to avoid adding comments like this.  Use the ChangeLog
>  instead.  Comments like this are usually present because the function
>  was originally part of Octave Forge and we normally don't remove them
>  when importing the function.
>
>  | diff -r b5731e43283a -r 0d6f5caf3209 scripts/general/lookup.m
>  | --- a/scripts/general/lookup.m        Wed Mar 26 23:01:16 2008 -0400
>  | +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
>  | @@ -1,100 +0,0 @@
>  | -## Copyright (C) 2000, 2006, 2007 Paul Kienzle
>  | -##
>
>  Did you run hg remove on this file?  If so, I think it is best to use
>  hg export -g so that this information shows up in your changeset.  I'd
>  recommend adding
>
>   [diff]
>   git = 1
>
>  to your ~/.hgrc file so you won't have to remember the -g option.
>
>  | +      if (icase)
>  | +        if (is_descending (table.data (), table.length (), ov_stri_less))
>  | +          ov_str_comp = ov_stri_greater;
>  | +        else
>  | +          ov_str_comp = ov_stri_less;
>  | +      else
>  | +        if (is_descending (table.data (), table.length (), ov_str_less))
>  | +          ov_str_comp = ov_str_greater;
>  | +        else
>  | +          ov_str_comp = ov_str_less;
>
>  To avoid possible confusion, please write
>
>   if (icase)
>     {
>       if (is_descending (table.data (), table.length (), ov_stri_less))
>         ov_str_comp = ov_stri_greater;
>       else
>         ov_str_comp = ov_stri_less;
>     }
>   else
>     {
>       if (is_descending (table.data (), table.length (), ov_str_less))
>         ov_str_comp = ov_str_greater;
>       else
>         ov_str_comp = ov_str_less;
>     }
>
>  Thanks,
>
>  jwe
>

OK, everything addressed. Please find the reworked patch attached.

regards,

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

binlookup.diff
Description: Text Data