issorted & sortrows

[Jaroslav Hajek-2]

hi,

following the recent optimization of sort, I went ahead and
implemented issorted and optimized sortrows:

Summary of changes:
issorted is now supported (built-in). issorted(..., 'rows') also
works, except for sparse matrices.
The check uses no temporary arrays and is quite fast (inlined versions
in octave_sort).

sortrows is still an m-file. The old O(M*N*log(M) + M*N^2) algorithm
has been simply optimized to be O(M*N*log(M)).
The homogeneous case (whole matrix is sorted or all columns
identically oriented), is forwarded to a built-in implementation
(__sortrows_idx__) that uses an even more efficient breadth-first
tree-traversing algorithm, which I think is O(M*(N+log(M))).

To get an idea of the speed-up, here's a short benchmark:

# purely random array
n = 5e5;
a = randn (n, 10);
tic; b = sortrows (a); toc

# partially ordered array
for k = 1:100
  i = ceil (rand * (n-1));
  # swap randomly
  b = [b(j+1:end,:); b(1:j,:)];
endfor
tic; a = sortrows (b); toc

with a recent tip, I got:
Elapsed time is 1.62271 seconds.
Elapsed time is 1.62623 seconds.

whereas with the new tip, I get:

Elapsed time is 0.194896 seconds.
Elapsed time is 0.084264 seconds.

i.e. speed-ups by factors 8.3 and 19.3.

once again I'm wondering whether Matlab has an even better algorithm...

cheers

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

[John W. Eaton-3]

On 11-Feb-2009, Jaroslav Hajek wrote:

| following the recent optimization of sort, I went ahead and
| implemented issorted and optimized sortrows:

Your patch has

  diff --git a/liboctave/Array-C.cc b/liboctave/Array-C.cc
  --- a/liboctave/Array-C.cc
  +++ b/liboctave/Array-C.cc
  @@ -28,41 +28,79 @@
   // Instantiate Arrays of Complex values.

   #include "oct-cmplx.h"
  +#include "lo-mappers.h"

   #include "Array.h"
   #include "Array.cc"
   #include "oct-sort.cc"

  -static double
  -xabs (const Complex& x)
  +template <>
  +inline bool _sort_isnan (Complex x)
   {
  -  return (xisinf (x.real ()) || xisinf (x.imag ())) ? octave_Inf : abs (x);
  +  return xisnan (x);
   }

Why the change from "const Complex&" to "Complex"?  That means you are
copying the Complex data structure on each call.  I think this should
still be a call by const reference.

For Octave, please also use "x" as a prefix for functions like this
instead of "_".

   template <>
   bool
   octave_sort<Complex>::ascending_compare (Complex a, Complex b)
   {
  -  return (xisnan (b) || (xabs (a) < xabs (b))
  -  || ((xabs (a) == xabs (b)) && (arg (a) < arg (b))));
  +  return ((std::abs (a) < std::abs (b))
  +  || ((std::abs (a) == std::abs (b)) && (arg (a) < arg (b))));
   }

Apparently this was already call by value?  I think these arguments
should also be "const Complex&", not "Complex".

  +static bool nan_ascending_compare (Complex x, Complex y)
  +{
  +  return xisnan (y) ? ! xisnan (x) : ((std::abs (x) < std::abs (x))
  +  || ((std::abs (x) == std::abs (x)) && (arg (x) < arg (x))));
  +}

For consistency with the rest of the Octave sources, and so that

  grep ^FCN_NAME

will find function definitions (but not uses), please write

  static bool
  nan_ascending_compare (const Complex& x, const Complex& y)


