* Bug #5205 fixed - permute() function was slow with large hypermatrixes 74/12574/3
Paul BIGNIER [Wed, 18 Sep 2013 07:22:32 +0000 (09:22 +0200)]
Step 2: eased main loop and side loop, added test.

Change-Id: I4363bda51fb3cba1462340e55c4da8d51e3d1d62

scilab/CHANGES_5.5.X
scilab/modules/elementary_functions/macros/permute.sci
scilab/modules/elementary_functions/tests/unit_tests/permute.dia.ref [new file with mode: 0644]
scilab/modules/elementary_functions/tests/unit_tests/permute.tst [new file with mode: 0644]

index 619b64f..0885182 100644 (file)
@@ -252,6 +252,8 @@ Bug Fixes
 
 * Bug #5073 fixed - New parameter added in strtod function (decimal separator).
 
+* Bug #5205 fixed - permute was slow for large hypermatrices.
+
 * Bug #5207 fixed - grand can now return a hypermatrix.
 
 * Bug #5365 fixed - makecell help page was in the "compatibility functions" directory
index dab77dd..e22ed9b 100644 (file)
@@ -7,7 +7,7 @@
 // are also available at
 // http://www.cecill.info/licences/Licence_CeCILL_V2.1-en.txt
 
-function   y = permute(x,dims)
+function y = permute(x, dims)
 
     // This function returns an array y which results of the x permutation
     // Input :
@@ -17,79 +17,81 @@ function   y = permute(x,dims)
     // -y the result of the x permutation
 
     // Verify input arguments number
-    if argn(2)<>2 then
-        error(msprintf(gettext("%s: Wrong number of input argument(s): %d expected.\n"),"permute",2));
+    if argn(2) <> 2 then
+        error(msprintf(gettext("%s: Wrong number of input argument(s): %d expected.\n"), "permute", 2));
     end
 
     // Verify if the size of dims corresponds to dimension of x
+    if ndims(dims) <> 2 then
+        error(msprintf(gettext("%s: Wrong size for argument #%d: Vector expected.\n"), "permute", 2));
 
-    if ndims(dims)<>2 then
-        error(msprintf(gettext("%s: Wrong size for argument #%d: Vector expected.\n"),"permute",2));
+    elseif or(gsort(dims,"c","i") <> (1:prod(size(dims)))) then
+        error(msprintf(gettext("%s: Wrong size for input argument #%d.\n"), "permute", 2));
 
-    elseif or(gsort(dims,"c","i")<>(1:prod(size(dims)))) then
-        error(msprintf(gettext("%s: Wrong size for input argument #%d.\n"),"permute",2));
-
-    elseif prod(size(dims))<ndims(x) then
-        error(msprintf(gettext("%s: Wrong size for input argument #%d: At least the size of input argument #%d expected.\n"),"permute",2,1));
+    elseif prod(size(dims)) < ndims(x) then
+        error(msprintf(gettext("%s: Wrong size for input argument #%d: At least the size of input argument #%d expected.\n"), "permute", 2, 1));
     end
 
     // Case x is empty
     if isempty(x) then
-        y=x
+        y = x
         return
     end
 
     // xsize vector contains the size of x
-    xsize=size(x)
+    xsize = size(x)
     // ysize vector contains the new size of x after the permutation
-    ind1=find(dims<=ndims(x))
-    ind2=find(dims>ndims(x))
-    ysize(ind1)=xsize(dims(ind1))
-    ysize(ind2)=1
-    dims=dims(ind1)
+    ind1 = find(dims<=ndims(x))
+    ind2 = find(dims>ndims(x))
+    ysize(ind1) = xsize(dims(ind1))
+    ysize(ind2) = 1
+    dims = dims(ind1)
 
-    // delete the last dimensions of ysize which are equal to 1, ex : [2,3,1,4,1,1,1] -> [2,3,1,4]
-    i=prod(size(ysize))
+    // Delete the last dimensions of ysize which are equal to 1, ex : [2,3,1,4,1,1,1] -> [2,3,1,4]
+    i = prod(size(ysize))
     while i>2 & ysize(i)==1 & i>max(ind1)
-        ysize(i)=[]
-        i=i-1
+        ysize(i) = []
+        i = i-1
     end
 
     // index vector contains all indices of x
-    index=[]
+    index = zeros(1, prod(xsize)*length(xsize)); // Preallocate index
+    m = 1; // Iterator on index
     for k=1:size(xsize,"*")
         for j=1:size(x,"*")/prod(xsize(1:k))
             for l=1:xsize(k)
-                index=[index,ones(1:prod(xsize(1:k-1)))*l]
+                temp = ones(1, prod(xsize(1:k-1)))*l;
+                index(1, m:m+size(temp,"*")-1) = temp;
+                m = m+size(temp, "*"); // Pad m with the size of the vector we just computed
             end
         end
     end
-    index=matrix(index,size(x,"*"),size(xsize,"*"))
+    index = matrix(index, size(x, "*"), size(xsize, "*"))
 
     // prodxsize is a vector, its ith component contains the prod of the first to the (ith-1) entries of xsize, its first component is always equal to one
-    prodxsize(1)=1
+    prodxsize = ones(size(xsize, "*"), 1)
     for i=2:size(xsize,"*")
-        prodxsize($+1)=prod(xsize(1:i-1))
+        prodxsize(i) = prod(xsize(1:i-1))
     end
-    prodysize(1)=1
+    prodysize = ones(size(xsize, "*"), 1)
     for i=2:size(ysize,"*")
