How to generate a single vector of block-consecutive values from 2 vectors of same size without a loop ?

Hello, I have 2 vectors of same size let's say a = [3 7 19 22] and b = [5 10 20 24]

And from those 2 vectors I want to generate without a loop a single vector:

v = [a(1):b(1) a(2):b(2) ... a(end):b(end)].

so here v=[3 4 5 7 8 9 10 19 20 22 23 24].

I found linspaceNDim(a,b,N) on File Exchange Linearly spaced multidimensional matrix without loop but it doesn't work here as I dont want a fixed number of values between a(i) and b(i), but only block-consecutive values : a(i):b(i). So here N is changing at each index i.

I tried a:.b but this syntax doesn't work on Matlab.

Thanks for you help.

[Amro]

here is a similar question on Stack Overflow: Vectorized array creation from a list of start/end indices

Answer 1

[José-Luis]

Any particular reason you don't want to use a loop? This is one of those cases where you should use one, if performance is an issue. Arrayfun() is just syntactic sugar around a loop. Plus the added overheads of invoking cell arrays:

a = [3 7 19 22];
b = [5 10 20 24];

tic
your_mat = cell2mat(arrayfun(@(x,y) x:y,a,b,'uniformoutput',false));
toc 
tic
   numEl = b - a;
   pos = 1;
   your_data = NaN * ones(sum(numEl),1);
   for ii = 1:numel(numEl)
       your_data(pos:pos+numEl(ii)) = a(ii):b(ii);
       pos = pos + numEl(ii) + 1;
   end
toc

 Elapsed time is 0.000602 seconds.
 Elapsed time is 0.000038 seconds.

EDIT

I had made a mistake, the pre-allocation should read:

 your_data = NaN * ones(sum(numEl) + numel(numEl),1);

EDIT

A bit cleaner:

vals = reshape(sort(randperm(10^6,1000)),2,[]);
a = vals(1,:);
b = vals(2,:);
tic
   offset = b - a;
   numVal = sum(offset + 1);
   pos = 1;
   your_data = ones(numVal,1);
   for ii = 1:numel(offset)
       your_data(pos:pos+offset(ii)) = a(ii):b(ii);
       pos = pos + offset(ii) + 1;
   end
toc

[jyloup p]

Why you wrote

 NaN * ones(sum(numEl) + numel(numEl),1);

instead of zeros(sum(numEl),1) for example ? Is NaN useful here for allocating memory ?

[José-Luis]

I had done the pre-allocation wrong. Please replace by:

 your_data = ones(b(end),1);

or

 your_data = (sum(numEl) + numel(numEl),1);

Answer 2

[Andrei Bobrov]

v = a(1):b(end);
v = v(any(bsxfun(@ge,v,a.')&bsxfun(@le,v,b.')));

other variant

zo = zeros(b(end) - a(1) + 2,1);
zo(a - a(1) + 1) = 1;
zo(b - a(1) + 2) = -1;
t = cumsum(zo(1:end-1)) > 0;
out = a(1):b(end);
v = out(t);

Answer 3

[Sean de Wolski]

There's also FEX:mcolon which does exactly what you're looking for and has a mex implementation that may very well be the fastest.

[jyloup p]

Wow I'm impressed, this solution might be the quickest in fact, although hard and long to code. Sorry for my bad comparison José-Luis as I didn't realize limits were overlapping by generating a and b like I did. I finally compared those 3 methods (JL's loop, mcolon and Andrei's cumsum method) with :

vals = reshape(sort(randperm(10^6,1000)),2,[]);
a = vals(1,:);
b = vals(2,:);

and indeed mcolon gets Gold medal for time computation : about twice faster than the JL's loop, and ten times faster than Andrei's trick. Anyway the 3 solutions are good. The previous suggestions by Azzi and JL, alghouth compact to write, using cell2mat(fun,...) and bsxfun are prohibitive here. An example of times I got (1st time : Andrei's cumsum, 2nd time : JL's loop, 3rd time: mcolon)

