[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: review needed: binary lookup
From: |
Jaroslav Hajek |
Subject: |
Re: review needed: binary lookup |
Date: |
Fri, 28 Mar 2008 07:39:02 +0100 |
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