Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Is there any way to vectorize/ speed up calculation?

Subject: Is there any way to vectorize/ speed up calculation?

From: Pete sherer

Date: 30 Nov, 2012 19:35:08

Message: 1 of 6

Hi,

I have example data below. First column indicating block, second column indicating sub-block, and 3rd column shows values.

What I need to do is to
1. find max and sum value per block
2. for each block, count how many sub-blocks have values greater than threshold (i.e., thres)

I have the for...loop below to do it, but for my actual, large data it takes very long time to compute.

tdata= [3153,90493,182; ...
    3155,4584,305258;...
    3155,4585,102274;...
    4000, 2, 9;...
    5001, 4, 50000;...
    5001, 10, 400; ...
    6500, 1 , 500;...
    6500, 1, 1000];

thres = [10000 100000];
nThres= length(thres);

flExc = repmat( tdata(:,3), 1, nThres) > repmat( thres, length(tdata(:,3)), 1); % repeat by #thresholds

uniqCol1 = unique( tdata(:,1));
maxVal = zeros( length(uniqCol1), 1);
sumVal = zeros( length(uniqCol1), 1);
tcnt = zeros( length(uniqCol1), nThres);
for runi= 1:length( uniqCol1) % 1: nYrs
    tindx = (tdata(:,1)== uniqCol1( runi));
    maxVal( runi,1)= max( tdata(tindx,3),[],1);
    sumVal( runi,1)= sum( tdata(tindx,3),1);
    tcnt(runi,:) = sum( flExc(tindx,:), 1); % [ #uniqYrs, #Thres]
end % for runi

Thanks,
Pete

Subject: Is there any way to vectorize/ speed up calculation?

From: Roger Stafford

Date: 1 Dec, 2012 00:49:09

Message: 2 of 6

"Pete sherer" wrote in message <k9b1pc$cvq$1@newscl01ah.mathworks.com>...
> I have example data below. First column indicating block, second column indicating sub-block, and 3rd column shows values.
>
> What I need to do is to
> 1. find max and sum value per block
> 2. for each block, count how many sub-blocks have values greater than threshold (i.e., thres)
>
> I have the for...loop below to do it, but for my actual, large data it takes very long time to compute.
>
> tdata= [3153,90493,182; ...
> 3155,4584,305258;...
> 3155,4585,102274;...
> 4000, 2, 9;...
> 5001, 4, 50000;...
> 5001, 10, 400; ...
> 6500, 1 , 500;...
> 6500, 1, 1000];
>
> thres = [10000 100000];
> nThres= length(thres);
>
> flExc = repmat( tdata(:,3), 1, nThres) > repmat( thres, length(tdata(:,3)), 1); % repeat by #thresholds
>
> uniqCol1 = unique( tdata(:,1));
> maxVal = zeros( length(uniqCol1), 1);
> sumVal = zeros( length(uniqCol1), 1);
> tcnt = zeros( length(uniqCol1), nThres);
> for runi= 1:length( uniqCol1) % 1: nYrs
> tindx = (tdata(:,1)== uniqCol1( runi));
> maxVal( runi,1)= max( tdata(tindx,3),[],1);
> sumVal( runi,1)= sum( tdata(tindx,3),1);
> tcnt(runi,:) = sum( flExc(tindx,:), 1); % [ #uniqYrs, #Thres]
> end % for runi
- - - - - - - - -
  I think if 'nThres' is large, the calculation of 'flExc' may be the source of a large part of your computation time. This way you are having to compare every "value" with every threshold. It might pay you to sort 'thres' and use it as the "edges" argument in the 'histc' function, once for each unique block number. The computation time would then only be proportional to the log of the number of thresholds. The first argument in 'histc' for each block would be the "values" for the set of subblocks associated with that block. The returned 'bin' count would constitute an entire row of 'tcnt'. The order in each row would of course be that of the sorted 'thres'. If you want the original order of 'thres', you would have to make use of the second argument returned by the 'sort' function.

  Also instead of using "tdata(:,1)==uniqCol1(runi)" to compute 'tindx', which is probably a comparatively heavy drain on your CPU time, you should either use the colon operator if your 'tdata' are already sorted as shown in your example, or else make proper use of the third argument returned by "unique(tdata(:,1))" and then the colon operator.

Roger Stafford

Subject: Is there any way to vectorize/ speed up calculation?

From: Pete sherer

Date: 1 Dec, 2012 02:42:11

Message: 3 of 6

nThres is actually 1-by-3 array. It's the length( uniqCol1) that is large, about 500k. Each block has about 4-5 sub-blocks, so the total number of rows is about 2-2.5M rows.

Since it has to run the loop, here 500k times it's just not fast at all.

This line computes really fast:
flExc = repmat( tdata(:,3), 1, nThres) > repmat( thres, length(tdata(:,3)), 1);

That's why I want to find ways to avoid loops and do something like above if possible.

Thanks,
Pete

Subject: Is there any way to vectorize/ speed up calculation?

From: Pete sherer

Date: 1 Dec, 2012 04:49:13

Message: 4 of 6

Thanks Roger. I tried colon operator and it works amazingly fast since I don't need to find indx in every loop.

tdata = sortrows( tdata,[1 2 3]);
flExc = repmat( tdata(:,3), 1, nThres) > repmat( thres, length(tdata(:,3)), 1);

        [ uniqCol1, endIndx] = unique( tdata(:,1));
        stIndx= [1; 1+endIndx(1:end-1)];
        maxVal = zeros( length(uniqCol1), 1);
        sumVal = zeros( length(uniqCol1), 1);
        tcnt = zeros( length(uniqCol1), nThres);
        for runi= 1:length( uniqCol1) % 1: nYrs
            tindx = [stIndx(runi):endIndx(runi)];
            maxVal( runi,1)= max( tdata(tindx,3),[],1);
            sumVal( runi,1)= sum( tdata(tindx,3),1);
            tcnt(runi,:) = sum( flExc(tindx,:), 1); % [ #uniqYrs, #Thres]
        end % for runi

Subject: Is there any way to vectorize/ speed up calculation?

From: Roger Stafford

Date: 1 Dec, 2012 05:15:13

Message: 5 of 6

"Pete sherer" wrote in message <k9bqq3$pst$1@newscl01ah.mathworks.com>...
> nThres is actually 1-by-3 array. It's the length( uniqCol1) that is large, about 500k. Each block has about 4-5 sub-blocks, so the total number of rows is about 2-2.5M rows.
>
> Since it has to run the loop, here 500k times it's just not fast at all.
>
> This line computes really fast:
> flExc = repmat( tdata(:,3), 1, nThres) > repmat( thres, length(tdata(:,3)), 1);
>
> That's why I want to find ways to avoid loops and do something like above if possible.
>
> Thanks,
> Pete
- - - - - - - - -
  Well, that rules out the use of 'histc'. However, there is all the more reason to get rid of the line

 tindx = (tdata(:,1)==uniqCol1( runi));

  Try this:

t = sortrows(tdata,[1,2]); % <-- Do this if tdata is not already sorted
v = t(:,3);
E = bsxfun(@gr,v,thres);
f = find([true;diff(t(:,1))>0;true]);
n = length(f)-1;
sumVal = zeros(n,1);
maxVal = zeros(n,1);
tcnt = zeros(n,size(E,2));
for k = 1:n
  r = f(k):f(k+1)-1;
  sumVal(k) = sum(v(r),1);
  maxVal(k) = max(v(r),[],1);
  tcnt(k,:) = sum(E(r,:),1);
end

  You can also consider using the function 'accumarray'. It can presumably vectorize your whole processing but I don't know whether it would be faster or not.

Roger Stafford

Subject: Is there any way to vectorize/ speed up calculation?

From: Bruno Luong

Date: 1 Dec, 2012 07:32:14

Message: 6 of 6

Try this
 tdata= [3153,90493,182; ...
    3155,4584,305258;...
    3155,4585,102274;...
    4000, 2, 9;...
    5001, 4, 50000;...
    5001, 10, 400; ...
    6500, 1 , 500;...
    6500, 1, 1000];

thres = [10000 100000]

% Engine:
[u, ~, J] = unique(tdata(:,1));
val = tdata(:,3);
sumVal = accumarray(J, val)
maxVal = accumarray(J, val, [], @max)

[J C] = ndgrid(J, 1:length(thres));
tcnt = bsxfun(@gt, val, thres);
tcnt = accumarray([J(:) C(:)], tcnt(:))

% Bruno

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us