Re: review needed: binary lookup

[John W. Eaton]

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