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:
faster way to add certain elements ?

Subject: faster way to add certain elements ?

From: Juliette Salexa

Date: 15 Jun, 2010 17:04:04

Message: 1 of 11

Hello,

I have the array:

A=[1 ;
     2 ;
     3 ;
     4 ;
     5 ;
     6 ;
     7 ;
     8 ;
     9]

And I want to produce the array:

B=[1+4+7;
     1+4+7;
     1+4+7;
     2+5+8 ;
     2+5+8 ;
     2+5+8 ;
     3+6+9 ;
     3+6+9 ;
     3+6+9 ]

I've tried the following methods, but they are both too slow when A is large (~ size=4^14,1) and the method is part of a loop that's iterated 1000s of times.
==============================
METHOD 1:

A=expand(sum(reshape(A,length(A)/3,3),2),[3,1]);

where expand is:
http://www.mathworks.com/matlabcentral/fileexchange/24536-expand

I'm aware that expand is an m-file and reshape is built-in, but based on the output of my profiler, the reshape is still taking a significant percentage of time.

I've also tried splitting it up:

B=zeros(length(A)/3,3);
B=reshape(A,length(A)/3,3);
A=expand(sum(B,2),[3,1]);

But the difference in time is less than a second.

I think reshape might be slow because matlab stores elements column-wise, and by using reshape it has to find three new contiguous blocks of memory and store some elements along rows ?
==============================
METHOD 2:

