Re: circular shifting a vector/matrix - Problem

Unfortunately circshift is a handy function, but terribly slow. I've just
knocked up this fast and dirty benchmark to give you an idea of how to do
the same thing, in a very straigthforward way and still in a loop if that's
what you need in your algorithm, but without using circshift. Comment out
one or other line inside the loops to measure the performance of that
particular method. You'll see that the simple single matrix duplication
method is faster by several orders of magnitude:-

clear all; clc; close all

% Matrices
a = rand(5,20); % original matrix
c = size(a,2); % no. columns in original matrix

tic
b = repmat(a,1,2); % duplicated and concatenated (*comment out for
circshift method benchmark*)
for k = 1:1000 % loop simply to make longer for benchmark purposes
for j = 1:c % loop over column shift positions
d = b(:,j:(j+c-1)); % replication method (*comment out for
circshift method benchmark*)
%d = circshift(a,[0 -j]); % circshift method (*comment out for
replication method benchmark*)
end
end
toc



"jkvdpoel" <jkvdpoel@xxxxxxxxx> wrote in message
news:1146363422.047346.98370@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Hello,

I have a problem with circular shifting a vector/matrix that is keeping
my mind absolutely crazy.

I know and use the "circshift" function (many thanks to the one that
designed this function, as it helps me to solve almost all of my
problems ;-).

I have two matrices, each one with equal dimensions M-by-N, and I am
using "corr2" to calculate the two-dimensional correlation coefficient
between them. The second matrix is "almost similar" to the first one,
but its columns are rotated in relation to the columns of the first
one.

So, I am using "corr2" as a way to compute the similarity between these
two matrices. As one is shifted to the other, I compute "corr2" between
them, rotate by one column one of the matrices, compute "corr2" between
them, then rotate again, compute "corr2", and so on...

Each time I rotate one of the matrices, I keep the correlation
coefficient. At the end, when all columns are shifted I end up with a
vector of correlation coefficients. Then I compute
max(vector_coef_corr) to see where the two matrices are most similar to
each other.

My problem is that, as my matrices have a large number of columns, the
circular shifting is a time consuming procedure (of course I know that
"corr2" is also a time consuming procedure, but I _have_ to use this
function - as it is part of the idea of my algorithm). How can I speed
the circular shifting process? I am using a for loop (argh!!!!!)
nowadays, because I couldn't thing in any other solution (-:. Is there
a way to vectorize this thing?

Here you have a piece of my code:

corrCoef = zeros(1, numColMatrix01);
for shiftSize = 1:numColMatrix01,
corrCoef(shiftSize) = corr2(Matrix01, Matrix02);
Matrix01 = circshift(Matrix01, [0 shiftSize]);
end;
corrCoef = max(corrCoef);

Many thanks in advance,
JKvdPoel



.

Relevant Pages

  • Re: Why is C# 450% slower than C++ on nested loops ??
    ... The posted benchmark was crucial to ... > compilers generate for the loop and get over with it. ... > additions in the outer loops, which the C# compiler doesn't. ... gotten around to implementing every possible optimization in every language, ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Bit-order reversal (little-endian <--> big-endian)
    ... The only thing I did with your do loop is ... copy and paste it into a benchmark app. ... Certainly you can use a standard if then statement instead of the IIF. ... design is faster as it avoids extra iterations. ...
    (microsoft.public.vb.general.discussion)
  • Re: Test cpu speed
    ... Certainly if you run this benchmark on two CPUs with exactly the same ... CPU will run these faster. ... possibly exceeding the instruction cache. ... As the loop contents ...
    (comp.soft-sys.matlab)
  • Re: circshift, slow?
    ... I also find that circshift is very slow. ... In some cases much slower than naive fortran-style programming with a loop, so you could try this for your problem. ... I often use loops of the following kind, I have a set of coordinates, and I want to re-use a matrix that is a solution to one pair of coordinates, to calculate for example the total potential from a set of point charges. ... % use the solution PHI, but shift it to new coordinates, and calculate the total potential. ...
    (comp.soft-sys.matlab)
  • Re: string comparison
    ... > hoops to "make it work". ... No need to jump through hoops: ... My gut feeling is that the loop with eq will ... I'll try benchmark later. ...
    (comp.lang.perl.misc)