Efficient Code for Filling Rows of an Array involving Indices Ranges

Hello,

I have an array A of zeros. I need to set a range of column indices for each row of A to ones. These ranges are determined by elements of another vector B, specifying start and end indices for the ranges for each row. For example, this is what I'm trying to figure out:

The first row of B indicates that the first row of A should have ones from columns 1 to 3. The second row of B indicates that the second row of A should have ones from columns 2 to 4 etc.

I could code this with a for-loop that goes through each of the rows and creates indices with the colon operator however, I'm hoping for a smarter, more efficient way to do it than that.

Can anyone help me with this or any suggestions?

Thanks.

Answer 1

[Matt J]

Edited - bsxfun is now obsolete

Awidth=4;
B=[1,3; 2 4; 1 1];

e=1:Awidth;

A= B(:,1)<=e & e<=B(:,2)

A = 3x4 logical array
   1   1   1   0
   0   1   1   1
   1   0   0   0

[Mohammad Abouali]

nice

[Matt J]

Thanks. The syntax is brief, but I still think a for-loop will be more efficient.

Answer 2

[Ray]

Hi All,

I implemented the above and acquired the average execution times for each approach:

The for-loop approach is the most efficient.

On a larger matrix (50000x20) the results are similar however, the approach suggested by Guillaume takes a bit longer ~0.2 seconds.

Thanks to everyone for their replies and help.

[Matt J]

This was with a for-loop across columns, correct?

Answer 3

[Guillaume]

I don't think there's a more efficient way of doing it than with a loop. The following would work, but it's arguable that it does not involve loops because of the cellfun, and it's certainly convoluted:

A=A';
bounds = sub2ind(size(A), B', repmat(1:size(B, 1), size(B, 2), 1));
indices = cellfun(@(b) b(1):b(2), num2cell(bounds, 1), 'UniformOutput', false);
A([indices{:}]) = 1;
A=A';

[Matt J]

I don't think there's a more efficient way of doing it than with a loop.

I don't think so either, nor do I expect a loop's performance to be bad.

Answer 4

[Joseph Cheng]

so... it is certainly a brain teaser to do this without a loop. so far i'm up to this.

A=zeros(3,4);
B = [1 3;2 4;1 1];

a=A';
B=B+repmat([0:4:4*(size(B,1)-1)]',1,2)
a(B)=1
a=a'

which leaves just filling in the zeros between ones without looping.

Answer 5

[Matt J]

     [M,N]=size(A);
       e=(1:M).';
      idx1=sub2ind([M,N], e, B(:,1));

       idx2a=B(:,2)<N;   
      idx2b=sub2ind([M,N], e(idx2a), B(idx2a,2)+1);

      A(idx1)=1;
      A(idx2b)=-1;
      A=cumsum(A,2)

Answer 6

[Kyle Duckworth]

Hi Ray,

I know this question is a decade old but I stumbled across it when I was trying to solve a very similar problem. I am posting this for the other users who may still come across this page even years later. I scoured forums for a long time trying to figure out how to do this without loops and unfortunately couldn't find an answer that I think we're both looking for.

I have found a solution that is concise and very fast. It's actually relatively simple. Here are the steps.

Start with array A of any size (I'm going to use your example)

A = zeros([3,4]);

A =

0 0 0 0

0 0 0 0

0 0 0 0

Create array of size n x 2, where n is equal to the number of rows in A. This array will contain our range of indices. The lower bound is in the left column and the upper bound is in the right (again, using your example).

B = ([1, 3; 2, 4; 1, 1]);

B =

1 3

2 4

1 1

Now this is where the magic happens. Define a new array C with 1 row and the same number of columns as A. Fill it in with linspace() so that element 1 is numbered 1, element 2 is numbered 2, etc.

C = linspace(1,numel(A(1,:)),numel(A(1,:)));

C =

1 2 3 4

Use repmat() to duplicate the rows of this matrix n times, where n is the number of rows in A.

C = repmat(C,numel(A(:,1)),1);

C =

1 2 3 4

1 2 3 4

1 2 3 4

Now you will simply return all values of C that are greater than or equal to the first column of B and less than or equal to the second column of B.

idx = C >= B(:,1) & C <= B(:,2);

idx =

3×4 logical array

1 1 1 0

0 1 1 1

1 0 0 0

We can now use idx an an index for A. Per your example, we'll change all of these values to ones.

A(idx) = 1;

A =

1 1 1 0

0 1 1 1

1 0 0 0

Full code:

A = zeros([3,4]);

B = ([1, 3; 2, 4; 1, 1]);

C = linspace(1,numel(A(1,:)),numel(A(1,:)));

C = repmat(C,3,1);

idx = C >= B(:,1) & C <= B(:,2);

A(idx) = 1;

Hope someone finds this useful.

[Kyle Duckworth]

By the way, in your specific example you don't need to define a new index called idx to reference those values in A. You could just set A equal to what idx was supposed to be and convert it from logicals to integers. I wrote the code to be general in cases when you want to do something like this where you are not just turning zeros to ones but some numbers to any other number.

[Catalytic]

No, this is very inefficient, especially in the way C is created. You could just do -

A=zeros(3,4);
B = ([1, 3; 2, 4; 1, 1]);
C = 1:width(A);
A = double(C >= B(:,1) & C <= B(:,2))

A = 3x4

1 1 1 0 0 1 1 1 1 0 0 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

It ends up being about the same as the accepted answer.

[Matt J]

I mentioned in my comments 10 years ago that I thought an explicit for-loop could not be beaten. To my surprise, the Accepted answer does beat a loop, at least it does in R2023-4. This answer's proposal does not beat a loop, though, neither in speed nor code-conciseness:

M=3000;N=4000;
A = zeros([M,N]);
B = randi(N,M,2);

isequal(version1(A,B), version2(A,B), versionLoop(A,B))

ans = logical
   1

timeit(@() version1(A,B))

ans = 0.0945

timeit(@() version2(A,B))

ans = 0.0193

timeit(@() versionLoop(A,B))

ans = 0.0674

function A=version1(A,B)

    C = linspace(1,numel(A(1,:)),numel(A(1,:)));
    C = repmat(C,height(A),1);
    idx = C >= B(:,1) & C <= B(:,2);
    A(idx) = 1;

end

function A=version2(A,B)

    C = 1:width(A);
    A=double(C >= B(:,1) & C <= B(:,2));

end

function A=versionLoop(A,B)

    for i=1:height(B)
        A(i,B(i,1):B(i,2))=1;
    end

end