repetitionIndex=repmat((1:3)',3,1);
A=expand(accumarray(repetitionIndex,A(:)),[3,1]);

This method is a little bit slower than method 1, probably because repetitionIndex is taking up extra memory, but I'm again not 100% sure.

==============================

Does anyone think there's a faster way ??

Any suggestions or discussion would be extremely appreciated.
Juliette

Subject: faster way to add certain elements ?

From: Doug Schwarz

Date: 15 Jun, 2010 17:17:54

Message: 2 of 11

Juliette Salexa wrote:
> Hello,
>
> I have the array:
>
> A=[1 ;
> 2 ;
> 3 ;
> 4 ;
> 5 ; 6 ;
> 7 ;
> 8 ;
> 9]
>
> And I want to produce the array:
>
> B=[1+4+7;
> 1+4+7;
> 1+4+7;
> 2+5+8 ;
> 2+5+8 ;
> 2+5+8 ;
> 3+6+9 ;
> 3+6+9 ;
> 3+6+9 ]
>
> I've tried the following methods, but they are both too slow when A is
> large (~ size=4^14,1) and the method is part of a loop that's iterated
> 1000s of times.
> ==============================
> METHOD 1:
>
> A=expand(sum(reshape(A,length(A)/3,3),2),[3,1]);
>
> where expand is:
> http://www.mathworks.com/matlabcentral/fileexchange/24536-expand
>
> I'm aware that expand is an m-file and reshape is built-in, but based on
> the output of my profiler, the reshape is still taking a significant
> percentage of time.
>
> I've also tried splitting it up:
>
> B=zeros(length(A)/3,3);
> B=reshape(A,length(A)/3,3);
> A=expand(sum(B,2),[3,1]);
>
> But the difference in time is less than a second.
>
> I think reshape might be slow because matlab stores elements
> column-wise, and by using reshape it has to find three new contiguous
> blocks of memory and store some elements along rows ?
> ==============================
> METHOD 2:
>
> repetitionIndex=repmat((1:3)',3,1);
> A=expand(accumarray(repetitionIndex,A(:)),[3,1]);
>
> This method is a little bit slower than method 1, probably because
> repetitionIndex is taking up extra memory, but I'm again not 100% sure.
>
> ==============================
>
> Does anyone think there's a faster way ??
>
> Any suggestions or discussion would be extremely appreciated.
> Juliette


reshape never takes much time because it never moves data.

I would do it this way:

   temp = repmat(sum(reshape(A,[],3),2),1,3).';
   B = temp(:);

--
Doug Schwarz
dmschwarz&ieee,org
Make obvious changes to get real email address.

Subject: faster way to add certain elements ?

From: Sean

Date: 15 Jun, 2010 17:26:07

Message: 3 of 11

"Juliette Salexa" <juliette.physicist@gmail.com> wrote in message <hv8bq4$nv5$1@fred.mathworks.com>...
> Hello,
>
> I have the array:
>
> A=[1 ;
> 2 ;
> 3 ;
> 4 ;
> 5 ;
> 6 ;
> 7 ;
> 8 ;
> 9]
>
> And I want to produce the array:
>
> B=[1+4+7;
> 1+4+7;
> 1+4+7;
> 2+5+8 ;
> 2+5+8 ;
> 2+5+8 ;
> 3+6+9 ;
> 3+6+9 ;
> 3+6+9 ]
>
> I've tried the following methods, but they are both too slow when A is large (~ size=4^14,1) and the method is part of a loop that's iterated 1000s of times.
> ==============================
> METHOD 1:
>
> A=expand(sum(reshape(A,length(A)/3,3),2),[3,1]);
>
> where expand is:
> http://www.mathworks.com/matlabcentral/fileexchange/24536-expand
>
> I'm aware that expand is an m-file and reshape is built-in, but based on the output of my profiler, the reshape is still taking a significant percentage of time.
>
> I've also tried splitting it up:
>
> B=zeros(length(A)/3,3);
> B=reshape(A,length(A)/3,3);
> A=expand(sum(B,2),[3,1]);
>
> But the difference in time is less than a second.
>
> I think reshape might be slow because matlab stores elements column-wise, and by using reshape it has to find three new contiguous blocks of memory and store some elements along rows ?
> ==============================
> METHOD 2:
>
> repetitionIndex=repmat((1:3)',3,1);
> A=expand(accumarray(repetitionIndex,A(:)),[3,1]);
>
> This method is a little bit slower than method 1, probably because repetitionIndex is taking up extra memory, but I'm again not 100% sure.
>
> ==============================
>
> Does anyone think there's a faster way ??
>
> Any suggestions or discussion would be extremely appreciated.
> Juliette

How much RAM do you have? 4^14 of class double requires a lot of memory (2.147483648GB) and a second array the same size will require as much. If the numbers are all integers and depending on the maximum integer you have you could recast them as something that takes up less RAM.

The big question to ask is why do you need to do this and is there another way around it? It's probably unnecessary to have the same number repeated 3x over and over again.

Here's another way too:
A = [1:12]'; %to 12 so sizes are 3,4 to make it distinguishable
B = repmat(sum(reshape(A,[3 4]),2),1,3)';
C = B(:);

Subject: faster way to add certain elements ?

From: Juliette Salexa

Date: 15 Jun, 2010 18:50:22

Message: 4 of 11

Thanks Sean and Doug.

I can't see the difference between your methods though! =(

I do appreciate that using REPMAT instead of EXPAND speeds things up by about a factor of 3.

But, as I said in the initial post, the profiler suggests that RESHAPE is taking up a significant percentage of the time:

===================
A=(1:3^12)';I=rand(3^12,1);
B=zeros(length(A)/3,3)';

profile on
for i=1:1000
temp=repmat(sum(reshape(A,length(A)/3,3),2),1,3).';
A=temp(:);
A=A.*I;
end
profile viewer
===================

Out of the 57 seconds, 14.5 seconds were from using REPMAT,

If I avoid call SUM and LENGTH:

lengthOfAover3=length(A)/3;
for i=1:1000
temp=reshape(A,lengthOfAover3,3);
temp2=repmat(temp(:,1),1,3);
A=temp2(:);
A=A.*I;
end

===================

Out of the 39 seconds, 13.5 seconds were from using REPTMAT

=> which leads me to believe RESHAPE is taking the majority of the time.

Considering that I don't actually *need* the reshaped array, and that the pattern of indices over which I'm summing is very simple, I was hoping there would be a way to do this without RESHAPE.

Also, I've been told that the transpose is very costly for large matrices since matlab stores elements column-wise.

There must be a more efficient way to add every Nth element and store them in an array!



Thanks sean for your concern, but I need to use that much memory since I'm reusing the result 1000's of times and it would be a nightmare to recalculate it each time. And the reason why I'm making 3 copies of the same elements is that (as in the example above), I'm multiplying each of the 3 copies by a different number - If I could get A.*I (as in the above example) without having to make 3 copies of each element of A, that would be very nice! But I can't think of a way to do that =(


Thanks again for your help and suggestions

Subject: faster way to add certain elements ?

From: Matt J

Date: 15 Jun, 2010 19:34:04

Message: 5 of 11

"Juliette Salexa" <juliette.physicist@gmail.com> wrote in message <hv8i1e$3g4$1@fred.mathworks.com>...
seconds, 14.5 seconds were from using REPMAT,
>
> If I avoid call SUM and LENGTH:
>
> lengthOfAover3=length(A)/3;
> for i=1:1000
> temp=reshape(A,lengthOfAover3,3);
==============

As an FYI, you don't need to be computing lengthOfAover3. You can just do

temp=reshape(A,[],3);

*************************
> temp2=repmat(temp(:,1),1,3);
> A=temp2(:);
> A=A.*I;
> end
>
> ===================
>
> Out of the 39 seconds, 13.5 seconds were from using REPTMAT
>
> => which leads me to believe RESHAPE is taking the majority of the time.
=================

You're ignoring the contribution of A.*I. No doubt that contributes an appreciable fraction.


******************
> Thanks sean for your concern, but I need to use that much memory since I'm reusing the result 1000's of times and it would be a nightmare to recalculate it each time. And the reason why I'm making 3 copies of the same elements is that (as in the example above), I'm multiplying each of the 3 copies by a different number - If I could get A.*I (as in the above example) without having to make 3 copies of each element of A, that would be very nice! But I can't think of a way to do that =(
=========================

You mean you have a vector and need to multiply it by different scalars? Again, it would be good to know what that result is going to feed into. It seems like a lot of redundant calculation. In any case, you can avoid using repmat by using bsxfun instead, which is more memory efficient, e.g.

>> bsxfun(@times,[1;2;3],[10,11,12])

ans =

    10 11 12
    20 22 24
    30 33 36

Subject: faster way to add certain elements ?

From: Sean

Date: 15 Jun, 2010 19:47:04

Message: 6 of 11

"Juliette Salexa" <juliette.physicist@gmail.com> wrote in message <hv8i1e$3g4$1@fred.mathworks.com>...
> Thanks Sean and Doug.
>
> I can't see the difference between your methods though! =(
>

The only difference is I had a small typo in mine. :{

snip:
> A=(1:3^12)';I=rand(3^12,1);
> B=zeros(length(A)/3,3)';
>
>I'm multiplying each of the 3 copies by a different number - If I could get A.*I (as in the above example) without having to make 3 copies of each element of A, that would be very nice! But I can't think of a way to do that =(
>

If the numbers you gave in your examples are correct i.e. you A vector is 1:n this will also work - not sure if it's faster.

A = (1:63)';
B = ones(63,1); % just so the results are known to be right/wrong
s = length(A)/3; %length of one column if using reshape
v = [s+1:s+s]'*3; %vector of sums
v = kron(v,[1;1;1]); %repeated 3x so it lines up with second vector
C = v.*B;

Subject: faster way to add certain elements ?

From: Doug Schwarz

Date: 15 Jun, 2010 19:59:22

Message: 7 of 11

Juliette Salexa wrote:
> Thanks Sean and Doug.
>
> I can't see the difference between your methods though! =(
>
> I do appreciate that using REPMAT instead of EXPAND speeds things up by
> about a factor of 3.
> But, as I said in the initial post, the profiler suggests that RESHAPE
> is taking up a significant percentage of the time:

Then the profiler's suggestion is wrong. Reshape uses negligible time.
  All it does is change the array header that stores how many rows and
columns there are. It doesn't move any data. It is always very fast no
matter how large the argument. Always. (Did I emphasize that enough?)

As Matt said, look into bsxfun.

--
Doug Schwarz
dmschwarz&ieee,org
Make obvious changes to get real email address.

Subject: faster way to add certain elements ?

From: James Tursa

Date: 15 Jun, 2010 21:00:22

Message: 8 of 11

Doug Schwarz <see@sig.for.address.edu> wrote in message <sYQRn.44917$rU6.8009@newsfe10.iad>...
> Juliette Salexa wrote:
> > Thanks Sean and Doug.
> >
> > I can't see the difference between your methods though! =(
> >
> > I do appreciate that using REPMAT instead of EXPAND speeds things up by
> > about a factor of 3.
> > But, as I said in the initial post, the profiler suggests that RESHAPE
> > is taking up a significant percentage of the time:
>
> Then the profiler's suggestion is wrong. Reshape uses negligible time.
> All it does is change the array header that stores how many rows and
> columns there are. It doesn't move any data. It is always very fast no
> matter how large the argument. Always. (Did I emphasize that enough?)

Except for sparse matrices, where a data copy is involved. (Not this application of course).

James Tursa

Subject: faster way to add certain elements ?

From: James Tursa

Date: 15 Jun, 2010 21:12:05

Message: 9 of 11

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <hv8kjc$fvi$1@fred.mathworks.com>...
>
> In any case, you can avoid using repmat by using bsxfun instead, which is more memory efficient

e.g., for poster's original code:

A = (1:3^12)';
I = rand(3^12,1);
B = repmat(sum(reshape(A,length(A)/3,3),2),1,3).';
B = B(:).*I;

it would look something like this:

A = (1:3^12)';
I = rand(3^12,1);
Ar = reshape(sum(reshape(A,length(A)/3,3),2),1,[]);
Ir = reshape(I,3,[]);
B = bsxfun(@times,Ar,Ir);
B = B(:);

James Tursa

Subject: faster way to add certain elements ?

From: Juliette Salexa

Date: 16 Jun, 2010 17:15:21

Message: 10 of 11

Thank you everyone,
I think James Tursa's solution sped up my computation by about 1.6 hours (I have to test still)
==================
Matt J:

> As an FYI, you don't need to be computing lengthOfAover3. You can just do
> temp=reshape(A,[],3);

I think this might be slower because matlab has to calculate what the missing dimension is (when repeated 10000 times that overhead could build up)

> You're ignoring the contribution of A.*I. No doubt that contributes an appreciable fraction.

You're right, I retested, and the multiplication was actually taking longer than the RESHAPE. Thanks for pointing that out!

> You mean you have a vector and need to multiply it by different scalars?

Not quite. each element is multiplied by 3 different scalars, and those 3 scalars are different for each element.

==================

Sean:

> If the numbers you gave in your examples are correct i.e. you A vector is 1:n this will also work - not sure if it's faster.

KRON is known to be slow (about twice as slow as EXPAND for what we're doing here), since it's written to handle very general cases, and consequently isn't optimized for simple things like replicating elements.

==================

Doug:

> Then the profiler's suggestion is wrong. Reshape uses negligible time.

Thanks, sorry for doubting you =)
It turns out that (as Matt J suggested), multiplication was taking a lot of the time, so RESHAPE was only taking about 8 seconds (a third of what I thought)

==================

James:

> it would look something like this: ....

I think that works perfectly and significantly speeds up the calculation, Thanks!

==================

Summary:

replace KRON by EXPAND: 2x speedup
replace EXPAND by repmat: 3x speedup (6x speedup in total)
replace repmat by bsxfun: 2x speedup (12x speedup in total)


And this can be done in one-line (not the fastest solution, but very compact):

reshape(bsxfun(@times,reshape(sum(reshape(A,[],3),2),1,[]),reshape(I,3,[])),[],1);


Thanks again Doug, Sean, Matt J and James for your fantastic help!

Subject: faster way to add certain elements ?

From: Matt J

Date: 16 Jun, 2010 17:57:05

Message: 11 of 11

"Juliette Salexa" <juliette.physicist@gmail.com> wrote in message <hvb0r9$bdk$1@fred.mathworks.com>...

> > As an FYI, you don't need to be computing lengthOfAover3. You can just do
> > temp=reshape(A,[],3);
>
> I think this might be slower because matlab has to calculate what the missing dimension is (when repeated 10000 times that overhead could build up)
==============

I tend to doubt it. Compared to all the sums and multiplications you're doing elsewhere in the loop, this is a ridiculously small fraction of the total computation, even if temp really only does have 9 elements (I assume in reality there are more??).

Also, since reshape() is implemented in optimized C code, there's a chance that the missing dimension will be calculated in the CPU, which would be much faster than fetching lengthOfAover3 from RAM.

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