Fully vectorized concatenation of multiple ranges?

Hello all,

I've been looking for an efficient way to concatenate an arbitrarily large set of ranges.

For example:

lower_bounds = [1, 5, 20, 50]
upper_bounds = [2, 10, 40, 100]
output = unknown_magic(lower_bounds, upper_bounds)

output =
[1:2 5:10 20:40 50:100]

I've seen similar questions asked, but none addressed this issue directly. The closest question I could find on the Internet was at stackoverflow.

I have found a semi-working solution, which incurs some unnecessary overhead because it uses cells:

output = cell2mat (arrayfun( @(x,y)(x:y), lower_bounds, upper_bounds, 'UniformOutput', false))

However, the arrayfun throws an error ("Non-scalar in Uniform output") unless I pass the argument 'UniformOutput', false. Using this argument incurs the cell array overhead. I use cell2mat to convert back to the concatenated ranges.

If anyone else has a similar problem I hope my makeshift solution works for you until someone posts a better method.

Answer 1

[Andrei Bobrov]

lo = [1, 5, 20, 50]
up = [2, 10, 40, 100]

n = cumsum([1;up(:) - lo(:) + 1]);
z = ones(n(end)-1,1);
z(n(1:end-1)) = [lo(1),lo(2:end)-up(1:end-1)];
out = cumsum(z);

in two row:

x = cumsum(accumarray(cumsum([1;up(:)-lo(:)+1]),[lo(:);0]-[0;up(:)]-1)+1);
out = X(1:end-1);

[Michael]

Brillant!

It appears as if you make a vector of ones, then encode the gaps between the ranges. The final step cumulatively sums which is "continuous" over each range then jumps the gap!

[Daniel]

Awesome

Answer 2

[Guillaume]

This looks very much like one of my cody problems.

I don't think you'll find a more efficient solution. You need a cell array anyway to store all the matrices for each range. The alternative is to store them directly into the final matrix and that would involve multiple resizing since you don't know beforehand the size of the final matrix. This is bound to be slower.

It takes around 2.5 seconds on my machine to process a million bounds. I think that's reasonable.

[Michael]

Actually you can compute the size in advance as the sum of differences between lower and upper, each offset by one

   upper_prime = upper+1;
   preallocate = sum(upper_prime - lower);