Mercurial > hg > octave-lojdl
changeset 10114:e4936c129cbd
optimize sorting of bools
author | Jaroslav Hajek <highegg@gmail.com> |
---|---|
date | Fri, 15 Jan 2010 08:57:07 +0100 |
parents | 5aff7f14aa7f |
children | ed49cef7e005 |
files | liboctave/Array-b.cc liboctave/ChangeLog |
diffstat | 2 files changed, 79 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/liboctave/Array-b.cc +++ b/liboctave/Array-b.cc @@ -29,8 +29,81 @@ #include "Array.h" #include "Array.cc" +#define INLINE_ASCENDING_SORT +#define INLINE_DESCENDING_SORT #include "oct-sort.cc" +// Specialize bool sorting (aka stable partitioning). + +template<bool desc> +static void do_bool_partition (bool *data, octave_idx_type nel) +{ + octave_idx_type k = 0; + for (octave_idx_type i = 0; i < nel; i++) + if (data[i] == desc) + data[k++] = desc; + for (octave_idx_type i = k; i < nel; i++) + data[i] = ! desc; +} + +template<bool desc> +static void do_bool_partition (bool *data, octave_idx_type *idx, + octave_idx_type nel) +{ + // FIXME: This is essentially a simple bucket sort. + // Can it be efficiently done by std::partition? + OCTAVE_LOCAL_BUFFER (octave_idx_type, jdx, nel); + octave_idx_type k = 0, l = 0; + for (octave_idx_type i = 0; i < nel; i++) + { + if (data[i] == desc) + { + data[k] = desc; + idx[k++] = idx[i]; + } + else + jdx[l++] = idx[i]; + } + + for (octave_idx_type i = k; i < nel; i++) + { + data[i] = ! desc; + idx[i] = jdx[i-k]; + } +} + +template <> template <> +void +octave_sort<bool>::sort (bool *data, octave_idx_type nel, + std::less<bool>) +{ + do_bool_partition<false> (data, nel); +} + +template <> template <> +void +octave_sort<bool>::sort (bool *data, octave_idx_type nel, + std::greater<bool>) +{ + do_bool_partition<true> (data, nel); +} + +template <> template <> +void +octave_sort<bool>::sort (bool *data, octave_idx_type *idx, octave_idx_type nel, + std::less<bool>) +{ + do_bool_partition<false> (data, idx, nel); +} + +template <> template <> +void +octave_sort<bool>::sort (bool *data, octave_idx_type *idx, octave_idx_type nel, + std::greater<bool>) +{ + do_bool_partition<true> (data, idx, nel); +} + INSTANTIATE_ARRAY_SORT (bool); INSTANTIATE_ARRAY (bool, OCTAVE_API);
--- a/liboctave/ChangeLog +++ b/liboctave/ChangeLog @@ -1,3 +1,9 @@ +2010-01-15 Jaroslav Hajek <highegg@gmail.com> + + * Array-b.cc: Inline ascending and descending sort. + (do_bool_partition): New helper template function. + (octave_sort<bool>::sort): Provide specializations. + 2010-01-14 Jaroslav Hajek <highegg@gmail.com> * Array.cc (Array<T>::insert (const Array<T>&, const