MATLAB Central Newsreader - Faster and vectorized

Faster and vectorized

Oleg Komarov — Thu, 29 Oct 2009 10:33:21 -0400

Dear all,
i've been using a user defined function, written more than one year ago, without any problem on small datasets. Since I started to work on a bigger dataset the computational time raised significanlty, i ask you therefore to help me to optimize this function.

I need to compute weighted means (by row) grouped into classes

Ssize = 100;
% Example Inputs:
% Generate Values
Values = 10.*rand(Ssize); Values(ceil(100.*rand(Ssize/2))) = NaN;
% Generate Weights
Weights = 50000.*rand(Ssize); Weights(ceil(100.*rand(Ssize/2))) = NaN;
% Generate Classes to which values belong
Class = floor(Ssize/10.*rand(Ssize));

tic;
    Out = WeMean(Values, Weights, Class);
toc;

% Elapsed time is 0.011368 seconds for Ssize = 100;
% Elapsed time is 7.054131 seconds for Ssize = 1000;

The number of elements raised by a factor of 100, the time 7.054131/0.011368 > 600.
I let you imagine what happens if Ssize = 10000.

% FUNCTION HERE
function Out = WeMean(Values, Weights, Class)

% All three inputs might come from different datasets/computations so i need to "align" Class
Class(isnan(Values) | isnan(Weights)) = 0; % Note that class doesn't have NaN by construction

% Unique classes (0 is not a class)
unC = setdiff(unique(Class), 0)';

% Preallocate OUT
Out = NaN(size(Values,1)+1, length(unC));
% header row
Out(1,:) = unC;

% LOOP by class
for i = 1 : length(unC)
   % Index the specific class
    IDX = Class == unC(1,i);

   % Filter the values and the weights which belong to the class
    TempV = zeros(size(Values));
    TempV(IDX) = Values(IDX);
    TempW = zeros(size(Weights));
    TempW(IDX) = Weights(IDX);
    % Denominator by row
    Den = sum(TempW, 2);
    % Numerator by row
    Num = sum(TempV.*TempW,2);
    % weighted mean by row
    Out(2:end,i) = Num./Den;
end

i tried to vectorize the summations (for the den and num computation) using accumarray. I avoided the loop with a subfunction which computed vectorized grouped sums. I reduced the computation time by half but accumulated eps (the approzimation is still far over e-15).

Thanks in advance!

Oleg

Re: Faster and vectorized

roger — Thu, 29 Oct 2009 12:36:46 -0400

On Oct 29, 11:33 am, "Oleg Komarov" <oleg.koma...@hotmail.it> wrote:
> Dear all,
> i've been using a user defined function, written more than one year ago, without any problem on small datasets. Since I started to work on a bigger dataset the computational time raised significanlty, i ask you therefore to help me to optimize this function.
>
> I need to compute weighted means (by row) grouped into classes
>
> Ssize = 100;
> % Example Inputs:
> % Generate Values
> Values = 10.*rand(Ssize); Values(ceil(100.*rand(Ssize/2))) = NaN;
> % Generate Weights
> Weights = 50000.*rand(Ssize); Weights(ceil(100.*rand(Ssize/2))) = NaN;
> % Generate Classes to which values belong
> Class = floor(Ssize/10.*rand(Ssize));
>
> tic;
> Out = WeMean(Values, Weights, Class);
> toc;
>
> % Elapsed time is 0.011368 seconds for Ssize = 100;
> % Elapsed time is 7.054131 seconds for Ssize = 1000;
>
> The number of elements raised by a factor of 100, the time 7.054131/0.011368 > 600.
> I let you imagine what happens if Ssize = 10000.
>
> % FUNCTION HERE
> function Out = WeMean(Values, Weights, Class)
>
> % All three inputs might come from different datasets/computations so i need to "align" Class
> Class(isnan(Values) | isnan(Weights)) = 0; % Note that class doesn't have NaN by construction
>
> % Unique classes (0 is not a class)
> unC = setdiff(unique(Class), 0)';
>
> % Preallocate OUT
> Out = NaN(size(Values,1)+1, length(unC));
> % header row
> Out(1,:) = unC;
>
> % LOOP by class
> for i = 1 : length(unC)
> % Index the specific class
> IDX = Class == unC(1,i);
>
> % Filter the values and the weights which belong to the class
> TempV = zeros(size(Values));
> TempV(IDX) = Values(IDX);
> TempW = zeros(size(Weights));
> TempW(IDX) = Weights(IDX);
> % Denominator by row
> Den = sum(TempW, 2);
> % Numerator by row
> Num = sum(TempV.*TempW,2);
> % weighted mean by row
> Out(2:end,i) = Num./Den;
> end
>
> i tried to vectorize the summations (for the den and num computation) using accumarray. I avoided the loop with a subfunction which computed vectorized grouped sums. I reduced the computation time by half but accumulated eps (the approzimation is still far over e-15).
>
> Thanks in advance!
>
> Oleg

