Mercurial > hg > octave-nkf
changeset 9922:3a8327d51ed4
optimize issorted for doubles & floats
author | Jaroslav Hajek <highegg@gmail.com> |
---|---|
date | Sat, 05 Dec 2009 21:30:47 +0100 |
parents | 7c8392a034e6 |
children | 31d644253380 |
files | liboctave/Array-d.cc liboctave/Array-f.cc liboctave/ChangeLog |
diffstat | 3 files changed, 145 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/liboctave/Array-d.cc +++ b/liboctave/Array-d.cc @@ -84,6 +84,76 @@ return result; } +// The default solution using NaN-safe comparator is OK, but almost twice as +// slow than this code. +template <> +sortmode +Array<double>::is_sorted (sortmode mode) const +{ + octave_idx_type n = numel (); + + const double *el = data (); + + if (n <= 1) + return mode ? mode : ASCENDING; + + if (! mode) + { + // Auto-detect mode. + if (el[n-1] < el[0] || xisnan (el[0])) + mode = DESCENDING; + else + mode = ASCENDING; + } + + if (mode == DESCENDING) + { + octave_idx_type j = 0; + double r; + // Sort out NaNs. + do + r = el[j++]; + while (xisnan (r) && j < n); + + // Orient the test so that NaN will not pass through. + for (; j < n; j++) + { + if (r >= el[j]) + r = el[j]; + else + { + mode = UNSORTED; + break; + } + } + + } + else if (mode == ASCENDING) + { + // Sort out NaNs. + while (n > 0 && xisnan (el[n-1])) + n--; + + if (n > 0) + { + // Orient the test so that NaN will not pass through. + double r = el[0]; + for (octave_idx_type j = 1; j < n; j++) + { + if (r <= el[j]) + r = el[j]; + else + { + mode = UNSORTED; + break; + } + } + } + } + + return mode; +} + INSTANTIATE_ARRAY_SORT (double); INSTANTIATE_ARRAY (double, OCTAVE_API);
--- a/liboctave/Array-f.cc +++ b/liboctave/Array-f.cc @@ -84,6 +84,76 @@ return result; } +// The default solution using NaN-safe comparator is OK, but almost twice as +// slow than this code. +template <> +sortmode +Array<float>::is_sorted (sortmode mode) const +{ + octave_idx_type n = numel (); + + const float *el = data (); + + if (n <= 1) + return mode ? mode : ASCENDING; + + if (! mode) + { + // Auto-detect mode. + if (el[n-1] < el[0] || xisnan (el[0])) + mode = DESCENDING; + else + mode = ASCENDING; + } + + if (mode == DESCENDING) + { + octave_idx_type j = 0; + float r; + // Sort out NaNs. + do + r = el[j++]; + while (xisnan (r) && j < n); + + // Orient the test so that NaN will not pass through. + for (; j < n; j++) + { + if (r >= el[j]) + r = el[j]; + else + { + mode = UNSORTED; + break; + } + } + + } + else if (mode == ASCENDING) + { + // Sort out NaNs. + while (n > 0 && xisnan (el[n-1])) + n--; + + if (n > 0) + { + // Orient the test so that NaN will not pass through. + float r = el[0]; + for (octave_idx_type j = 1; j < n; j++) + { + if (r <= el[j]) + r = el[j]; + else + { + mode = UNSORTED; + break; + } + } + } + } + + return mode; +} + INSTANTIATE_ARRAY_SORT (float); INSTANTIATE_ARRAY (float, OCTAVE_API);
--- a/liboctave/ChangeLog +++ b/liboctave/ChangeLog @@ -1,3 +1,8 @@ +2009-12-05 Jaroslav Hajek <highegg@gmail.com> + + * Array-d.cc (Array<double>::is_sorted): Optimized specialization. + * Array-f.cc (Array<float>::is_sorted): Ditto. + 2009-12-05 Jaroslav Hajek <highegg@gmail.com> * oct-sort.cc (lookup_binary): Remove.