+bool (*_sortrows_comparator (sortmode mode,
+                             const Array<Complex>& a , bool allow_chk))
+(Complex, Complex)
+{

This has me scratching my head.  Maybe a typedef would help here, so
you could write this as

  sortrows_comparator_function
  xsortrows_comparator (const Complex&, const Complex&)
  {

?  Or am I completely missing the point of this function signature?
If so, then I think a comment might help here, as this looks a little
obscure and is sure to confuse more people than just me.

jwe

[Jaroslav Hajek-2]

On Wed, Feb 11, 2009 at 4:02 PM, John W. Eaton <jwe@...> wrote:

> On 11-Feb-2009, Jaroslav Hajek wrote:
>
> | following the recent optimization of sort, I went ahead and
> | implemented issorted and optimized sortrows:
>
> Your patch has
>
>  diff --git a/liboctave/Array-C.cc b/liboctave/Array-C.cc
>  --- a/liboctave/Array-C.cc
>  +++ b/liboctave/Array-C.cc
>  @@ -28,41 +28,79 @@
>   // Instantiate Arrays of Complex values.
>
>   #include "oct-cmplx.h"
>  +#include "lo-mappers.h"
>
>   #include "Array.h"
>   #include "Array.cc"
>   #include "oct-sort.cc"
>
>  -static double
>  -xabs (const Complex& x)
>  +template <>
>  +inline bool _sort_isnan (Complex x)
>   {
>  -  return (xisinf (x.real ()) || xisinf (x.imag ())) ? octave_Inf : abs (x);
>  +  return xisnan (x);
>   }
>
> Why the change from "const Complex&" to "Complex"?  That means you are
> copying the Complex data structure on each call.  I think this should
> still be a call by const reference.
>

It's not really a change, because this is a completely different
function. Since it is marked inline and very simple, I think it will
be always inlined, so the speed should be the same. In fact
_sort_isnan is a purely convenience wrapper just to make the code in
Array.cc more generic. It will always either return constant true (if
a type has no NaN) or forward the call.

> For Octave, please also use "x" as a prefix for functions like this
> instead of "_".

I thought x was the prefix for mappers; this is something different.
But feel free to adjust the style wherever you wish.

>   template <>
>   bool
>   octave_sort<Complex>::ascending_compare (Complex a, Complex b)
>   {
>  -  return (xisnan (b) || (xabs (a) < xabs (b))
>  -       || ((xabs (a) == xabs (b)) && (arg (a) < arg (b))));
>  +  return ((std::abs (a) < std::abs (b))
>  +       || ((std::abs (a) == std::abs (b)) && (arg (a) < arg (b))));
>   }
>
> Apparently this was already call by value?  I think these arguments
> should also be "const Complex&", not "Complex".
>

Here, this is not so easily possible. The type of
octave_sort<T>::compare is bool (*) (T, T), not bool (*) (const T&,
const T&), so you'd get a type mismatch. The first form is probably
more suitable for simple built-in types, the latter for complex ones.
Supporting both would be possible but somewhat complicated.

>  +static bool nan_ascending_compare (Complex x, Complex y)
>  +{
>  +  return xisnan (y) ? ! xisnan (x) : ((std::abs (x) < std::abs (x))
>  +       || ((std::abs (x) == std::abs (x)) && (arg (x) < arg (x))));
>  +}
>
> For consistency with the rest of the Octave sources, and so that
>
>  grep ^FCN_NAME
>
> will find function definitions (but not uses), please write
>
>  static bool
>  nan_ascending_compare (const Complex& x, const Complex& y)
>

OK, sorry. I usually do this; however, this is again just a helper
function (that's why it's static).

>
> +bool (*_sortrows_comparator (sortmode mode,
> +                             const Array<Complex>& a , bool allow_chk))
> +(Complex, Complex)
> +{
>
> This has me scratching my head.  Maybe a typedef would help here, so
> you could write this as
>
>  sortrows_comparator_function
>  xsortrows_comparator (const Complex&, const Complex&)
>  {
>

Here, I simply copied the template from Array.cc

template<class T>
bool (*_sortrows_comparator (...))(T, T) { ... }

I don't think this syntax can be simplified without introducing a
traits class. For the specializations, one can introduce explicit
typedefs (like you have shown) but it seems to me that it obscures
somewhat the fact that it's a specialization (matching signatures).

> ?  Or am I completely missing the point of this function signature?
> If so, then I think a comment might help here, as this looks a little
> obscure and is sure to confuse more people than just me.
>

OK, a comment would help. It's just after working at octave_sort for a
few days it seemed natural to me :)

cheers


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

[Jaroslav Hajek-2]

On Wed, Feb 11, 2009 at 3:37 PM, Jaroslav Hajek <highegg@...> wrote:

> hi,
>
> following the recent optimization of sort, I went ahead and
> implemented issorted and optimized sortrows:
>
> Summary of changes:
> issorted is now supported (built-in). issorted(..., 'rows') also
> works, except for sparse matrices.
> The check uses no temporary arrays and is quite fast (inlined versions
> in octave_sort).
>
> sortrows is still an m-file. The old O(M*N*log(M) + M*N^2) algorithm
> has been simply optimized to be O(M*N*log(M)).
> The homogeneous case (whole matrix is sorted or all columns
> identically oriented), is forwarded to a built-in implementation
> (__sortrows_idx__) that uses an even more efficient breadth-first
> tree-traversing algorithm, which I think is O(M*(N+log(M))).
>
> To get an idea of the speed-up, here's a short benchmark:
>
> # purely random array
> n = 5e5;
> a = randn (n, 10);
> tic; b = sortrows (a); toc
>
> # partially ordered array
> for k = 1:100
>  i = ceil (rand * (n-1));
>  # swap randomly
>  b = [b(j+1:end,:); b(1:j,:)];
> endfor
> tic; a = sortrows (b); toc
>
> with a recent tip, I got:
> Elapsed time is 1.62271 seconds.
> Elapsed time is 1.62623 seconds.
>
> whereas with the new tip, I get:
>
> Elapsed time is 0.194896 seconds.
> Elapsed time is 0.084264 seconds.
>
> i.e. speed-ups by factors 8.3 and 19.3.
>
> once again I'm wondering whether Matlab has an even better algorithm...
>

OK I just realized this benchmark is not really much realistic, as the
first column is almost enough to determine ordering.
Rounding to just 100 random values is somewhat better:

# purely random array
n = 5e5;
a = round (100*rand (n, 10));
tic; b = sortrows (a); toc

# partially ordered array
for k = 1:100
  i = ceil (rand * (n-1));
  # swap randomly
  b = [b(j+1:end,:); b(1:j,:)];
endfor
tic; a = sortrows (b); toc

and the times:

Elapsed time is 1.42739 seconds.
Elapsed time is 1.41714 seconds.

vs.

Elapsed time is 0.273507 seconds.
Elapsed time is 0.114233 seconds.

here, speedups are slightly smaller but still significant.

cheers

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

[John W. Eaton-3]

On 11-Feb-2009, Jaroslav Hajek wrote:

| Here, this is not so easily possible. The type of
| octave_sort<T>::compare is bool (*) (T, T), not bool (*) (const T&,
| const T&), so you'd get a type mismatch. The first form is probably
| more suitable for simple built-in types, the latter for complex ones.
| Supporting both would be possible but somewhat complicated.

I don't see why it shouldn't use "const T&".  Doing that shouldn't
cause trouble for built-in types, and has some advantage for aggregate
types like Complex or some other class or structure that we may use
later.  I don't understand why it was ever defined to just use T.

jwe

[John W. Eaton-3]

On 11-Feb-2009, Jaroslav Hajek wrote:

| On Wed, Feb 11, 2009 at 4:02 PM, John W. Eaton <jwe@...> wrote:
|
| > +bool (*_sortrows_comparator (sortmode mode,
| > +                             const Array<Complex>& a , bool allow_chk))
| > +(Complex, Complex)
| > +{
| >
| > This has me scratching my head.  Maybe a typedef would help here, so
| > you could write this as
| >
| >  sortrows_comparator_function
| >  xsortrows_comparator (const Complex&, const Complex&)
| >  {
| >
|
| Here, I simply copied the template from Array.cc
|
| template<class T>
| bool (*_sortrows_comparator (...))(T, T) { ... }
|
| I don't think this syntax can be simplified without introducing a
| traits class. For the specializations, one can introduce explicit
| typedefs (like you have shown) but it seems to me that it obscures
| somewhat the fact that it's a specialization (matching signatures).

I don't see why a traits class is needed.  Won't something like the
following work?

  diff --git a/liboctave/Array-d.cc b/liboctave/Array-d.cc
  --- a/liboctave/Array-d.cc
  +++ b/liboctave/Array-d.cc
  @@ -52,11 +52,10 @@
     return lo_ieee_isnan (x) ? ! lo_ieee_isnan (y) : x > y;
   }

  -bool (*_sortrows_comparator (sortmode mode,
  -                             const Array<double>& a , bool allow_chk))
  -(double, double)
  +octave_sort<double>::compare_fcn_type
  +_sortrows_comparator (sortmode mode, const Array<double>& a , bool allow_chk)
   {
  -  bool (*result) (double, double) = 0;
  +  octave_sort<double>::compare_fcn_type result = 0;

     if (allow_chk)
       {
  diff --git a/liboctave/oct-sort.h b/liboctave/oct-sort.h
  --- a/liboctave/oct-sort.h
  +++ b/liboctave/oct-sort.h
  @@ -135,6 +135,8 @@

     static bool ascending_compare (T, T);
     static bool descending_compare (T, T);
  +
  +  typedef bool (*compare_fcn_type) (T, T);

   private:


It seems much clearer to have a typedef like this and be able to write
the function as

  octave_sort<double>::compare_fcn_type
  _sortrows_comparator (sortmode mode, const Array<double>& a , bool allow_chk)
  {
    octave_sort<double>::compare_fcn_type result = 0;
    ...

instead of

  bool (*_sortrows_comparator (sortmode mode,
                              const Array<double>& a , bool allow_chk))
  (double, double)
  {
    bool (*result) (double, double) = 0;
    ...

I now see I had it wrong in my earlier message because I was having
trouble deciphering the declaration.

If you don't like mixing the octave_sort and Array classes for this,
then I think you can put the typedef in the Array class instead.

BTW, why isn't _sortrows_comparator a member of the Array class?

jwe

[Jaroslav Hajek-2]

On Wed, Feb 11, 2009 at 7:29 PM, John W. Eaton <jwe@...> wrote:

> On 11-Feb-2009, Jaroslav Hajek wrote:
>
> | Here, this is not so easily possible. The type of
> | octave_sort<T>::compare is bool (*) (T, T), not bool (*) (const T&,
> | const T&), so you'd get a type mismatch. The first form is probably
> | more suitable for simple built-in types, the latter for complex ones.
> | Supporting both would be possible but somewhat complicated.
>
> I don't see why it shouldn't use "const T&".  Doing that shouldn't
> cause trouble for built-in types, and has some advantage for aggregate
> types like Complex or some other class or structure that we may use
> later.  I don't understand why it was ever defined to just use T.
>

Apparently it was David who did it; presumably because he thought it'd
be faster for the simple types. Now, because for the simple types the
comparison is inlined anyway, even this vague reason is probably gone,
so I'm all for changing that to const T&, const T&, presumably
together with a typedef inside octave_sort (as suggested in the
following mail).

If you  want to do it, please go ahead, otherwise I'll do it in near future.

regards

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

[dbateman2]

Jaroslav Hajek wrote:

> On Wed, Feb 11, 2009 at 7:29 PM, John W. Eaton <jwe@...> wrote:
>  
>> On 11-Feb-2009, Jaroslav Hajek wrote:
>>
>> | Here, this is not so easily possible. The type of
>> | octave_sort<T>::compare is bool (*) (T, T), not bool (*) (const T&,
>> | const T&), so you'd get a type mismatch. The first form is probably
>> | more suitable for simple built-in types, the latter for complex ones.
>> | Supporting both would be possible but somewhat complicated.
>>
>> I don't see why it shouldn't use "const T&".  Doing that shouldn't
>> cause trouble for built-in types, and has some advantage for aggregate
>> types like Complex or some other class or structure that we may use
>> later.  I don't understand why it was ever defined to just use T.
>>
>>    
>
> Apparently it was David who did it; presumably because he thought it'd
> be faster for the simple types. Now, because for the simple types the
> comparison is inlined anyway, even this vague reason is probably gone,
> so I'm all for changing that to const T&, const T&, presumably
> together with a typedef inside octave_sort (as suggested in the
> following mail).
>
> If you  want to do it, please go ahead, otherwise I'll do it in near future.
>  

Hey its a few years back that I did this so all I can say is that you
are probably right on the reason..

D.


--
David Bateman                                dbateman@...
35 rue Gambetta                              [phone] (Home)
92100 Boulogne-Billancourt FRANCE            [phone] (Mob)

[John W. Eaton-3]

On 11-Feb-2009, David Bateman wrote:

| Jaroslav Hajek wrote:
| > On Wed, Feb 11, 2009 at 7:29 PM, John W. Eaton <jwe@...> wrote:
| >  
| >> On 11-Feb-2009, Jaroslav Hajek wrote:
| >>
| >> | Here, this is not so easily possible. The type of
| >> | octave_sort<T>::compare is bool (*) (T, T), not bool (*) (const T&,
| >> | const T&), so you'd get a type mismatch. The first form is probably
| >> | more suitable for simple built-in types, the latter for complex ones.
| >> | Supporting both would be possible but somewhat complicated.
| >>
| >> I don't see why it shouldn't use "const T&".  Doing that shouldn't
| >> cause trouble for built-in types, and has some advantage for aggregate
| >> types like Complex or some other class or structure that we may use
| >> later.  I don't understand why it was ever defined to just use T.
| >>
| >>    
| >
| > Apparently it was David who did it; presumably because he thought it'd
| > be faster for the simple types. Now, because for the simple types the
| > comparison is inlined anyway, even this vague reason is probably gone,
| > so I'm all for changing that to const T&, const T&, presumably
| > together with a typedef inside octave_sort (as suggested in the
| > following mail).
| >
| > If you  want to do it, please go ahead, otherwise I'll do it in near future.
| >  
| Hey its a few years back that I did this so all I can say is that you
| are probably right on the reason..

OK.  I checked in the following changeset that uses some template
magic to allow us to use "T const&" for the parameters of these
functions if T is a class type, and to use "T" if T is not a class
type.  It also simplifies some declarations with typedefs and removes
the strange comparison functions for octave_value objects from the
src/TEMPLATE-INST/Array-tc.cc file.

  http://hg.savannah.gnu.org/hgweb/octave/rev/d5af326a3ede

jwe

[Jaroslav Hajek-2]

On Thu, Feb 12, 2009 at 9:02 AM, John W. Eaton <jwe@...> wrote:

> On 11-Feb-2009, David Bateman wrote:
>
> | Jaroslav Hajek wrote:
> | > On Wed, Feb 11, 2009 at 7:29 PM, John W. Eaton <jwe@...> wrote:
> | >
> | >> On 11-Feb-2009, Jaroslav Hajek wrote:
> | >>
> | >> | Here, this is not so easily possible. The type of
> | >> | octave_sort<T>::compare is bool (*) (T, T), not bool (*) (const T&,
> | >> | const T&), so you'd get a type mismatch. The first form is probably
> | >> | more suitable for simple built-in types, the latter for complex ones.
> | >> | Supporting both would be possible but somewhat complicated.
> | >>
> | >> I don't see why it shouldn't use "const T&".  Doing that shouldn't
> | >> cause trouble for built-in types, and has some advantage for aggregate
> | >> types like Complex or some other class or structure that we may use
> | >> later.  I don't understand why it was ever defined to just use T.
> | >>
> | >>
> | >
> | > Apparently it was David who did it; presumably because he thought it'd
> | > be faster for the simple types. Now, because for the simple types the
> | > comparison is inlined anyway, even this vague reason is probably gone,
> | > so I'm all for changing that to const T&, const T&, presumably
> | > together with a typedef inside octave_sort (as suggested in the
> | > following mail).
> | >
> | > If you  want to do it, please go ahead, otherwise I'll do it in near future.
> | >
> | Hey its a few years back that I did this so all I can say is that you
> | are probably right on the reason..
>
> OK.  I checked in the following changeset that uses some template
> magic to allow us to use "T const&" for the parameters of these
> functions if T is a class type, and to use "T" if T is not a class
> type.  It also simplifies some declarations with typedefs and removes
> the strange comparison functions for octave_value objects from the
> src/TEMPLATE-INST/Array-tc.cc file.
>
>  http://hg.savannah.gnu.org/hgweb/octave/rev/d5af326a3ede
>
> jwe
>

Just when I was compiling my own version ... :)
But yours is better - I've been long missing lo-traits.h, I just
lacked the courage to create it (my version puts the traits to
oct-sort.h). I guess maybe some of the stuff inside oct-inttypes.h can
be moved here, so I'll abandon my version.


cheers

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

[John W. Eaton-3]

On 12-Feb-2009, Jaroslav Hajek wrote:

| On Thu, Feb 12, 2009 at 9:02 AM, John W. Eaton <jwe@...> wrote:
|
| > removes
| > the strange comparison functions for octave_value objects from the
| > src/TEMPLATE-INST/Array-tc.cc file.
|
| Just when I was compiling my own version ... :)
| But yours is better - I've been long missing lo-traits.h, I just
| lacked the courage to create it (my version puts the traits to
| oct-sort.h). I guess maybe some of the stuff inside oct-inttypes.h can
| be moved here, so I'll abandon my version.

OK.

I had to undo the part of my change that removed the strange
comparison functions for octave_value objects from the
src/TEMPLATE-INST/Array-tc.cc file because without them I was reliably
seeing

  src/data.cc ............................................error: `pso' undefined near line 252 column 23
error: evaluating argument list element number 1
error: evaluating argument list element number 1
error: called from:
error:   /home/jwe/src/octave/test/fntests.m at line 252, column 3

but make check succeeds with them.  I added a FIXME in this file
because these functions just seem wrong:

  // FIXME -- these comparisons don't look right.  Where do we sort
  // octave_value objects and expect them to be character strings?

  template <>
  bool
  octave_sort<octave_value>::ascending_compare (const octave_value& a, const octave_value& b)
  {
    return (a.string_value () < b.string_value ());
  }

  template <>
  bool
  octave_sort<octave_value>::descending_compare (const octave_value& a, const octave_value& b)
  {
    return (a.string_value () > b.string_value ());
  }

I don't see where they are used.  Does anyone have some clues for me?

jwe

[Jaroslav Hajek-2]

On Thu, Feb 12, 2009 at 9:54 AM, John W. Eaton <jwe@...> wrote:

> On 12-Feb-2009, Jaroslav Hajek wrote:
>
> | On Thu, Feb 12, 2009 at 9:02 AM, John W. Eaton <jwe@...> wrote:
> |
> | > removes
> | > the strange comparison functions for octave_value objects from the
> | > src/TEMPLATE-INST/Array-tc.cc file.
> |
> | Just when I was compiling my own version ... :)
> | But yours is better - I've been long missing lo-traits.h, I just
> | lacked the courage to create it (my version puts the traits to
> | oct-sort.h). I guess maybe some of the stuff inside oct-inttypes.h can
> | be moved here, so I'll abandon my version.
>
> OK.
>
> I had to undo the part of my change that removed the strange
> comparison functions for octave_value objects from the
> src/TEMPLATE-INST/Array-tc.cc file because without them I was reliably
> seeing
>
>  src/data.cc ............................................error: `pso' undefined near line 252 column 23
> error: evaluating argument list element number 1
> error: evaluating argument list element number 1
> error: called from:
> error:   /home/jwe/src/octave/test/fntests.m at line 252, column 3
>
> but make check succeeds with them.  I added a FIXME in this file
> because these functions just seem wrong:
>
>  // FIXME -- these comparisons don't look right.  Where do we sort
>  // octave_value objects and expect them to be character strings?
>
>  template <>
>  bool
>  octave_sort<octave_value>::ascending_compare (const octave_value& a, const octave_value& b)
>  {
>    return (a.string_value () < b.string_value ());
>  }
>
>  template <>
>  bool
>  octave_sort<octave_value>::descending_compare (const octave_value& a, const octave_value& b)
>  {
>    return (a.string_value () > b.string_value ());
>  }
>
> I don't see where they are used.  Does anyone have some clues for me?
>
> jwe
>

I think these are used for sorting cell arrays.


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

[dbateman]

Jaroslav Hajek-2 wrote:

On Thu, Feb 12, 2009 at 9:54 AM, John W. Eaton <[e-mail]> wrote:
> On 12-Feb-2009, Jaroslav Hajek wrote:
>
> | On Thu, Feb 12, 2009 at 9:02 AM, John W. Eaton <[e-mail]> wrote:
> |
> | > removes
> | > the strange comparison functions for octave_value objects from the
> | > src/TEMPLATE-INST/Array-tc.cc file.
> |
> | Just when I was compiling my own version ... :)
> | But yours is better - I've been long missing lo-traits.h, I just
> | lacked the courage to create it (my version puts the traits to
> | oct-sort.h). I guess maybe some of the stuff inside oct-inttypes.h can
> | be moved here, so I'll abandon my version.
>
> OK.
>
> I had to undo the part of my change that removed the strange
> comparison functions for octave_value objects from the
> src/TEMPLATE-INST/Array-tc.cc file because without them I was reliably
> seeing
>
>  src/data.cc ............................................error: `pso' undefined near line 252 column 23
> error: evaluating argument list element number 1
> error: evaluating argument list element number 1
> error: called from:
> error:   /home/jwe/src/octave/test/fntests.m at line 252, column 3
>
> but make check succeeds with them.  I added a FIXME in this file
> because these functions just seem wrong:
>
>  // FIXME -- these comparisons don't look right.  Where do we sort
>  // octave_value objects and expect them to be character strings?
>
>  template <>
>  bool
>  octave_sort<octave_value>::ascending_compare (const octave_value& a, const octave_value& b)
>  {
>    return (a.string_value () < b.string_value ());
>  }
>
>  template <>
>  bool
>  octave_sort<octave_value>::descending_compare (const octave_value& a, const octave_value& b)
>  {
>    return (a.string_value () > b.string_value ());
>  }
>
> I don't see where they are used.  Does anyone have some clues for me?
>
> jwe
>

I think these are used for sorting cell arrays.


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

I confirm that they are used to sort cell string arrays

D.

[John W. Eaton-3]

On 12-Feb-2009, dbateman wrote:

| Jaroslav Hajek-2 wrote:
|
| > I think these are used for sorting cell arrays.
|
| I confirm that they are used to sort cell string arrays

OK, I checked in the following change:

  http://hg.savannah.gnu.org/hgweb/octave/rev/a669df7beb73

(sorry about the useless hg log message).  This change restricts
sorting on cell arrays to cell arrays of strings only, by implementing
octave_cell::sort and octave_cell::sortrows_idx methods that ensure
that the cell array contains only strings, and then converts the array
of octave_value objects to an array of std::string objects before
doing the sort, then creates a new .  It might be good to have a way
to avoid doing the conversion if the array is already sorted, but I
don't see a way to do that since the is_sorted functions always seem
to examine the values.  Would it be worth caching the sort mode in the
Array?  When creating a cell from an Array<std::string> object, we
could copy the sort mode as well, then the octave_cell::sort function
could skip the sort without having to first convert the
Array<octave_value> object to an Array<std::string> object.

Does that make sense?  Does it seem worth the effort?

jwe

[Jaroslav Hajek-2]

On Thu, Feb 12, 2009 at 9:10 PM, John W. Eaton <jwe@...> wrote:

> On 12-Feb-2009, dbateman wrote:
>
> | Jaroslav Hajek-2 wrote:
> |
> | > I think these are used for sorting cell arrays.
> |
> | I confirm that they are used to sort cell string arrays
>
> OK, I checked in the following change:
>
>  http://hg.savannah.gnu.org/hgweb/octave/rev/a669df7beb73
>
> (sorry about the useless hg log message).  This change restricts
> sorting on cell arrays to cell arrays of strings only, by implementing
> octave_cell::sort and octave_cell::sortrows_idx methods that ensure
> that the cell array contains only strings, and then converts the array
> of octave_value objects to an array of std::string objects before
> doing the sort, then creates a new .  It might be good to have a way
> to avoid doing the conversion if the array is already sorted, but I
> don't see a way to do that since the is_sorted functions always seem
> to examine the values.  Would it be worth caching the sort mode in the
> Array?  When creating a cell from an Array<std::string> object, we
> could copy the sort mode as well, then the octave_cell::sort function
> could skip the sort without having to first convert the
> Array<octave_value> object to an Array<std::string> object.
>
> Does that make sense?  Does it seem worth the effort?
>
> jwe
>

Here's a different suggestion: given the fact that cells are often
used as cells of strings, maybe we could cache the cellstr value in
Cell, and invalidate it on modifications? (or check for string
modifications)?
This may be useful for more built-in functions operating on cell
arrays of strings.

cheers

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