Mercurial > octave-nkf

changeset 10339:de2d43bcb083

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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	Fri Feb 19 10:44:27 2010 +0100
+++ b/liboctave/ChangeLog	Fri Feb 19 11:47:47 2010 +0100
@@ -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	Fri Feb 19 10:44:27 2010 +0100
+++ b/liboctave/idx-vector.cc	Fri Feb 19 11:47:47 2010 +0100
@@ -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	Fri Feb 19 10:44:27 2010 +0100
+++ b/liboctave/idx-vector.h	Fri Feb 19 11:47:47 2010 +0100
@@ -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	Fri Feb 19 10:44:27 2010 +0100
+++ b/src/ChangeLog	Fri Feb 19 11:47:47 2010 +0100
@@ -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	Fri Feb 19 10:44:27 2010 +0100
+++ b/src/ov-lazy-idx.cc	Fri Feb 19 11:47:47 2010 +0100
@@ -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	Fri Feb 19 10:44:27 2010 +0100
+++ b/src/ov-lazy-idx.h	Fri Feb 19 11:47:47 2010 +0100
@@ -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	Fri Feb 19 10:44:27 2010 +0100
+++ b/src/ov-re-mat.cc	Fri Feb 19 11:47:47 2010 +0100
@@ -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	Fri Feb 19 10:44:27 2010 +0100
+++ b/src/ov-re-mat.h	Fri Feb 19 11:47:47 2010 +0100
@@ -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; }