losing the temp arrays may make it a bit faster. other than that
you'll just have to live with the fact that matlab is slow with loops.

for i = 1 : length(unC)
   % Index the specific class
    IDX = Class == unC(1,i);

    % weighted mean by row
    Out(2:end,i) = sum(Values(IDX).*Weights(IDX),2)./sum(Weights(IDX),
2);
end

Re: Faster and vectorized

Oleg Komarov — Thu, 29 Oct 2009 16:11:03 -0400

> losing the temp arrays may make it a bit faster. other than that
> you'll just have to live with the fact that matlab is slow with loops.
>
> for i = 1 : length(unC)
> % Index the specific class
> IDX = Class == unC(1,i);
>
> % weighted mean by row
> Out(2:end,i) = sum(Values(IDX).*Weights(IDX),2)./sum(Weights(IDX),
> 2);
> end
Well i loose the matrix form of the inputs if i dont make use of the temp matrices...
unfortunately i can't suppress them in that way.

Re: Faster and vectorized

roger — Thu, 29 Oct 2009 16:22:27 -0400

On Oct 29, 5:11 pm, "Oleg Komarov" <oleg.koma...@hotmail.it> wrote:
> > losing the temp arrays may make it a bit faster. other than that
> > you'll just have to live with the fact that matlab is slow with loops.
>
> > for i = 1 : length(unC)
> > % Index the specific class
> > IDX = Class == unC(1,i);
>
> > % weighted mean by row
> > Out(2:end,i) = sum(Values(IDX).*Weights(IDX),2)./sum(Weights(IDX),
> > 2);
> > end
>
> Well i loose the matrix form of the inputs if i dont make use of the temp matrices...
> unfortunately i can't suppress them in that way.

not really sure what you mean by that, if you intialize them the right
way it shouldn't make a difference.
Out(IDX,i) = ... may work in that sense. In fact if you make sure the
matrices are intialized the right way you may be able to make IDX a
matrix and use a matrix index into matrices.

Re: Faster and vectorized

Bruno Luong — Thu, 29 Oct 2009 17:03:19 -0400

Try this:

function Out = WeMean(Values, Weights, Class)