>> concatetest
Elapsed time is 0.047985 seconds.
Elapsed time is 0.010318 seconds.
Elapsed time is 0.004613 seconds.
>> concatetest
Elapsed time is 0.049128 seconds.
Elapsed time is 0.011598 seconds.
Elapsed time is 0.005588 seconds.
>> concatetest
Elapsed time is 0.055113 seconds.
Elapsed time is 0.010911 seconds.
Elapsed time is 0.005586 seconds.

Strangely, I wonder why such a function is not naturally present in Matlab, like an operator like a.:b which would apply element-by-elements for 2 vectors a, b instead of scalars a,b, as we usually do for example with a.^b, a.*b, etc...

Or maybe dot is useless : a:steps:b would be mcolon(a,steps,b) where steps is the steps vectors, a and b the left and right bound vectors, and a:b would be implicit steps equal to 1.

Maybe in a future version ? Currently, unfortunately, with a=[2 4 7]; b=[3 6 8] I get

a:b = [2 3] applying operator ":" only to first elements a(1) and b(1).

The fact this feature is not implemented in Matlab is not obvious to me.

Answer 4

[Azzi Abdelmalek]

cell2mat(arrayfun(@(x,y) x:y,a,b,'un',0))

[Amro]

slightly simplified: cell2mat(arrayfun(@colon,a,b,'un',0))

Answer 5

[jyloup p]

OK that function cell2mat(arrayfun(@(x,y) x:y,a,b,'un',0)) answers my question. However I wouldn't have believed that a loop is quicker than a "Matlab compact way" to do it in fact. So finally compact ways are not always quicker than using a loop, then I will keep the loop do create v=[... a(i):b(i)...] .

Thanks anyway for your solution.

Answer 6

[jyloup p]

Ok I tested the four solutions you proposed to me. Andrei Bobrov's variant solution is the best one in term of "Matlab compact code" and time computation. Here is what i get :

    a = [3 7 19 22];
    b = [5 10 20 24];

% First solution  : cell2mat (José-Luis and Azzi Abdelmalek)
tic
your_mat = cell2mat(arrayfun(@(x,y) x:y,a,b,'uniformoutput',false));
toc
% 2nd solution : usual loop (José Luis)
tic 
 numEl = b - a;
 pos = 1;
 your_data = NaN * ones(sum(numEl),1);
 for ii = 1:numel(numEl)
     your_data(pos:pos+numEl(ii)) = a(ii):b(ii);
     pos = pos + numEl(ii) + 1;
 end
toc
% 3rd solution : bsxfun, Matlab compact style (Andrei Bobrov)
tic
v = a(1):b(end);
v = v(any(bsxfun(@ge,v,a.')&bsxfun(@le,v,b.')));
toc
% 4th solution : cumsum, Matlab compact style (Andrei Bobrov) : Quicker than ones above !!! :-)
tic
zo = zeros(b(end) - a(1) + 2,1);
zo(a - a(1) + 1) = 1;
zo(b - a(1) + 2) = -1;
t = cumsum(zo(1:end-1)) > 0;
out = a(1):b(end);
v = out(t);
toc

Results I get :

>> concate
Elapsed time is 0.001004 seconds.
Elapsed time is 0.000070 seconds.
Elapsed time is 0.000214 seconds.
Elapsed time is 0.000060 seconds.
>> concate
Elapsed time is 0.005388 seconds.
Elapsed time is 0.000086 seconds.
Elapsed time is 0.003414 seconds.
Elapsed time is 0.000081 seconds.
>> concate
Elapsed time is 0.000961 seconds.
Elapsed time is 0.000066 seconds.
Elapsed time is 0.000198 seconds.
Elapsed time is 0.000048 seconds.

First and 3rd solutions with cell2mat and bsxfun are the longest .

