efficient variable circshift on 3D matrix

Hello,

I have a working method of circularly shifting every 60 element vector in a 3D matrix A (300x300x60) over its corresponding value in 2D shift matrix B (300x300) which is relatively slow. I hope there is a faster method than the methods I currently have.

The shifting works as follows: If B(1,1) for example is 10, I want to shift A(1, 1, :) over 10 samples. Every value in B can be different.

My first approach was the following:

for i=1:size(B, 1)
    for j=1:size(B, 2)
        A(i, j, :) = circshift(A(i, j, :), B(i, j));
    end
end

which works, but is relatively slow (0.2s). A second approach was to first reshape matrices A and B to 2D and 1D respectively and get rid of the nested for loop.

a = reshape(A, size(A, 1)*size(A, 2), size(A, 3))';
b = reshape(B, size(B, 1)*size(B, 2), 1);
for i = 1:length(b)
    a(:, i) = circshift(a(:, i), b(i));
end
A = reshape(a', size(fm2, 1), size(fm2, 2), size(fm2, 3));

Which also works and is already little bit faster (0.1s).

Is there any other method to do this that would be much faster?

Thanks.

[DGM]

I don't know of a good alternative. I was going to suggest reshaping, but you already got there. I don't think avoiding the multiple size() calls saves any meaningful amount of time, but it's more compact.

A = rand(300,300,60);
B = randi([-30 30],300,300);

% original method
a = timeit(@() testA(A,B))

a = 0.2226

% using simplified mcode
b = timeit(@() testB(A,B))

b = 0.0610

% time ratio
a/b

ans = 3.6500

function testA(A,B)
    for i=1:size(B, 1)
        for j=1:size(B, 2)
            A(i, j, :) = circshift(A(i, j, :), B(i, j));
        end
    end
end

function testB(A,B)
    s = size(A);
    a = reshape(A, [], s(3))';
    b = reshape(B, [], 1);
    for i = 1:length(b)
        a(:, i) = circshift(a(:, i), b(i));
    end
    A = reshape(a', s);
end

There's probably something I'm forgetting, but I recall running into this same obstacle before.

[Jona Gladines]

Loosing the size() calls makes it indeed considerably faster. Thanks

I'm happy with this result, although other solutions are still welcome.

Big thanks for the super fast response.

[DGM]

Well, I'm still kind of hoping that someone else has another improvement. I was mostly just offering a (more) reliable timing method.

[Jan]

Providing inputs would be very useful. It matters e.g. if the values of B are unique or if there are typically many same values. Optimizing code can exploit such patterns of the input.

For the test data DGM hast provided, this is twice as fast:

s = size(A);
a = reshape(A, [], s(3))';
b = reshape(B, [], 1);
ub = unique(b);
for i = 1:numel(ub)
   m       = (b == ub(i));
   a(:, m) = circshift(a(:, m), ub(i));
end
A = reshape(a', s);

[Jona Gladines]

The shift data is part of a 3D recovery method, of which I cannot disclose more information at this point in time. however I've attached a shift matrix from one of the measurements. However since every item that is measured is different, these values wil also be different for every measurement. Sometimes there will be lots of the same values, other times values might differ more.

Answer 1

[Jan]

In this code:

s = size(A);
a = reshape(A, [], s(3))';
b = reshape(B, [], 1);
ub = unique(b);
for i = 1:numel(ub)
   m       = (b == ub(i));
   a(:, m) = circshift(a(:, m), ub(i));
end
A = reshape(a', s);

40% of the computing time is spent for transposing. So if you store the data directly in a way, which let the operations work on the first dimension, the computing time is reduced also.

Answer 2

[Jona Gladines]

The data is gathered from camera's and can only be transposed at this step, but your proposed method is certainly fast enough for my purpose.

Thanks to everyone who helped me in this quest.

regards,

Jona