Fast ways to generate multiple sequences without using for loop

Hi all,

Suppose, I have two arrays:

startIds = [x1, x2, x3]
endIds = [y1, y2, y3]

The two arrays have the same length and can be long. We may assume that (endIds(ii)-startIds(ii)) are the same for all positions ii. Is there any fast ways to generate multiple sequences without using for loop?

startIds(1):endIds(1)
startIds(2):endIds(2)
startIds(3):endIds(3)

Thanks!

-Thang

Answer 1

[Walter Roberson]

range = endIds(1) - startIds(1);
[t1, t2] = ndgrid(startIds, 0:range);
t3 = t1 + t2;

[Walter Roberson]

range = endIds(1) - startIds(1);
t3 = bsxfun(@plus, startIds(:), 0:range);

[Thang Luong]

Yes! This is what I have been looking for. The last version with bsxfun is the fastest one, three times faster than the for-loop version, which is, in turn, faster than the other versions with arrayfun and ndgrid. See the benchmark below:

N = 128;
range = 40;
startIds = 1:N;
endIds = startIds + range-1;
% sol1: arrayfun
tic
indices = cell2mat(arrayfun(@(x) startIds(x):endIds(x), 1:N, 'UniformOutput',false));
toc
% sol2: for loop
tic
indices1 = zeros(1, N*range);
for ii=1:N
  indices1(range*(ii-1)+1:range*ii) = startIds(ii):endIds(ii);
end
toc
% sol3: ndgrid
tic
[t1, t2] = ndgrid(0:range-1, startIds);
indices2 = reshape(t1 + t2, 1, []);
toc
% sol4: bsxfun
tic
indices3 = reshape(bsxfun(@plus, startIds(:), 0:range-1)', 1, []);
toc
assert(sum(abs(indices - indices1))==0);
assert(sum(abs(indices - indices2))==0);
assert(sum(abs(indices - indices3))==0);

Running time:

Elapsed time is 0.000927 seconds.
Elapsed time is 0.000169 seconds.
Elapsed time is 0.000223 seconds.
Elapsed time is 0.000064 seconds.

Answer 2

[Geoff Hayes]

Thang - you could use a combination of arrayfun with cell2mat to produce the desired result.

For example, if we assume (as you have stated) that (endIds(ii)-startIds(ii)) are identical for all ii then

 startIds = [1 2 3];
 endIds   = [12 13 14];
 cell2mat(arrayfun(@(x)startIds(x):endIs(x),1:length(startIds), 'UniformOutput',false)')

would produce the following

     1     2     3     4     5     6     7     8     9    10    11    12
     2     3     4     5     6     7     8     9    10    11    12    13
     3     4     5     6     7     8     9    10    11    12    13    14

We arrayfun to a apply the anonymous function

 @(x)startIds(x):endIds(x)

to each of the pairs in startIds and endIds (much like your for loop would do). We then transpose this result (which becomes a 3x1 cell array of 1x12 elements each) and convert it to a matrix using cell2mat.

Try the above and see what happens!

[Thang Luong]

Hi Geoff,

Thanks a lot for your answer. It's elegant. Unfortunately, it seems that for loop is still faster in this case. I tried the following benchmark:

N = 128;
  M = 40;
  startIds = 1:N;
  endIds = startIds + M-1;
  tic
  indices = cell2mat(arrayfun(@(x) startIds(x):endIds(x), 1:N, 'UniformOutput',false));
  toc
  tic
  indices1 = zeros(1, N*M);
  for ii=1:N
    indices1(M*(ii-1)+1:M*ii) = startIds(ii):endIds(ii);
  end
  toc

Here're the running times:

Elapsed time is 0.001588 seconds.
Elapsed time is 0.000172 seconds.

-Thang

[Walter Roberson]

You didn't ask about fast ways to do it: you asked about doing it without a for loop.

[Thang Luong]

Thanks for pointing that out. I've just updated the question title.