Mercurial > octave

changeset 17691:8a54a481ecb5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Massive speed improvement in sparse min/max functions for calls like 'max(s,[],2)' (bug #40268) * dSparse.cc (SparseMatrix SparseMatrix::max (Array<octave_idx-type>&, int)) : Remove triple loop by using a local buffer (SparseMatrix SparseMatrix::min (Array<octave_idx-type>&, int)) : ditto * CSparse.cc (SparseComplexMatrix SparseComplexMatrix::max ( Array<octave_idx-type>&, int)) : Remove triple loop by using a local buffer (SparseComplexMatrix SparseComplexMatrix::min (Array<octave_idx-type>&, int)) : ditto
author David Bateman <dbateman@free.fr>
date Fri, 18 Oct 2013 23:44:44 +0200
parents 79d6af38b96f
children 38cf56b77274
files liboctave/array/CSparse.cc liboctave/array/dSparse.cc
diffstat 2 files changed, 60 insertions(+), 75 deletions(-) [+]
line wrap: on
line diff
--- a/liboctave/array/CSparse.cc	Fri Oct 18 14:25:29 2013 -0700
+++ b/liboctave/array/CSparse.cc	Fri Oct 18 23:44:44 2013 +0200
@@ -342,29 +342,19 @@
       if (nr == 0 || nc == 0 || dim >= dv.length ())
         return SparseComplexMatrix (nr, nc == 0 ? 0 : 1);
 
-
-      idx_arg.resize (dim_vector (nr, 1), 0);
-
-      for (octave_idx_type i = cidx (0); i < cidx (1); i++)
-        idx_arg.elem (ridx (i)) = -1;
+      OCTAVE_LOCAL_BUFFER (octave_idx_type, found, nr);
+
+      for (octave_idx_type i = 0; i < nr; i++)
+        found [i] = 0;
 
       for (octave_idx_type j = 0; j < nc; j++)
-        for (octave_idx_type i = 0; i < nr; i++)
-          {
-            if (idx_arg.elem (i) != -1)
-              continue;
-            bool found = false;
-            for (octave_idx_type k = cidx (j); k < cidx (j+1); k++)
-              if (ridx (k) == i)
-                {
-                  found = true;
-                  break;
-                }
-
-            if (!found)
-              idx_arg.elem (i) = j;
-
-          }
+        for (octave_idx_type i = cidx(j); i < cidx(j+1); i++)
+          if (found [ridx (i)] == -j)
+            found [ridx (i)] = -j - 1;
+      
+      for (octave_idx_type i = 0; i < nr; i++)
+        if (found [i] > -nc && found [i] < 0)
+          idx_arg.elem (i) = -found [i];
 
       for (octave_idx_type j = 0; j < nc; j++)
         {
@@ -509,26 +499,19 @@
       if (nr == 0 || nc == 0 || dim >= dv.length ())
         return SparseComplexMatrix (nr, nc == 0 ? 0 : 1);
 
-      for (octave_idx_type i = cidx (0); i < cidx (1); i++)
-        idx_arg.elem (ridx (i)) = -1;
+      OCTAVE_LOCAL_BUFFER (octave_idx_type, found, nr);
+
+      for (octave_idx_type i = 0; i < nr; i++)
+        found [i] = 0;
 
       for (octave_idx_type j = 0; j < nc; j++)
-        for (octave_idx_type i = 0; i < nr; i++)
-          {
-            if (idx_arg.elem (i) != -1)
-              continue;
-            bool found = false;
-            for (octave_idx_type k = cidx (j); k < cidx (j+1); k++)
-              if (ridx (k) == i)
-                {
-                  found = true;
-                  break;
-                }
-
-            if (!found)
-              idx_arg.elem (i) = j;
-
-          }
+        for (octave_idx_type i = cidx(j); i < cidx(j+1); i++)
+          if (found [ridx (i)] == -j)
+            found [ridx (i)] = -j - 1;
+      
+      for (octave_idx_type i = 0; i < nr; i++)
+        if (found [i] > -nc && found [i] < 0)
+          idx_arg.elem (i) = -found [i];
 
       for (octave_idx_type j = 0; j < nc; j++)
         {
@@ -582,6 +565,14 @@
 
 %!assert (max (max (speye (65536) * 1i)), sparse (1i)) 
 %!assert (min (min (speye (65536) * 1i)), sparse (0)) 
+%!assert (size (max (sparse (8, 0), [], 1)), [1, 0]) 
+%!assert (size (max (sparse (8, 0), [], 2)), [8, 0]) 
+%!assert (size (max (sparse (0, 8), [], 1)), [0, 8]) 
+%!assert (size (max (sparse (0, 8), [], 2)), [0, 1]) 
+%!assert (size (min (sparse (8, 0), [], 1)), [1, 0]) 
+%!assert (size (min (sparse (8, 0), [], 2)), [8, 0]) 
+%!assert (size (min (sparse (0, 8), [], 1)), [0, 8]) 
+%!assert (size (min (sparse (0, 8), [], 2)), [0, 1]) 
 
 */
 
--- a/liboctave/array/dSparse.cc	Fri Oct 18 14:25:29 2013 -0700
+++ b/liboctave/array/dSparse.cc	Fri Oct 18 23:44:44 2013 +0200
@@ -353,26 +353,19 @@
       if (nr == 0 || nc == 0 || dim >= dv.length ())
         return SparseMatrix (nr, nc == 0 ? 0 : 1);
 
-      for (octave_idx_type i = cidx (0); i < cidx (1); i++)
-        idx_arg.elem (ridx (i)) = -1;
+      OCTAVE_LOCAL_BUFFER (octave_idx_type, found, nr);
+
+      for (octave_idx_type i = 0; i < nr; i++)
+        found [i] = 0;
 
       for (octave_idx_type j = 0; j < nc; j++)
-        for (octave_idx_type i = 0; i < nr; i++)
-          {
-            if (idx_arg.elem (i) != -1)
-              continue;
-            bool found = false;
-            for (octave_idx_type k = cidx (j); k < cidx (j+1); k++)
-              if (ridx (k) == i)
-                {
-                  found = true;
-                  break;
-                }
-
-            if (!found)
-              idx_arg.elem (i) = j;
-
-          }
+        for (octave_idx_type i = cidx(j); i < cidx(j+1); i++)
+          if (found [ridx (i)] == -j)
+            found [ridx (i)] = -j - 1;
+      
+      for (octave_idx_type i = 0; i < nr; i++)
+        if (found [i] > -nc && found [i] < 0)
+          idx_arg.elem (i) = -found [i];
 
       for (octave_idx_type j = 0; j < nc; j++)
         {
@@ -511,26 +504,19 @@
       if (nr == 0 || nc == 0 || dim >= dv.length ())
         return SparseMatrix (nr, nc == 0 ? 0 : 1);
 
-      for (octave_idx_type i = cidx (0); i < cidx (1); i++)
-        idx_arg.elem (ridx (i)) = -1;
+      OCTAVE_LOCAL_BUFFER (octave_idx_type, found, nr);
+
+      for (octave_idx_type i = 0; i < nr; i++)
+        found [i] = 0;
 
       for (octave_idx_type j = 0; j < nc; j++)
-        for (octave_idx_type i = 0; i < nr; i++)
-          {
-            if (idx_arg.elem (i) != -1)
-              continue;
-            bool found = false;
-            for (octave_idx_type k = cidx (j); k < cidx (j+1); k++)
-              if (ridx (k) == i)
-                {
-                  found = true;
-                  break;
-                }
-
-            if (!found)
-              idx_arg.elem (i) = j;
-
-          }
+        for (octave_idx_type i = cidx(j); i < cidx(j+1); i++)
+          if (found [ridx (i)] == -j)
+            found [ridx (i)] = -j - 1;
+      
+      for (octave_idx_type i = 0; i < nr; i++)
+        if (found [i] > -nc && found [i] < 0)
+          idx_arg.elem (i) = -found [i];
 
       for (octave_idx_type j = 0; j < nc; j++)
         {
@@ -584,6 +570,14 @@
 
 %!assert (max (max (speye (65536))), sparse (1)) 
 %!assert (min (min (speye (65536))), sparse (0)) 
+%!assert (size (max (sparse (8, 0), [], 1)), [1, 0]) 
+%!assert (size (max (sparse (8, 0), [], 2)), [8, 0]) 
+%!assert (size (max (sparse (0, 8), [], 1)), [0, 8]) 
+%!assert (size (max (sparse (0, 8), [], 2)), [0, 1]) 
+%!assert (size (min (sparse (8, 0), [], 1)), [1, 0]) 
+%!assert (size (min (sparse (8, 0), [], 2)), [8, 0]) 
+%!assert (size (min (sparse (0, 8), [], 1)), [0, 8]) 
+%!assert (size (min (sparse (0, 8), [], 2)), [0, 1]) 
 
 */