Efficiently Swapping Columns in a Matrix

Is there a more efficient/faster way to switch out two columns in a matrix than calling:

A(:,[i j]) = A(:,[j i]);

If anyone knew of faster implementation (possibly even using MEX), I would greatly appreciate them sharing.

[Sean de Wolski]

How long is it taking and how fast do you need it to be?

[Kyle Marocchini]

I often need to swap one column with the last column of a matrix - calling this 150,000 results in at worst, a time of 1.4 seconds, which is really dismal as I call this operation maybe 10-15 times in a given iteration of a rather large program.

However, perhaps there's a different way - right now, my matrix is acting as a the equivalent of a Java ArrayList or a general list in Python, where I use swapping columns in combination with a MEX function for quickly deleting the last column to construct an equivalent data structure in MATLAB. If there isn't a way to swap columns efficiently, perhaps there's a better way to implement the data structure; if you know of such a way (I've already tried using java.util.ArrayList in MATLAB - super slow...), I'd also appreciate any feedback in that regards as well.

[James Tursa]

This could easily be done in a mex routine in-place (I can post the code if you want). I don't know how much faster it would run. The caveat is that if A is shared with another variable then you would have unwanted side effects. Do you know if A is shared with any other variable?

Answer 1

[James Tursa]

Here is the mex code to swap columns in-place. Note that it is up to the user to make sure the input matrix is not shared with another variable, since every shared variable would have their columns swapped in that case.

/* swapcolumns.c  Swaps columns of X in-place.
 *                Relies on user to make sure X is not shared with another variable
 *                since there is no checking for this in the code.
 * Syntax:  swapcolumns(X,i,j)
 *          X = a matrix (any standard class ... no objects)
 *          i,j = columns to swap
 * Programmer:  James Tursa
 * Date:        June 24, 2016
 */
#include "mex.h"

void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
{
    unsigned char b;
    unsigned char *data, *target, *source;
    size_t M, N, i, j, k, c, bytes;

      if( nrhs == 0 ) {
          mexPrintf("swapcolumns -> Swaps columns of X in-place.\n");
          mexPrintf("Relies on user to make sure X is not shared with another variable\n");
          mexPrintf("since there is no checking for this in the code.\n");
          mexPrintf("Syntax:  swapcolumns(X,i,j)\n");
          mexPrintf("         X = a matrix (any standard class ... no objects)\n");
          mexPrintf("         i,j = columns to swap\n");
          return;
      }
      if( nrhs != 3 ) {
          mexErrMsgTxt("Need exactly 3 inputs");
      }
      if( nlhs > 0 ) {
          mexErrMsgTxt("Too many outputs\n");
      }
      if( !(mxIsNumeric(prhs[0]) || mxIsChar(prhs[0]) || mxIsLogical(prhs[0]) || 
            mxIsCell(prhs[0])) ) {
          mexErrMsgTxt("1st argument needs to be standard class");
      }
      M = mxGetM(prhs[0]);
      N = mxGetN(prhs[0]);
      if( M == 0 || N == 0 ) {
          return;
      }
      i = (size_t) mxGetScalar(prhs[1]);
      j = (size_t) mxGetScalar(prhs[2]);
      if( i > N || j > N ) {
          mexErrMsgTxt("Column index(es) are too large");
      }
      if( i == 0 || j == 0 ) {
          mexErrMsgTxt("Column index(es) cannot be 0");
      }
      data = mxGetData(prhs[0]);
      bytes = M * mxGetElementSize(prhs[0]);
      c = 2;
      while( c-- ) {
          target = data + (i-1) * bytes;
          source = data + (j-1) * bytes;
          for( k=0; k<bytes; k++ ) {
              b = *target;
              *target++ = *source;
              *source++ = b;
          }
          if( mxIsNumeric(prhs[0]) && mxIsComplex(prhs[0]) ) {
              data = mxGetImagData(prhs[0]);
          } else {
              break;
          }
      }
  }

[Kyle Marocchini]

Slight speed up over current MATLAB implementation, but this helped where cyclists' answer could not be applied. Appreciate your help!

Answer 2

[the cyclist]

Are you certain you actually have to "physically" swap the columns every time? Could you instead simply keep track of the swaps, and then index into the resulting matrix, or do one massive multi-column swap at the end? Just a thought.

[Jos (10584)]

This a very elegant solution! +1

[Kyle Marocchini]

For the measure of simply column-swapping, this would do me well - however, I'm not just column swapping, I'm column swapping and then manipulating data (namely, removing data using a fast C MEX function). Moreover, the fact that I'm randomly selecting entries - often without replacement - makes keeping track of these columns swaps, along with subsequent randi() generation, a lot trickier.

However, your approach is by far the best way for straight-up column swapping.

Answer 3

[Philip Borghesani]

Does your data need to be in a matrix? Swaping two elements of a cell array will be much faster for large element sizes and will be similar to an array list or general list.

%swaptime.m
sz=1e8;
m=ones(sz,5);
for col=1:5
  c{col}=ones(sz,1);
end

tic
  m(:,[2,5])=m(:,[5,2]);
toc

tic
  c([2,5])=c([5,2]);
toc

 >> swaptime
Elapsed time is 1.295767 seconds.
Elapsed time is 0.000899 seconds.

[Kyle Marocchini]

Definitely interesting and promising results - I'll look into this and let you know if it bears any fruit!

[Kyle Marocchini]

After testing, I realized that part of the reason you were getting such a dramatic difference in speed was because of the way the matrices were arranged.

Switching to columns as opposed to rows results in a different answer:

 %swaptime.m
 sz=1e5;
 m=ones(5,sz);

 Z = mat2cell(m, size(m,1) , ones(1, size(m, 2)));

 tic
   m(:,[2,5])=m(:,[5,2]);
 toc

 tic
   Z([2,5])=Z([5,2]);
 toc

 %Elapsed time is 0.000017 seconds.
 %Elapsed time is 0.000026 seconds.

Answer 4

[Roger Stafford]

It is possible that matlab accomplishes A(:,[i j]) = A(:,[j i]); by the compiler equivalent of

   t1 = A(:,i);
   t2 = A(:,j);
   A(:,i) = t2;
   A(:,j) = t1;

which requires 4*n transfers. If you wrote a mex file that does the equivalent of

   t = A(:,i);
   A(:,i) = A(:,j);
   A(:,j) = t;

it would take only 3*n transfers. I cannot think of any more significant gains that you might make on this kind of swapping. Swapping inherently involves a transfer to temporary storage, transfer of another into the previous location, and finally transfer from temporary storage into the second location.