-        prodysize($+1)=prod(ysize(1:i-1))
+        prodysize(i) = prod(ysize(1:i-1))
     end
 
     // newindex contains the indices of x dimensions permutation
     for j=1:size(index,1)
-        indexj=index(j,:)
-        newindexj=ones(1:prod(size(ysize)))
-        newindexj(ind1)=indexj(dims)
-        indexj(2:$)=indexj(2:$)-1
-        newindexj(2:$)=newindexj(2:$)-1
-        if typeof(x)=="ce" then //case x is a cell array
-            y(newindexj*prodysize).entries=x(indexj*prodxsize).entries
+        indexj = index(j, :)
+        newindexj = ones(1:prod(size(ysize)))
+        newindexj(ind1) = indexj(dims)
+        indexj(2:$) = indexj(2:$)-1
+        newindexj(2:$) = newindexj(2:$)-1
+        if typeof(x) == "ce" then // Case x is a cell array
+            y(newindexj*prodysize).entries = x(indexj*prodxsize).entries
         else
-            y(newindexj*prodysize)=x(indexj*prodxsize)
+            y(newindexj*prodysize) = x(indexj*prodxsize)
         end
     end
 
-    y=matrix(y,ysize)
+    y = matrix(y, ysize)
 
 endfunction
diff --git a/scilab/modules/elementary_functions/tests/unit_tests/permute.dia.ref b/scilab/modules/elementary_functions/tests/unit_tests/permute.dia.ref
new file mode 100644 (file)
index 0000000..6e94f3f
--- /dev/null
@@ -0,0 +1,44 @@
+// =============================================================================
+// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+// Copyright (C) 2013 - Scilab Enterprises - Paul Bignier
+//
+//  This file is distributed under the same license as the Scilab package.
+// =============================================================================
+//
+// <-- CLI SHELL MODE -->
+//
+// With a real matrix
+x = [1 2 3; 4 5 6];
+y = permute(x, [2 1]);
+assert_checkequal(y, x');
+// With an integer matrix
+x = int32(x);
+y = permute(x, [2 1]);
+assert_checkequal(y, x');
+// With a string matrix
+x = string(x);
+y = permute(x, [2 1]);
+assert_checkequal(y, x');
+// With a real hypermatrix
+x = matrix(1:12, [2, 3, 2]);
+y = permute(x, [3 1 2]);
+refY(:, :, 1) = [1 2; 7 8];
+refY(:, :, 2) = [3 4; 9 10];
+refY(:, :, 3) = [5 6; 11 12];
+assert_checkequal(y, refY);
+// With an integer hypermatrix
+x = int32(x);
+y = permute(x, [3 1 2]);
+refY = int32(refY);
+assert_checkequal(y, refY);
+// With a string hypermatrix
+x = string(x);
+y = permute(x, [3 1 2]);
+refY = string(refY);
+assert_checkequal(y, refY);
+// Error checks
+refMsg = msprintf(_("%s: Wrong size for input argument #%d: At least the size of input argument #%d expected.\n"), "permute", 2, 1);
+assert_checkerror("permute(x, [1 2]);", refMsg);
+refMsg = msprintf(_("%s: Wrong size for input argument #%d.\n"), "permute", 2);
+assert_checkerror("permute(x, [1 2 4]);", refMsg);
+assert_checkerror("permute(x, [1 2 3 5]);", refMsg);
diff --git a/scilab/modules/elementary_functions/tests/unit_tests/permute.tst b/scilab/modules/elementary_functions/tests/unit_tests/permute.tst
new file mode 100644 (file)
index 0000000..fc16f39
--- /dev/null
@@ -0,0 +1,57 @@
+// =============================================================================
+// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+// Copyright (C) 2013 - Scilab Enterprises - Paul Bignier
+//
+//  This file is distributed under the same license as the Scilab package.
+// =============================================================================
+//
+// <-- CLI SHELL MODE -->
+//
+
+// With a real matrix
+x = [1 2 3; 4 5 6];
+y = permute(x, [2 1]);
+
+assert_checkequal(y, x');
+
+// With an integer matrix
+x = int32(x);
+y = permute(x, [2 1]);
+
+assert_checkequal(y, x');
+
+// With a string matrix
+x = string(x);
+y = permute(x, [2 1]);
+
+assert_checkequal(y, x');
+
+// With a real hypermatrix
+x = matrix(1:12, [2, 3, 2]);
+y = permute(x, [3 1 2]);
+refY(:, :, 1) = [1 2; 7 8];
+refY(:, :, 2) = [3 4; 9 10];
+refY(:, :, 3) = [5 6; 11 12];
+
+assert_checkequal(y, refY);
+
+// With an integer hypermatrix
+x = int32(x);
+y = permute(x, [3 1 2]);
+refY = int32(refY);
+
+assert_checkequal(y, refY);
+
+// With a string hypermatrix
+x = string(x);
+y = permute(x, [3 1 2]);
+refY = string(refY);
+
+assert_checkequal(y, refY);
+
+// Error checks
+refMsg = msprintf(_("%s: Wrong size for input argument #%d: At least the size of input argument #%d expected.\n"), "permute", 2, 1);
+assert_checkerror("permute(x, [1 2]);", refMsg);
+refMsg = msprintf(_("%s: Wrong size for input argument #%d.\n"), "permute", 2);
+assert_checkerror("permute(x, [1 2 4]);", refMsg);
+assert_checkerror("permute(x, [1 2 3 5]);", refMsg);