Class(isnan(Values) | isnan(Weights)) = 0;
[unC trash C] = unique(Class);
[m n] = size(Class);
I = repmat((1:m).',1,n);
K = [I(:) C(:)];
sz = [m length(unC)];
Den = accumarray(K, Weights(:), sz);
Num = accumarray(K, Values(:).*Weights(:), sz);
filled = accumarray(K, 1, sz);
Out = Num./Den;
header = unC(2:end).';
Out= [header; Out(:,2:end)];
Out(~filled)=NaN; % faster than fill with accumarray

% Bruno

Re: Faster and vectorized

Bruno Luong — Thu, 29 Oct 2009 17:19:18 -0400

The below way of indexing is more correct:

...
idx = unC ~= 0;
header = unC(idx).';
Out= [header; Out(:,idx)];
...

% Bruno

Re: Faster and vectorized

Bruno Luong — Thu, 29 Oct 2009 17:44:02 -0400

Oops, one more bug corrected

function Out = WeMean(Values, Weights, Class)

Class(isnan(Values) | isnan(Weights)) = 0;
[unC trash C] = unique(Class);
[m n] = size(Class);
I = repmat((1:m).',1,n);
K = [I(:) C(:)];
sz = [m length(unC)];
Den = accumarray(K, Weights(:), sz);
Num = accumarray(K, Values(:).*Weights(:), sz);
filled = accumarray(K, 1, sz);
Out = Num./Den;
idx = unC ~= 0;
Out(filled>0)=NaN; % faster than fill with accumarray
header = unC(idx).';
Out= [header; Out(:,idx)];

% Bruno

Re: Faster and vectorized

Oleg Komarov — Thu, 29 Oct 2009 18:13:05 -0400

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hcck92$28n$1@fred.mathworks.com>...
> Oops, one more bug corrected
>
> function Out = WeMean(Values, Weights, Class)
>
> Class(isnan(Values) | isnan(Weights)) = 0;
> [unC trash C] = unique(Class);
> [m n] = size(Class);
> I = repmat((1:m).',1,n);
> K = [I(:) C(:)];
> sz = [m length(unC)];
> Den = accumarray(K, Weights(:), sz);
> Num = accumarray(K, Values(:).*Weights(:), sz);
> filled = accumarray(K, 1, sz);
> Out = Num./Den;
> idx = unC ~= 0;
> Out(filled>0)=NaN; % faster than fill with accumarray
> header = unC(idx).';
> Out= [header; Out(:,idx)];
>
> % Bruno

There's something in the:
> Out(filled>0)=NaN; % faster than fill with accumarray
row that doesn't work the right way. The output is all NaNs...

Re: Faster and vectorized

Oleg Komarov — Thu, 29 Oct 2009 18:39:06 -0400

> There's something in the:
> Out(filled>0)=NaN; % faster than fill with accumarray
> row that doesn't work the right way. The output is all NaNs...
replaced ">" with "==";

BRUNO'S

function Out = WeMean2(Values, Weights, Class)
Class(isnan(Values) | isnan(Weights)) = 0; % Align Class to Values and Weights
[unC, ~, C] = unique(Class); % Unique di Class and col sub
[m n] = size(Class); % Class dimensions
I = repmat((1:m).',1,n); % row sub
K = [I(:) C(:)]; % subs
sz = [m length(unC)]; % Out dimensions
Den = accumarray(K, Weights(:), sz); % Denominator
Num = accumarray(K, Values(:).*Weights(:), sz); % Numerator
Out = Num./Den; % Output
filled = accumarray(K, 1, sz); % Clear not filled with NaN
Out(filled == 0) = NaN; % major sign replaced with ==
% Place header
idx = unC ~= 0;
header = unC(idx).';
Out= [header; Out(:,idx)];
end

MINE
(look at the first post)

Perfomance check and same result..

for Ssize = 10:100:900;
Values = 10.*rand(Ssize); Values(ceil(100.*rand(Ssize/2))) = NaN; % Generate Values
Weights = 50000.*rand(Ssize); Weights(ceil(100.*rand(Ssize/2))) = NaN; % Generate Weights
Class = floor(Ssize*2/5.*rand(Ssize)); % Generate Classes to which values belong

tic; A = WeMean(Values, Weights, Class); toc; % Mine
tic; B = WeMean2(Values, Weights, Class); toc; % Bruno's

isequalwithequalnans(A,B); % always verified
end

Elapsed time is 0.001306 seconds.
Elapsed time is 0.001084 seconds.

Elapsed time is 0.033996 seconds.
Elapsed time is 0.008017 seconds.

Elapsed time is 0.232533 seconds.
Elapsed time is 0.028339 seconds.

Elapsed time is 0.714834 seconds.
Elapsed time is 0.063467 seconds.

Elapsed time is 1.705921 seconds.
Elapsed time is 0.077690 seconds.

Elapsed time is 2.787658 seconds.
Elapsed time is 0.166200 seconds.

Elapsed time is 4.025173 seconds.
Elapsed time is 0.222698 seconds.

Elapsed time is 6.259864 seconds.
Elapsed time is 0.259810 seconds.

Elapsed time is 9.305980 seconds.
Elapsed time is 0.376411 seconds.

And the winneeeeeerrr is BRUNO!

I tried to implement a solution with accumarray but as i wrote in the firt post but could't accomplish what u did.

Re: Faster and vectorized

Oleg Komarov — Wed, 04 Nov 2009 18:49:04 -0500

> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hcck92$28n$1@fred.mathworks.com>...

> > Out(filled==0)=NaN; % faster than fill with accumarray
> > % Bruno
>
I would also add that results differ slightly if using inbuilt fill option.