CODEWITHSUNDEEP
arraysmatlab
johnnyfuego
johnnyfuego

Reputation: 13

Indexing into N-D matrix

I have a matrix M (4*2) with values:

[1 0;
 0 0;
 1 1;
 0 1]

And an array X = [0.3 0.4 0.5 0.2];

All column entries of M are binary (0/1). What I want is a corresponding row value mapped into a ND-array of [2,2] called Z. Each dimension here indicates 0/1, by having it in the first row or second row. X(1) needs to go to Z(2,1) and X(2) needs to go to Z(1,1) and so on..

Z will look like this: 

Z = 
[0.4 0.2;
 0.3 0.5];

Currently I am looping over this, but it is really expensive to do so. Please note that this is a minimal example - I need to do this for a 128*7 matrix into a 7D array.

Any suggestions on how to speed up this process?

Upvotes: 1

Views: 85

Answers (3)

SCFrench
SCFrench

Reputation: 8374

How about

D=[1 0;0 0;1 1;0 1]; X = [0.3 0.4 0.5 0.2];

Z(sub2ind([2 2], D(:, 1) + 1, D(:, 2) + 1)) = X;
Z = reshape(Z, 2, 2);

EDIT

Most of the overhead of sub2ind is, unfortunately, error checking. If you are comfortable that all your D values are in range, you can effectively inline the sub2ind operation. Here's an example:

ndx = M(:, 1) + 1;
ndx = ndx + M(:, 2) * 2;
Z2=[];
Z2(ndx) = X;
Z2 = reshape(Z2, 2, 2);

Using this code and the timing test in @johnnyfuego's answer, I get

Elapsed time is 0.154196 seconds.    <--- johnny's
Elapsed time is 0.288680 seconds.    <--- mine
Elapsed time is 0.143874 seconds.

So, better, but still not beating the other two. However, note that there is a break-even point here. If I change the setup code in the time test to

M = randi(2, 1000, 2) - 1;
X = rand(1, 1000);

That is, I bump the number of values to write up from 4 to 1000, then the time trial results in

Elapsed time is 3.650833 seconds.     <--- johnny's
Elapsed time is 0.607361 seconds.     <--- mine
Elapsed time is 0.872595 seconds.

EDIT #2

Here's how you would unroll a multidimensional sub2ind:

siz = [2 2 2 2 2 2 2];
offsets = cumprod(siz);
ndx = M(:, 1) + 1;
ndx = ndx + M(:, 2) * offsets(1);
ndx = ndx + M(:, 3) * offsets(2);
ndx = ndx + M(:, 4) * offsets(3);
ndx = ndx + M(:, 5) * offsets(4);
ndx = ndx + M(:, 6) * offsets(5);
ndx = ndx + M(:, 7) * offsets(6);
Z2=[];
Z2(ndx) = X;
Z2 = reshape(Z2, [siz]);

Using that with your updated time test I get:

Elapsed time is 43.754363 seconds.
Elapsed time is 1.045980 seconds.
Elapsed time is 0.689487 seconds.

So, still better than looping, but it looks like in this multidimensional case accumarray (Rafael's answer) wins. I'd consider awarding him the "accepted answer" points.

Upvotes: 1

johnnyfuego
johnnyfuego

Reputation: 13

Thank you @rafael-monteiro & @SCFRench.

My original procedure was faster. I have pasted a benchmarking script below.

M=[1 0; 0 0; 1 1; 0 1];

X = [0.3 0.4 0.5 0.2];

nrep=50000;


%% My own code
tic
for A=1:nrep;
    MN=M+1; % I know I can do this outside of the loop, but comparison with this seems more fair.
    Z=zeros(size(X,2)/2,size(X,2)/2); % without pre-allocation it is twice as fast, I guess finding the size and the computation does not help here!
    for I=1:4
        Z1(MN(I,1),MN(I,2))=X(I);
    end
end
toc

%% SCFrench code
tic
for A=1:nrep;
    Z2(sub2ind([2 2], M(:, 1) + 1, M(:, 2) + 1)) = X;
    Z2 = reshape(Z2, 2, 2);
end
toc

%% Rafael code
tic
for A=1:nrep;
    Z3 = accumarray(M + 1, X, [2 2]);
end
toc

Elapsed time is 0.115488 seconds. % mine
Elapsed time is 1.082505 seconds. % SCFrench
Elapsed time is 0.282693 seconds. % rafael

EDIT:

Using larger data, the first implementation seems far slower.

alts=7;
M = dec2bin(0:2^alts-1)-'0';  
X = rand(size(M,1),1);
nrep=50000;

tic
for A=1:nrep;
    MN=M+1;
    for I=1:128
        Z1(MN(I,1),MN(I,2),MN(I,3),MN(I,4),MN(I,5),MN(I,6),MN(I,7))=X(I);
    end
end
toc

tic
for A=1:nrep;
    Z2(sub2ind([2 2 2 2 2 2 2], M(:, 1) + 1, M(:, 2) + 1, M(:, 3) + 1, M(:, 4)     + 1, M(:, 5) + 1, M(:, 6) + 1, M(:, 7) + 1)) = X;
    Z2 = reshape(Z2, [2 2 2 2 2 2 2]);
end
toc

tic
for A=1:nrep;
    Z3 = accumarray(M + 1, X, [2 2 2 2 2 2 2]);
end
toc

Elapsed time is 33.390247 seconds. % Mine
Elapsed time is 4.280668 seconds.  % SCFrench
Elapsed time is 0.629584 seconds.  % Rafael

Upvotes: 0

Rafael Monteiro
Rafael Monteiro

Reputation: 4549

You could try using accumarray (not sure if it's faster):

>> Z = accumarray(M + 1, X, [2 2])

Z =

    0.4000    0.2000
    0.2000    0.5000

Upvotes: 2

Related Questions