Simplify for-loop for big data

Question

I'm building a speech recognition based on time-aligned distance, and I have data like this :

tes = 1 x 160 double
refr = 1 x 54 double

and I do this following

[rows,A] = size(tes);
[rows,B] = size(refr);    
matr = zeros(A);
for b = 1:A
    for e = b+1:A
        tes_pot = tes(1,b:e);
        matr(b,e) = TA(tes_pot,refr);
    end
end

where the TA is the following function:

function ans = TA(test, ref)

[rows,N] = size(test);
[rows,M] = size(ref);

if(N>M)
    for ix = 1:N
    Y{ix} = fix(M/N*ix);
    end
else
    for ix = 1:M
    Y{ix} = fix(N/M*ix);
    end
end

Y = cell2mat(Y);
Y(Y == 0) = 1;

if(N>M)
    for j=1:N
    d(j)=abs(test(j)-ref(Y(1,j)));
    end
else
    for j=1:M
    d(j)=abs(ref(j)-test(Y(1,j)));
    end
end

ans = sum(d);

It works well, but when I execute this for many refr data, it takes so long (about more than 15 minutes to execute 100 refr data) to execute this. Is there any help to simplify this code?

Answer 1

Your function TA can be re-written as

function val = TA(test, ref)

    N = size(test,2);
    M = size(ref,2);

    Y = fix( (1:max(M,N)) * min(M,N)/max(M,N) );
    Y(Y == 0) = 1;

    if (N>M)    
        d = abs(test-ref(Y));
    else    
        d = abs(ref-test(Y));    
    end

    val = sum(d);

end

This will be faster, because:

• you didn't pre-allocate variables before the loops; this necessitates re-sizing the variable on each iteration, which is slow
• at least one if has been eliminated; branching is relatively slow on most modern CPUs. Where easy to avoid, avoid.
• you think bottom-up (a matrix is nothing more than a container of values) rather than top-down (a matrix is the value, it just happens to be compound). MATLAB specializes in the latter; you can make much bigger steps.

Answer 2

Without knowing exactly why you wrote what you wrote, here are some basic things to speed it up:

• compute the ratio M/N or N/M just once (division is slow)
• vectorize instead of using for loops (for loops are much slower)

With those two changes, I believe the following has the same functionality as your original code - but is probably significantly faster because of the lack of for loops:

[rows,N]=size(test);
[rows,M]=size(ref);
if (N>M) 
  nn = N;
  mult = M/N;
else
  nn = M;
  mult = N/M;
end
Y = fix(mult * (1:nn));
Y(Y == 0) = 1;
ans = sum(abs(test - ref(Y(1,:)))); % confirm that the shape of these two is the same? I think it is...

It may be possible to speed up your outer loops as well, but it's a bit hard to figure out exactly what you are doing there... But since you are executing the outer loop 160 times and the inner loop "up to" 160 times as well, any savings in the inner loop ought to help. With that, you can shave a little more off with

[rows,A]=size(tes);
[rows,B]=size(refr);    
matr=zeros(A);
for b = 1:A
    for e = b+1:A
        matr(b,e) = TA(tes(1,b:e),refr); % don't make a separate variable each time
    end
end

Let me know if this is any faster!

Answer 3

Here is a different approach - instead of computing the indices where you want to do the match "manually", this computes the resampled shape of the reference signal just once (for all sizes), then matches to all possible locations in the signal. It does the same "in spirit" but clearly is not an identical calculation. But it only takes 0.6 seconds. Might be worth taking a look to see if this would actually work for you:

N = 160;
M = 54;
tes = rand(1, N);
refr = rand(1, M);
tes(35:35+M-1)=tes; % create a point where correlation is good

% every possible segment of refr - size 2 to N - is scaled to match tes
% then the mean of the absolute differences is taken

tic
matr = zeros(N, N);

% first - case where segment of tes is less than refr:
for e=2:N
    xx = linspace(1,M,e);
    rr = interp1(1:M, refr, xx); % compute linear interpolation just once for each size
    for b = 1:N-e                % match this size at each possible point in the signal
        matr(b,e) = mean(abs(tes(b+(1:e))-rr)); % using mean to remove difference due to # of samples
    end
end

figure
imagesc(matr)                    % show the distribution of values: a hot spot indicates a "match"
axis image; axis xy; axis off    % get "right way around", square, no labels
toc

Timing:

Elapsed time is 0.551464 seconds

Image:

Obviously, if there is a good correlation between the signals, you would see a "cold spot" in the corresponding location in the image - which I simulated by copying a little bit of the template into the signal.