Usual loop (2nd solution) and 4th tricky solution by Andrei Bobrov are the quickest .

His last variant with cumsum is exactly the kind of solution I was looking for : fast-process and compact code !

Now how could I create .: operator with operator (or something else) so that a.:b = v ? The point in .: means I apply element by element the : operator, as we do usually in Matlab like a.*b, a.^b, etc.. So here :

a.:b = [a(1):b(1) a(2):b(2) ... a(end):b(end)] ? (that supposes numel(a) = numel(b) )

Thanks a lot to all of you for your clever solutions ! :-)

Answer 7

[jyloup p]

I did another series of tests on big vecors:

a = randi(500,1,100);
a=cumsum(a);
b=randi(500,1,100);
b=b+a;
b=cumsum(b);

Clearly the optimal solution is the one using cumsum.

As the methods using cell2mat and bsxfun are really long, I didn't display here. Generally I got those times :

(First time : usual loop, Second time : Method using cumsum by A. Bobrov) :

Elapsed time is 0.891365 seconds.
Elapsed time is 0.052555 seconds.
>> concate
Elapsed time is 0.948875 seconds.
Elapsed time is 0.057470 seconds.
>> concate
Elapsed time is 0.899819 seconds.
Elapsed time is 0.047447 seconds.
>> concate
Elapsed time is 0.895576 seconds.
Elapsed time is 0.049850 seconds.
>> concate
Elapsed time is 0.879542 seconds.
Elapsed time is 0.052174 seconds.
>> concate
Elapsed time is 0.901438 seconds.
Elapsed time is 0.048106 seconds.
>> concate
Elapsed time is 0.881922 seconds.
Elapsed time is 0.045292 seconds.

[jyloup p]

For small vectors, times are indeed almost the same (slightly quicker for "cumsum" method). But for big vectors, last method looks better. For example with those big vectors:

a = randi(1000000,1,10);
a=cumsum(a);
b=randi(1000000,1,10);
b=b+a;
b=cumsum(b);

I got this:

>> concatetest
Elapsed time is 1.775804 seconds.
Elapsed time is 0.956663 seconds.
>> concatetest
Elapsed time is 2.136480 seconds.
Elapsed time is 1.154071 seconds.
>> concatetest
Elapsed time is 2.180276 seconds.
Elapsed time is 1.307082 seconds.
>> concatetest
Elapsed time is 2.445985 seconds.
Elapsed time is 1.243243 seconds.
>> concatetest
Elapsed time is 2.328341 seconds.
Elapsed time is 1.118973 seconds.
>> concatetest
Elapsed time is 1.295947 seconds.
Elapsed time is 0.768078 seconds.
>> concatetest
Elapsed time is 1.976929 seconds.
Elapsed time is 1.066276 seconds.

[José-Luis]

That's not a fair comparison. If you generate your limits like that, with common intervals, then the for loop produces garbage. Also the pre-allocation becomes meaningless and the output keeps changing size, leading to poor performance.

If the data is set with non-overlapping intervals, like in the original question, then the loop is still faster:

vals = reshape(sort(randperm(10^6,1000)),2,[]);
a = vals(1,:);
b = vals(2,:);

tic
   offset = b - a;
   numVal = sum(offset + 1);
   pos = 1;
   your_data = ones(numVal,1);
   for ii = 1:numel(offset)
       your_data(pos:pos+offset(ii)) = a(ii):b(ii);
       pos = pos + offset(ii) + 1;
   end
toc
tic
    zo = zeros(b(end) - a(1) + 2,1);
    zo(a - a(1) + 1) = 1;
    zo(b - a(1) + 2) = -1;
    t = cumsum(zo(1:end-1)) > 0;
    out = a(1):b(end);
    v = out(t);
toc

Elapsed time is 0.003596 seconds.
Elapsed time is 0.024514 seconds.

That being said, I am always impressed by Andrei's tricks.