changeset 10983:4b51c0a20a98

optimize sum of sparse logical matrices
author Jaroslav Hajek <highegg@gmail.com>
date Wed, 15 Sep 2010 22:31:12 +0200
parents 1ec2f19857fa
children 58c57161626d
files liboctave/CSparse.h liboctave/ChangeLog liboctave/boolSparse.cc liboctave/boolSparse.h liboctave/dSparse.h src/data.cc
diffstat 6 files changed, 70 insertions(+), 8 deletions(-) [+]
line wrap: on
line diff
--- a/liboctave/CSparse.h
+++ b/liboctave/CSparse.h
@@ -72,6 +72,8 @@
 
   SparseComplexMatrix (const MSparse<Complex>& a) : MSparse<Complex> (a) { }
 
+  SparseComplexMatrix (const Sparse<Complex>& a) : MSparse<Complex> (a) { }
+
   explicit SparseComplexMatrix (const ComplexMatrix& a) 
     : MSparse<Complex> (a) { }
 
--- a/liboctave/ChangeLog
+++ b/liboctave/ChangeLog
@@ -1,3 +1,12 @@
+2010-09-15  Jaroslav Hajek  <highegg@gmail.com>
+
+	* dSparse.h (SparseMatrix::SparseMatrix (const Sparse<double>&)):
+	New ctor.
+	* CSparse.h (SparseComplexMatrix::SparseComplexMatrix 
+	(const Sparse<Complex>&)): New ctor.
+	* boolSparse.cc (SparseBoolMatrix::sum): New method.
+	* boolSparse.h: Declare it.
+
 2010-09-15  Jaroslav Hajek  <highegg@gmail.com>
 
 	* boolSparse.cc (SparseBoolMatrix::any): Optimize.
--- a/liboctave/boolSparse.cc
+++ b/liboctave/boolSparse.cc
@@ -35,6 +35,7 @@
 #include "lo-mappers.h"
 
 #include "boolSparse.h"
+#include "dSparse.h"
 #include "oct-mem.h"
 #include "oct-locbuf.h"
 
@@ -169,13 +170,58 @@
         }
       else
         {
-          OCTAVE_LOCAL_BUFFER (octave_idx_type, tmpridx, nz);
-          copy_or_memcpy (nz, ridx (), tmpridx);
-          std::sort (tmpridx, tmpridx+nz);
-          octave_idx_type new_nz = std::unique (tmpridx, tmpridx + nz) - tmpridx;
-          retval = Sparse<bool> (nr, 1, new_nz);
-          copy_or_memcpy (new_nz, tmpridx, retval.ridx ());
-          fill_or_memset (new_nz, true, retval.data ());
+          Array<octave_idx_type> tmp (nz, 1);
+          copy_or_memcpy (nz, ridx (), tmp.fortran_vec ());
+          retval = Sparse<bool> (Array<bool> (1, 1, true),
+                                 idx_vector (tmp), idx_vector (0), nr, 1,
+                                 false);
+        }
+    }
+
+  return retval;
+}
+
+SparseMatrix
+SparseBoolMatrix::sum (int dim) const
+{
+  Sparse<double> retval;
+  octave_idx_type nr = rows (), nc = cols (), nz = nnz ();
+  if (dim == -1)
+    dim = (nr == 1 && nc != 1) ? 1 : 0;
+
+  if (dim == 0)
+    {
+      // Result is a row vector.
+      retval = Sparse<double> (1, nc);
+      for(octave_idx_type i = 0; i < nc; i++)
+        retval.xcidx(i+1) = retval.xcidx(i) + (cidx(i+1) > cidx(i));
+      octave_idx_type new_nz = retval.xcidx(nc);
+      retval.change_capacity (new_nz);
+      fill_or_memset (new_nz, static_cast<octave_idx_type> (0), retval.ridx ());
+      for(octave_idx_type i = 0, k = 0; i < nc; i++)
+        {
+          octave_idx_type c = cidx(i+1) - cidx(i);
+          if (c > 0)
+            retval.xdata(k++) = c;
+        }
+    }
+  else if (dim == 1)
+    {
+      // Result is a column vector.
+      if (nz > nr)
+        {
+          // We can use O(nr) memory.
+          Array<double> tmp (nr, 1, 0);
+          for (octave_idx_type i = 0; i < nz; i++)
+            tmp.xelem(ridx(i)) += 1.0;
+          retval = tmp;
+        }
+      else
+        {
+          Array<octave_idx_type> tmp (nz, 1);
+          copy_or_memcpy (nz, ridx (), tmp.fortran_vec ());
+          retval = Sparse<double> (Array<double> (1, 1, 1.0),
+                                   idx_vector (tmp), idx_vector (0), nr, 1);
         }
     }
 
--- a/liboctave/boolSparse.h
+++ b/liboctave/boolSparse.h
@@ -28,6 +28,8 @@
 #include "MSparse-defs.h"
 #include "Sparse-op-defs.h"
 
+class SparseMatrix;
+
 class
 OCTAVE_API
 SparseBoolMatrix : public Sparse<bool>
@@ -108,6 +110,7 @@
 
   SparseBoolMatrix all (int dim = -1) const;
   SparseBoolMatrix any (int dim = -1) const;
+  SparseMatrix sum (int dim = -1) const;
 
   // i/o
 
--- a/liboctave/dSparse.h
+++ b/liboctave/dSparse.h
@@ -66,6 +66,8 @@
 
   SparseMatrix (const MSparse<double>& a) : MSparse<double> (a) { }
 
+  SparseMatrix (const Sparse<double>& a) : MSparse<double> (a) { }
+
   explicit SparseMatrix (const SparseBoolMatrix& a);
 
   explicit SparseMatrix (const Matrix& a) : MSparse<double> (a) { }
--- a/src/data.cc
+++ b/src/data.cc
@@ -2361,7 +2361,7 @@
                   if (isnative)
                     retval = arg.sparse_bool_matrix_value ().any (dim);
                   else
-                    retval = arg.sparse_matrix_value ().sum (dim);
+                    retval = arg.sparse_bool_matrix_value ().sum (dim);
                 }
               else if (isnative)
                 retval = arg.bool_array_value ().any (dim);