how to calculate the maximum of different parts of a vector without using a for loop?

Hi!

I have a vector H, which is separated in different events of known size, i.e. s=[2,5,7,2,...] and I want to find the maximum that corresponds to each event. How can I do it without using a for loop (I want to reduce the computational time)?

Using a for loop would be:

maxH(1) = max(H(1:s(1)));
for i=2:length(s)
  maxH(i) = max(H( 1+sum(s(1:i-1)) : sum(s(1:i-1)) + s(i) ));
end

Thanks!

[EDITED, Jan, code formatted]

[Jan]

Please learn how to format the code.

Answer 1

[Teja Muppirala]

Although I don't recommend programming like this in MATLAB, sometimes writing out the logic out explicitly can make it run extremely fast. MATLAB has become very good at loops you know:

maxH = zeros(numel(s),1);
V = 1;
thismax = -inf;
thiss = s(1);
cnt = 1;
N = numel(H);
for n = 1:N
    if cnt > thiss
        maxH(V) = thismax;
        thismax = H(n);
        V = V+1;
        cnt = 1;
        thiss = s(V);
    elseif H(n) > thismax
        thismax = H(n);
    end
    cnt = cnt+1;
end
maxH(V) = thismax;

[Teja Muppirala]

Run time comparison:

s = 1 + randi(10, 1, 1000000);
H = rand(1, sum(s));
%%%%%%%Straight up programming approach  %%%%%%%%
tic
  maxH = zeros(numel(s),1);
  V = 1;
  thismax = -inf;
  thiss = s(1);
  cnt = 1;
  N = numel(H);
  for n = 1:N
      if cnt > thiss
          maxH(V) = thismax;
          thismax = H(n);
          V = V+1;
          cnt = 1;
          thiss = s(V);
      elseif H(n) > thismax
          thismax = H(n);
      end
      cnt = cnt+1;
  end
  maxH(V) = thismax;
toc       % 0.198403 sec
%%%%%%%%ACCUMARRAY approach %%%%%%%%
tic;
idx = zeros(size(H));
idx(cumsum(s) - s +1) = 1;
maxH2 = accumarray(cumsum(idx(:)),H(:),[],@max);
toc       % 1.160289 sec

%%%%%%%%%Confirm they are equal %%%%%%%%
isequal(maxH,maxH2)

[Andrei Bobrov]

+1

[Jan]

@Teja: Runtime rules. As long as ACCUMARRAY is not multithreaded and/or you run the code on less than 12 cores, your solution is the most efficient. Therefore I see good reasons to recommend such programming techniques even in Matlab. +1

[Robert Cumming]

+1.

Answer 2

[Andrei Bobrov]

try this is code

for condition: numel(H) == sum(s)

maxH = cellfun(@max,mat2cell(H(:),s(:),1));

OR

idx = zeros(size(H));
idx(cumsum(s) - s +1) = 1;
maxH = accumarray(cumsum(idx(:)),H(:),[],@max);

[Jan]

The ACCUMARRAY approach is the fastest method under Matlab 2011b. +1

Answer 3

[Jan]

maxH    = zeros(1, length(s));  % Pre-allocate!!!
maxH(1) = max(H(1:s(1)));
cs      = cumsum(s);            % Avoid repeated summation
for ii = 2:length(s)
  maxH(ii) = max(H(1 + cs(ii - 1) : cs(ii)));
end

[EDITED] Timings:

s = 1 + randi(10, 1, 10000);
H = rand(1, sum(s));

% Original:
tic;
maxH(1) = max(H(1:s(1)));
for i=2:length(s)
  maxH(i) = max(H( 1+sum(s(1:i-1)) : sum(s(1:i-1)) + s(i) ));
end
toc      % 0.533000 seconds

% Andrei's CELLFUN:
tic;
maxH = cellfun(@max,mat2cell(H(:),s(:),1)); 
toc      % 0.080097 seconds

% Andrei's ACCUMARRAY:
tic;
idx = zeros(size(H));
idx(cumsum(s) - s +1) = 1;
maxH = accumarray(cumsum(idx(:)),H(:),[],@max);
toc      % 0.021015 seconds

% FOR-loop:
tic;
maxH    = zeros(1, length(s));  % Pre-allocate!!!
maxH(1) = max(H(1:s(1)));
cs      = cumsum(s);            % Avoid repeated summation
for ii = 2:length(s)
  maxH(ii) = max(H(1 + cs(ii - 1) : cs(ii)));
end
toc      % 0.033937 seconds

Answer 4

[Robert Cumming]

In your example above the biggest speed gain would be achieved by pre-allocating the maxH variable

   maxH = zeros(length(s),1);

note: For reference - removing the for loop will not necessarily speed things up....

Answer 5

[Merce Casas Prat]

Thanks! But I did it and as Robert suggested, this is not faster. Actually with the loop is the fastest option.

THanks anyway!