Mercurial > hg > octave-terminal
changeset 10339:de2d43bcb083
optimize some lazy index operations
author | Jaroslav Hajek <highegg@gmail.com> |
---|---|
date | Fri, 19 Feb 2010 11:47:47 +0100 |
parents | 21dd58bd683c |
children | 36317747577a |
files | liboctave/ChangeLog liboctave/idx-vector.cc liboctave/idx-vector.h src/ChangeLog src/ov-lazy-idx.cc src/ov-lazy-idx.h src/ov-re-mat.cc src/ov-re-mat.h |
diffstat | 8 files changed, 259 insertions(+), 31 deletions(-) [+] |
line wrap: on
line diff
--- a/liboctave/ChangeLog +++ b/liboctave/ChangeLog @@ -1,3 +1,11 @@ +2010-02-19 Jaroslav Hajek <highegg@gmail.com> + + * idx-vector.cc (idx_vector::as_array, + idx_vector::idx_range_rep::as_array, + idx_vector::idx_scalar_rep::as_array, + idx_vector::idx_vector_rep::as_array): New methods. + * idx-vector.h: Declare them. + 2010-02-17 John W. Eaton <jwe@octave.org> * oct-rand.cc: Include <sdint.h>. Change declarations of ranlib
--- a/liboctave/idx-vector.cc +++ b/liboctave/idx-vector.cc @@ -62,6 +62,15 @@ ("internal error: idx_vector index out of range."); } +Array<octave_idx_type> +idx_vector::idx_base_rep::as_array (void) +{ + (*current_liboctave_error_handler) + ("internal error: as_array not allowed for this index class."); + + return Array<octave_idx_type> (); +} + DEFINE_OCTAVE_ALLOCATOR(idx_vector::idx_colon_rep); idx_vector::idx_colon_rep::idx_colon_rep (char c) @@ -207,6 +216,16 @@ static_cast<double> (step), len); } +Array<octave_idx_type> +idx_vector::idx_range_rep::as_array (void) +{ + Array<octave_idx_type> retval (dim_vector (1, len)); + for (octave_idx_type i = 0; i < len; i++) + retval.xelem (i) = start + len*step; + + return retval; +} + inline octave_idx_type convert_index (octave_idx_type i, bool& conv_error, octave_idx_type& ext) @@ -289,6 +308,12 @@ return data + 1; } +Array<octave_idx_type> +idx_vector::idx_scalar_rep::as_array (void) +{ + return Array<octave_idx_type> (dim_vector (1, 1), data); +} + DEFINE_OCTAVE_ALLOCATOR(idx_vector::idx_vector_rep); template <class T> @@ -592,6 +617,23 @@ return retval; } +Array<octave_idx_type> +idx_vector::idx_vector_rep::as_array (void) +{ + if (aowner) + return *aowner; + else + { + Array<octave_idx_type> retval (orig_dims); + std::memcpy (retval.fortran_vec (), data, len*sizeof (octave_idx_type)); + // Delete the old copy and share the data instead to save memory. + delete [] data; + data = retval.fortran_vec (); + aowner = new Array<octave_idx_type> (retval); + return retval; + } +} + DEFINE_OCTAVE_ALLOCATOR(idx_vector::idx_mask_rep); idx_vector::idx_mask_rep::idx_mask_rep (bool b) @@ -1095,6 +1137,12 @@ } } +Array<octave_idx_type> +idx_vector::as_array (void) const +{ + return rep->as_array (); +} + octave_idx_type idx_vector::freeze (octave_idx_type z_len, const char *, bool resize_ok) {
--- a/liboctave/idx-vector.h +++ b/liboctave/idx-vector.h @@ -103,6 +103,8 @@ // i/o virtual std::ostream& print (std::ostream& os) const = 0; + virtual Array<octave_idx_type> as_array (void); + int count; bool err; @@ -203,6 +205,8 @@ Range unconvert (void) const; + Array<octave_idx_type> as_array (void); + private: DECLARE_OCTAVE_ALLOCATOR @@ -260,6 +264,8 @@ double unconvert (void) const; + Array<octave_idx_type> as_array (void); + private: DECLARE_OCTAVE_ALLOCATOR @@ -327,6 +333,8 @@ Array<double> unconvert (void) const; + Array<octave_idx_type> as_array (void); + private: DECLARE_OCTAVE_ALLOCATOR @@ -970,6 +978,8 @@ void unconvert (idx_class_type& iclass, double& scalar, Range& range, Array<double>& array, Array<bool>& mask) const; + + Array<octave_idx_type> as_array (void) const; // FIXME -- these are here for compatibility. They should be removed // when no longer in use.
--- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,3 +1,17 @@ +2010-02-19 Jaroslav Hajek <highegg@gmail.com> + + * ov-lazy-idx.cc (octave_lazy_index::reshape, + octave_lazy_index::squeeze, octave_lazy_index::permute, + octave_lazy_index::sort, octave_lazy_index::is_sorted, + octave_lazy_index::sort_rows_idx, octave_lazy_index::is_sorted_rows): + New method overrides. + * ov-lazy-idx.h: Declare them. + * ov-re-mat.cc (octave_matrix::reshape, octave_matrix::squeeze, + octave_matrix::sort, octave_matrix::is_sorted, + octave_matrix::sort_rows_idx, octave_matrix::is_sorted_rows): New + method overrides. + * ov-re-mat.h: Declare them. + 2010-02-19 Jaroslav Hajek <highegg@gmail.com> * DLD-FUNCTIONS/find.cc (Ffind): Avoid unsafe conversion from Inf to
--- a/src/ov-lazy-idx.cc +++ b/src/ov-lazy-idx.cc @@ -70,6 +70,88 @@ return retval; } +octave_value +octave_lazy_index::reshape (const dim_vector& new_dims) const +{ + return idx_vector (index.as_array ().reshape (new_dims), + index.extent (0)); +} + +octave_value +octave_lazy_index::permute (const Array<int>& vec, bool inv) const +{ + // If the conversion has already been made, forward the operation. + if (value.is_defined ()) + return value.permute (vec, inv); + else + return idx_vector (index.as_array ().permute (vec, inv), + index.extent (0)); +} + +octave_value +octave_lazy_index::squeeze (void) const +{ + return idx_vector (index.as_array ().squeeze (), + index.extent (0)); +} + +octave_value +octave_lazy_index::sort (octave_idx_type dim, sortmode mode) const +{ + const dim_vector odims = index.orig_dimensions (); + // index_vector can employ a more efficient sorting algorithm. + if (mode == ASCENDING && odims.length () == 2 + && (dim >= 0 && dim <= 1) && odims (1-dim) == 1) + return index_vector ().sorted (); + else + return idx_vector (index.as_array ().sort (dim, mode), + index.extent (0)); +} + +octave_value +octave_lazy_index::sort (Array<octave_idx_type> &sidx, octave_idx_type dim, + sortmode mode) const +{ + const dim_vector odims = index.orig_dimensions (); + // index_vector can employ a more efficient sorting algorithm. + if (mode == ASCENDING && odims.length () == 2 + && (dim >= 0 && dim <= 1) && odims (1-dim) == 1) + return index_vector ().sorted (sidx); + else + return idx_vector (index.as_array ().sort (sidx, dim, mode), + index.extent (0)); +} + +sortmode +octave_lazy_index::is_sorted (sortmode mode) const +{ + if (index.is_range ()) + { + // Avoid the array conversion. + octave_idx_type inc = index.increment (); + if (inc == 0) + return (mode == UNSORTED ? ASCENDING : mode); + else if (inc > 0) + return (mode == DESCENDING ? UNSORTED : ASCENDING); + else + return (mode == ASCENDING ? UNSORTED : DESCENDING); + } + else + return index.as_array ().is_sorted (mode); +} + +Array<octave_idx_type> +octave_lazy_index::sort_rows_idx (sortmode mode) const +{ + return index.as_array ().sort_rows_idx (mode); +} + +sortmode +octave_lazy_index::is_sorted_rows (sortmode mode) const +{ + return index.as_array ().is_sorted_rows (mode); +} + static const std::string value_save_tag ("index_value"); bool octave_lazy_index::save_ascii (std::ostream& os)
--- a/src/ov-lazy-idx.h +++ b/src/ov-lazy-idx.h @@ -54,8 +54,7 @@ size_t byte_size (void) const { return numel () * sizeof (octave_idx_type); } - // FIXME: should avoid conversion. - octave_value squeeze (void) const { return make_value ().squeeze (); } + octave_value squeeze (void) const; octave_value full_value (void) const { return make_value (); } @@ -95,12 +94,9 @@ octave_idx_type nnz (void) const { return numel (); } - // FIXME: should avoid conversion. - octave_value reshape (const dim_vector& new_dims) const - { return make_value ().reshape (new_dims); } + octave_value reshape (const dim_vector& new_dims) const; - octave_value permute (const Array<int>& vec, bool inv = false) const - { return make_value ().permute (vec, inv); } + octave_value permute (const Array<int>& vec, bool inv = false) const; octave_value resize (const dim_vector& dv, bool fill = false) const { return make_value ().resize (dv, fill); } @@ -112,15 +108,16 @@ MatrixType matrix_type (const MatrixType& _typ) const { return make_value ().matrix_type (_typ); } - // FIXME: should avoid conversion. - sortmode is_sorted (sortmode mode = UNSORTED) const - { return make_value ().is_sorted (mode); } + octave_value sort (octave_idx_type dim = 0, sortmode mode = ASCENDING) const; + + octave_value sort (Array<octave_idx_type> &sidx, octave_idx_type dim = 0, + sortmode mode = ASCENDING) const; - Array<octave_idx_type> sort_rows_idx (sortmode mode = ASCENDING) const - { return make_value ().sort_rows_idx (mode); } + sortmode is_sorted (sortmode mode = UNSORTED) const; - sortmode is_sorted_rows (sortmode mode = UNSORTED) const - { return make_value ().is_sorted_rows (mode); } + Array<octave_idx_type> sort_rows_idx (sortmode mode = ASCENDING) const; + + sortmode is_sorted_rows (sortmode mode = UNSORTED) const; bool is_matrix_type (void) const { return true; } @@ -196,13 +193,6 @@ octave_value diag (octave_idx_type k = 0) const { return make_value ().diag (k); } - octave_value sort (octave_idx_type dim = 0, sortmode mode = ASCENDING) const - { return make_value ().sort (dim, mode); } - - octave_value sort (Array<octave_idx_type> &sidx, octave_idx_type dim = 0, - sortmode mode = ASCENDING) const - { return make_value ().sort (sidx, dim, mode); } - octave_value convert_to_str_internal (bool pad, bool force, char type) const { return make_value ().convert_to_str_internal (pad, force, type); }
--- a/src/ov-re-mat.cc +++ b/src/ov-re-mat.cc @@ -57,6 +57,7 @@ #include "ov-re-sparse.h" #include "ov-re-diag.h" #include "ov-cx-diag.h" +#include "ov-lazy-idx.h" #include "ov-perm.h" #include "ov-type-conv.h" #include "pr-output.h" @@ -271,15 +272,42 @@ return retval; } +// We override these two functions to allow reshaping both +// the matrix and the index cache. +octave_value +octave_matrix::reshape (const dim_vector& new_dims) const +{ + if (idx_cache) + { + return new octave_matrix (matrix.reshape (new_dims), + idx_vector (idx_cache->as_array ().reshape (new_dims), + idx_cache->extent (0))); + } + else + return octave_base_matrix<NDArray>::reshape (new_dims); +} + +octave_value +octave_matrix::squeeze (void) const +{ + if (idx_cache) + { + return new octave_matrix (matrix.squeeze (), + idx_vector (idx_cache->as_array ().squeeze (), + idx_cache->extent (0))); + } + else + return octave_base_matrix<NDArray>::squeeze (); +} + octave_value octave_matrix::sort (octave_idx_type dim, sortmode mode) const { - // If this matrix is known to be a valid index, and we're doing a vector sort, - // sort via idx_vector which may be more efficient occassionally. - if (idx_cache && mode == ASCENDING && ndims () == 2 - && ((dim == 0 && matrix.columns () == 1) || (dim == 1 && matrix.rows () == 1))) + if (idx_cache) { - return index_vector ().sorted (); + // This is a valid index matrix, so sort via integers because it's + // generally more efficient. + return octave_lazy_index (*idx_cache).sort (dim, mode); } else return octave_base_matrix<NDArray>::sort (dim, mode); @@ -289,16 +317,54 @@ octave_matrix::sort (Array<octave_idx_type> &sidx, octave_idx_type dim, sortmode mode) const { - // If this matrix is known to be a valid index, and we're doing a vector sort, - // sort via idx_vector which may be more efficient occassionally. - if (idx_cache && mode == ASCENDING && ndims () == 2 - && ((dim == 0 && matrix.columns () == 1) || (dim == 1 && matrix.rows () == 1))) + if (idx_cache) { - return index_vector ().sorted (sidx); + // This is a valid index matrix, so sort via integers because it's + // generally more efficient. + return octave_lazy_index (*idx_cache).sort (sidx, dim, mode); } else return octave_base_matrix<NDArray>::sort (sidx, dim, mode); } + +sortmode +octave_matrix::is_sorted (sortmode mode) const +{ + if (idx_cache) + { + // This is a valid index matrix, so check via integers because it's + // generally more efficient. + return idx_cache->as_array ().is_sorted (mode); + } + else + return octave_base_matrix<NDArray>::is_sorted (mode); +} +Array<octave_idx_type> +octave_matrix::sort_rows_idx (sortmode mode) const +{ + if (idx_cache) + { + // This is a valid index matrix, so sort via integers because it's + // generally more efficient. + return octave_lazy_index (*idx_cache).sort_rows_idx (mode); + } + else + return octave_base_matrix<NDArray>::sort_rows_idx (mode); +} + +sortmode +octave_matrix::is_sorted_rows (sortmode mode) const +{ + if (idx_cache) + { + // This is a valid index matrix, so check via integers because it's + // generally more efficient. + return idx_cache->as_array ().is_sorted_rows (mode); + } + else + return octave_base_matrix<NDArray>::is_sorted_rows (mode); +} + octave_value octave_matrix::convert_to_str_internal (bool, bool, char type) const {
--- a/src/ov-re-mat.h +++ b/src/ov-re-mat.h @@ -179,10 +179,20 @@ octave_value diag (octave_idx_type k = 0) const; + octave_value reshape (const dim_vector& new_dims) const; + + octave_value squeeze (void) const; + octave_value sort (octave_idx_type dim = 0, sortmode mode = ASCENDING) const; octave_value sort (Array<octave_idx_type> &sidx, octave_idx_type dim = 0, sortmode mode = ASCENDING) const; + sortmode is_sorted (sortmode mode = UNSORTED) const; + + Array<octave_idx_type> sort_rows_idx (sortmode mode = ASCENDING) const; + + sortmode is_sorted_rows (sortmode mode = UNSORTED) const; + // Use matrix_ref here to clear index cache. void increment (void) { matrix_ref () += 1.0; }