# HG changeset patch # User David Bateman # Date 1382132684 -7200 # Node ID 8a54a481ecb5ee9709202b9d9d3abda2c6724980 # Parent 79d6af38b96fc3a6a7177aec9dd98280f199a0c0 Massive speed improvement in sparse min/max functions for calls like 'max(s,[],2)' (bug #40268) * dSparse.cc (SparseMatrix SparseMatrix::max (Array&, int)) : Remove triple loop by using a local buffer (SparseMatrix SparseMatrix::min (Array&, int)) : ditto * CSparse.cc (SparseComplexMatrix SparseComplexMatrix::max ( Array&, int)) : Remove triple loop by using a local buffer (SparseComplexMatrix SparseComplexMatrix::min (Array&, int)) : ditto diff -r 79d6af38b96f -r 8a54a481ecb5 liboctave/array/CSparse.cc --- 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]) */ diff -r 79d6af38b96f -r 8a54a481ecb5 liboctave/array/dSparse.cc --- 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]) */