Efficiently Swapping Columns in a Matrix

22 次查看（过去 30 天）
Kyle Marocchini
Kyle Marocchini 2016-6-23
评论： Kyle Marocchini 2016-6-30
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.
  3 个评论
显示 1更早的评论
Kyle Marocchini
Kyle Marocchini 2016-6-23
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
James Tursa 2016-6-23
编辑：James Tursa 2016-6-23
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?

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

James Tursa
James Tursa 2016-6-24
编辑：James Tursa 2016-6-28
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;
}
}
}
  1 个评论
Kyle Marocchini
Kyle Marocchini 2016-6-30
Slight speed up over current MATLAB implementation, but this helped where cyclists' answer could not be applied. Appreciate your help!

请先登录，再进行评论。

更多回答（3 个）

the cyclist
the cyclist 2016-6-23
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.
  2 个评论
Kyle Marocchini
Kyle Marocchini 2016-6-24
编辑：Kyle Marocchini 2016-6-24
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.

请先登录，再进行评论。

Philip Borghesani
Philip Borghesani 2016-6-23
编辑：Philip Borghesani 2016-6-23
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.
  2 个评论
Kyle Marocchini
Kyle Marocchini 2016-6-24
Definitely interesting and promising results - I'll look into this and let you know if it bears any fruit!
Kyle Marocchini
Kyle Marocchini 2016-6-25
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.

请先登录，再进行评论。

Roger Stafford
Roger Stafford 2016-6-25
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.

类别

在 Help Center 和 File Exchange 中查找有关 Write C Functions Callable from MATLAB (MEX Files) 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by