Sum elements of a vector based on given indices

I have two large vectors, values and indices. I need to sum the elements of values using indices as in this brute force example:

N = 3e7;
values = (rand(N, 1) > 0.3);
indices = cumsum(ceil(4*rand(N, 1)));
indices = [0; indices(find(indices > 1, 1, 'first'):find(indices < N, 1, 'last')); N];
HH = numel(indices) - 1;

% Brute force solution
tic
out1 = zeros(HH, 1);
for hh = 1:HH
  out1(hh) = sum(values((indices(hh)+1):indices(hh+1)));
end
toc

A more efficient way to do it is the following:

tic
indices2 = diff(indices);
new_inds = (1:HH+1)';
tmp = zeros(N, 1);
tmp(cumsum(indices2)-indices2+1)=1;
new_inds_long = new_inds(cumsum(tmp));
out2 = accumarray(new_inds_long, values);
toc

A better solution is:

tic
out3 = cumsum(values);
out3 = out3(indices(2:end));
out3 = [out3(1); diff(out3)];
toc

The three solutions are equivalent

all(out1 == out2)
all(out1 == out3)

Question is: since this is really a basic function, is there any faster, already known approach/function that does the same and that I may be overlooking or that I am just not aware of?

Answer 1

[Jonathan]

There are faster ways of accomplishing your task in Matlab.

First, let's examine if there is a function that will do what you want. Type 'methods double' for a list of functions that can act on the data type 'double'. This is not an exhaustive list, but it gives a good starting point. For example, the function 'accumarray' looks promising. However, brief experimentation does not give better results. After running through the remainder of the list, it does not look likely that a single builtin function will do what you want.

You also question if there is an already known approach that is faster. There is such an approach, and it is well known. MEX functions are functions written in C or Fortran that are compiled to be called from Matlab. Type 'doc mex' for more information. Often, this improves the final runtime of a function. With care in the implementation, this approach will improve the runtime for your case as well.