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:
how to calculate piecewise average faster?

Subject: how to calculate piecewise average faster?

From: Jingbo

Date: 16 Aug, 2010 19:33:05

Message: 1 of 6

Hi,

I'm looking for a fast way to calculate piecewise average of a vector.
For example
A=[5 3 7 9 8 9 7 7 1 1 4 3 8 6 2 1 4 5 0 2];
the number of points of every piece (3, 4, 5, 3, 5) is known
I want to obtain a vector contains piecewise average of A
B=[(5+3+7)/3, (7+8+9+7)/4, (7+1+1+4+3)/5, (8+6+2)/3, (1+4+5+0+2)/5];
  =[5 7.75 3.2 5.3 2.4];
Build another vector
C=[5 5 5 7.75 7.75 7.75 7.75 3.2 3.2 3.2 3.2 3.2 5.3 5.3 5.3 2.4 2.4 2.4 2.4 2.4];

The final vector I want is
D=A-C
  =[0 -2 2 1.25 0.25 1.25 -0.75 3.8 -2.2 -2.2 0.8 -0.2 2.7 0.7 -3.3 -1.4 1.6 2.6 -2.4 -0.4];

My existing implementation is using a for loop to calculate avg of each segment and remove it.

My question is how to do it faster because for loop is slow. or is there any function in Matlab can do it fast?

Thanks a lot

Subject: how to calculate piecewise average faster?

From: Walter Roberson

Date: 16 Aug, 2010 19:37:11

Message: 2 of 6

Jingbo wrote:
>
> I'm looking for a fast way to calculate piecewise average of a vector.
> For example
> A=[5 3 7 9 8 9 7 7 1 1 4 3 8 6 2 1 4 5 0 2];
> the number of points of every piece (3, 4, 5, 3, 5) is known
> I want to obtain a vector contains piecewise average of A

> My existing implementation is using a for loop to calculate avg of each
> segment and remove it.

> My question is how to do it faster because for loop is slow. or is there
> any function in Matlab can do it fast?

If you do not need very high precision and none of your values are infinite or
nan, then use cumsum() to construct a running total of the values. Once you
have the running total, the average from point K of length N is
(runningtotal(K+N-1)-runningtotal(K)) / N
and that is a calculation that can be vectorized
(hint: cumsum the piece lengths to get the starting points K)

Subject: how to calculate piecewise average faster?

From: Bruno Luong

Date: 16 Aug, 2010 20:15:22

Message: 3 of 6

"Jingbo " <duanjb@gmail.com> wrote in message <i4c3pg$7gt$1@fred.mathworks.com>...
> Hi,
>
> I'm looking for a fast way to calculate piecewise average of a vector.
> For example
> A=[5 3 7 9 8 9 7 7 1 1 4 3 8 6 2 1 4 5 0 2];
> the number of points of every piece (3, 4, 5, 3, 5) is known
> I want to obtain a vector contains piecewise average of A
> B=[(5+3+7)/3, (7+8+9+7)/4, (7+1+1+4+3)/5, (8+6+2)/3, (1+4+5+0+2)/5];
> =[5 7.75 3.2 5.3 2.4];
> Build another vector
> C=[5 5 5 7.75 7.75 7.75 7.75 3.2 3.2 3.2 3.2 3.2 5.3 5.3 5.3 2.4 2.4 2.4 2.4 2.4];
>
> The final vector I want is
> D=A-C
> =[0 -2 2 1.25 0.25 1.25 -0.75 3.8 -2.2 -2.2 0.8 -0.2 2.7 0.7 -3.3 -1.4 1.6 2.6 -2.4 -0.4];
>

The below is vectorized and does not suffer from cumsum accuracy problem.

% Data
A = [5 3 7 9 8 9 7 7 1 1 4 3 8 6 2 1 4 5 0 2];
l = [3 4 5 3 5];

% Engine
clear ind
ind(cumsum([1 l])) = 1;
ind = cumsum(ind(1:end-1));
C = accumarray(ind(:),A(:))./l(:);
C = reshape(C(ind),size(A))
D = A-C

% Bruno

Subject: how to calculate piecewise average faster?

From: Jingbo

Date: 17 Aug, 2010 00:56:04

Message: 4 of 6

Thank you very much

Walter Roberson <roberson@hushmail.com> wrote in message
> If you do not need very high precision and none of your values are infinite or
> nan, then use cumsum() to construct a running total of the values. Once you
> have the running total, the average from point K of length N is
> (runningtotal(K+N-1)-runningtotal(K)) / N
> and that is a calculation that can be vectorized
> (hint: cumsum the piece lengths to get the starting points K)

Subject: how to calculate piecewise average faster?

From: Jingbo

Date: 17 Aug, 2010 01:01:05

Message: 5 of 6

It seems that accumarray takes a lot of time. So I use running total mentioned by Walter to calculate the average. Now it becomes much faster.

Thanks for these clever codes.

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
>
> The below is vectorized and does not suffer from cumsum accuracy problem.
>
> % Data
> A = [5 3 7 9 8 9 7 7 1 1 4 3 8 6 2 1 4 5 0 2];
> l = [3 4 5 3 5];
>
> % Engine
> clear ind
> ind(cumsum([1 l])) = 1;
> ind = cumsum(ind(1:end-1));
> C = accumarray(ind(:),A(:))./l(:);
> C = reshape(C(ind),size(A))
> D = A-C
>
> % Bruno

Subject: how to calculate piecewise average faster?

From: Bruno Luong

Date: 17 Aug, 2010 09:40:26

Message: 6 of 6

"Jingbo " <duanjb@gmail.com> wrote in message <i4cn0h$esg$1@fred.mathworks.com>...
> It seems that accumarray takes a lot of time.

Something is not right ACCUMARRAY time is similar according to my test (script below). And it does not suffer of accuracy (see the plot) when the size get larger:

%% Generate data
l=ceil(20*rand(1,1e5)); % random sublengths, varying in (1,20)
A=rand(1,sum(l));
fprintf('length(A) = %d\n', length(A));

%% cumsum
tic
clear loc
B = [0 cumsum(A)];
ind = cumsum([1 l]);
loc(ind) = 1;
loc = cumsum(loc(1:end-1));
C = diff(B(ind))./l;
C1 = reshape(C(loc),size(A));
t1=toc; % 0.052789 [s]

%% accumarray
tic
clear ind
ind(cumsum([1 l])) = 1;
ind = cumsum(ind(1:end-1));
C = accumarray(ind(:),A(:),[length(l) 1]) ./ l(:);
C2 = reshape(C(ind),size(A));
t2=toc; % 0.047468 [s]

fprintf('cumsum time = %f [s]\n', t1);
fprintf('accumarray time = %f [s]\n', t2);
win = 1000;
plot(conv(abs(C1-C2), ones(1,win),'valid'));

% 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