Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
find the column index of the first occurance of a value in each row

Subject: find the column index of the first occurance of a value in each row

From: metaug

Date: 19 Aug, 2010 16:01:28

Message: 1 of 18

I have a matrix A where
A=[1 0 0;
   0 1 1;
   1 1 1;
   0 0 1]

I need to find the column index of the first occurance of 1 in each row. So in the example above, the resulting vector B should be:
B=[1;2;1;3]

Does anyone have any idea how to do it?

Many thanks!

Subject: find the column index of the first occurance of a value in each row

From: Sean

Date: 19 Aug, 2010 16:46:48

Message: 2 of 18

metaug <hxhu76@gmail.com> wrote in message <1339137264.30660.1282233718285.JavaMail.root@gallium.mathforum.org>...
> I have a matrix A where
> A=[1 0 0;
> 0 1 1;
> 1 1 1;
> 0 0 1]
>
> I need to find the column index of the first occurance of 1 in each row. So in the example above, the resulting vector B should be:
> B=[1;2;1;3]
>
> Does anyone have any idea how to do it?
>
> Many thanks!

One way:
%Data
 A=[1 0 0;
    0 1 1;
    1 1 1;
    0 0 1];

%Engine
idx = find(A);
[r c] = ind2sub(size(A),idx);
cmin = accumarray(r,c,[],@min)

Subject: find the column index of the first occurance of a value in each row

From: Matt Fig

Date: 19 Aug, 2010 17:01:17

Message: 3 of 18

For a binary matrix, as shown in your example:

[idx,idx] = max(A,[],2);
idx

Subject: find the column index of the first occurance of a value in each row

From: Sean

Date: 19 Aug, 2010 17:26:31

Message: 4 of 18

"Matt Fig" <spamanon@yahoo.com> wrote in message <i4jo0s$6sb$1@fred.mathworks.com>...
> For a binary matrix, as shown in your example:
>
> [idx,idx] = max(A,[],2);
> idx

Matt, that will return an incorrect result if a row has all zeros.

Also, to simplify mine from above: it could just be:
[r c] = find(A); %skip finding linear indices and the call to ind2sub

Subject: find the column index of the first occurance of a value in each row

From: Matt Fig

Date: 19 Aug, 2010 17:35:22

Message: 5 of 18

"Sean " <sean.dewolski@nospamplease.umit.maine.edu> wrote in message <i4jpg7$c7t$1@fred.mathworks.com>...
> "Matt Fig" <spamanon@yahoo.com> wrote in message <i4jo0s$6sb$1@fred.mathworks.com>...
> > For a binary matrix, as shown in your example:
> >
> > [idx,idx] = max(A,[],2);
> > idx
>
> Matt, that will return an incorrect result if a row has all zeros.
>
> Also, to simplify mine from above: it could just be:
> [r c] = find(A); %skip finding linear indices and the call to ind2sub

Good point! I would ask what the OP wants to do in such a case.
For example:

A = [0 0 0 0;1 0 1 0;0 0 1 1;0 0 0 1]

[h,cmin2] = max(A,[],2);
cmin2 = cmin2.*h

Now this matches your ACCUMARRAY solution. Still for binary matrices.

Subject: find the column index of the first occurance of a value in each row

From: Matt Fig

Date: 19 Aug, 2010 17:51:10

Message: 6 of 18

I am using 2007b, on XP 64. I am surprised to find that the niave FOR loop is WAY faster than either of our solutions. Sean, what are you using, and is this still true?


N = 5000;
A = round(rand(N));


cmin3 = zeros(N,1);
for ii=1:N
    for jj = 1:N
        if A(ii,jj)
            cmin3(ii) = jj;
            break
        end
    end
end

Subject: find the column index of the first occurance of a value in each row

From: Bruno Luong

Date: 19 Aug, 2010 17:59:24

Message: 7 of 18

metaug <hxhu76@gmail.com> wrote in message <1339137264.30660.1282233718285.JavaMail.root@gallium.mathforum.org>...
> I have a matrix A where
> A=[1 0 0;
> 0 1 1;
> 1 1 1;
> 0 0 1]
>
> I need to find the column index of the first occurance of 1 in each row. So in the example above, the resulting vector B should be:
> B=[1;2;1;3]
>
> Does anyone have any idea how to do it?
>
> Many thanks!

This does exactly what you want:

http://www.mathworks.com/matlabcentral/fileexchange/24641-vectorized-find-with-first-option

>> B = findfirst(A,2)

B =

     1
     2
     1
     3

% Bruno

Subject: find the column index of the first occurance of a value in each row

From: Sean

Date: 19 Aug, 2010 18:10:26

Message: 8 of 18

"Matt Fig" <spamanon@yahoo.com> wrote in message <i4jque$du4$1@fred.mathworks.com>...
> I am using 2007b, on XP 64. I am surprised to find that the niave FOR loop is WAY faster than either of our solutions. Sean, what are you using, and is this still true?
>
>
> N = 5000;
> A = round(rand(N));
>
>
> cmin3 = zeros(N,1);
> for ii=1:N
> for jj = 1:N
> if A(ii,jj)
> cmin3(ii) = jj;
> break
> end
> end
> end

Very Nice!
I am able to replicate that (64bit Mac with R2009b):
%%%
N = 5000;
A = round(rand(N));

tic
[r c] = find(A);
cmin1 = accumarray(r,c,[],@min);
toc
tic
[h,idx] = max(A,[],2);
cmin2 = h.*idx;
toc
tic
cmin3 = zeros(N,1);
for ii=1:N
    for jj = 1:N
        if A(ii,jj)
            cmin3(ii) = jj;
            break
        end
    end
end
toc
isequal(cmin1,cmin2,cmin3)

%{

Elapsed time is 2.553398 seconds.
Elapsed time is 0.068724 seconds.
Elapsed time is 0.000727 seconds.

ans =

     1
%}

Subject: find the column index of the first occurance of a value in each row

From: Sean

Date: 19 Aug, 2010 18:18:23

Message: 9 of 18

"Sean " <sean.dewolski@nospamplease.umit.maine.edu> wrote in message <i4js2i$suu$1@fred.mathworks.com>...
> "Matt Fig" <spamanon@yahoo.com> wrote in message <i4jque$du4$1@fred.mathworks.com>...
> > I am using 2007b, on XP 64. I am surprised to find that the niave FOR loop is WAY faster than either of our solutions. Sean, what are you using, and is this still true?
> >
> >
> > N = 5000;
> > A = round(rand(N));
> >
> >
> > cmin3 = zeros(N,1);
> > for ii=1:N
> > for jj = 1:N
> > if A(ii,jj)
> > cmin3(ii) = jj;
> > break
> > end
> > end
> > end
>
> Very Nice!
> I am able to replicate that (64bit Mac with R2009b):

I figured out why the for loops are much faster. In that example the round function is going to force approximately half of the first column to be 1 and the second/3rd columns will soon follow. Thus the jj-loop never has to traverse particularly deep.

I padded the rows with N zeros at the front and time tested it:
N = 5000;
A = [false(N),round(rand(N))];

tic
[r c] = find(A);
cmin1 = accumarray(r,c,[],@min);
toc
tic
[h,idx] = max(A,[],2);
cmin2 = h.*idx;
toc
tic
cmin3 = zeros(N,1);
for ii=1:N
    for jj = 1:2*N
        if A(ii,jj)
            cmin3(ii) = jj;
            break
        end
    end
end
toc
isequal(cmin1,cmin2,cmin3)

%{

Elapsed time is 2.775707 seconds.
Elapsed time is 0.143720 seconds.
Elapsed time is 0.906551 seconds.

ans =

     1
%}

Subject: find the column index of the first occurance of a value in each row

From: Matt Fig

Date: 19 Aug, 2010 18:23:20

Message: 10 of 18

"Sean " <sean.dewolski@nospamplease.umit.maine.edu> wrote in message
> I figured out why the for loops are much faster. In that example the round function is going to force approximately half of the first column to be 1 and the second/3rd columns will soon follow. Thus the jj-loop never has to traverse particularly deep.
>
> I padded the rows with N zeros at the front and time tested it:
> N = 5000;
> A = [false(N),round(rand(N))];


Padding is an ultra worst-case for sure. A more likely worst case (perhaps) would be a sparse A.

A = rand(N)>.9 % Or even .99 -- whatever.

Subject: find the column index of the first occurance of a value in each

From: metaug

Date: 19 Aug, 2010 18:41:51

Message: 11 of 18

Thanks Sean and Mike for your help! Mike, it seems that the naive FOR loop has advantange unless the column size is small. I am using R2009b:

N = 50000;
A = round(rand(N,10));

cmin3 = zeros(N,1);
tic;
for ii=1:size(A,1)
for jj = 1:size(A,2)
if A(ii,jj)
cmin3(ii) = jj;
break
end
end
end
toc;

tic;
[r,c] = find(A==1,1);
cmin = accumarray(r,c,[],@min);
toc;
Elapsed time is 0.022715 seconds.
Elapsed time is 0.005505 seconds.

Subject: find the column index of the first occurance of a value in each

From: metaug

Date: 19 Aug, 2010 18:52:24

Message: 12 of 18

Thanks, Bruno. It not only does what I want, but more!

Subject: find the column index of the first occurance of a value in each

From: Bruno Luong

Date: 19 Aug, 2010 19:05:41

Message: 13 of 18

You can't use FIRST option with FIND, because it does work globally, and not row-wise.
 
Here is the timings including the FINDFIRST Mex file:

N = 50000;
A = round(rand(N,10));

tic
[r c] = find(A);
cmin1 = accumarray(r,c,[],@min);
toc % 0.163066 seconds

tic;
% Yoi should count the preallocation to be fair
cmin3 = zeros(N,1);
for ii=1:size(A,1)
    for jj = 1:size(A,2)
        if A(ii,jj)
            cmin3(ii) = jj;
            break
        end
    end
end
toc; % 0.110102 seconds.

tic;
cmin4 = findfirst(A,2);
toc; % 0.001611 seconds.

isequal(cmin1,cmin3)
isequal(cmin3,cmin4)

% Bruno

Subject: find the column index of the first occurance of a value in each

From: Romain W

Date: 10 May, 2013 11:35:10

Message: 14 of 18

Hi Bruno,

The file does not seem to work on my Linux machine, any idea why this would happen?

Thank you very much for your reply,
Romain

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <i4jva5$k4$1@fred.mathworks.com>...
> You can't use FIRST option with FIND, because it does work globally, and not row-wise.
>
> Here is the timings including the FINDFIRST Mex file:
>
> N = 50000;
> A = round(rand(N,10));
>
> tic
> [r c] = find(A);
> cmin1 = accumarray(r,c,[],@min);
> toc % 0.163066 seconds
>
> tic;
> % Yoi should count the preallocation to be fair
> cmin3 = zeros(N,1);
> for ii=1:size(A,1)
> for jj = 1:size(A,2)
> if A(ii,jj)
> cmin3(ii) = jj;
> break
> end
> end
> end
> toc; % 0.110102 seconds.
>
> tic;
> cmin4 = findfirst(A,2);
> toc; % 0.001611 seconds.
>
> isequal(cmin1,cmin3)
> isequal(cmin3,cmin4)
>
> % Bruno

Subject: find the column index of the first occurance of a value in each

From: Bruno Luong

Date: 10 May, 2013 11:53:09

Message: 15 of 18

"Romain W" wrote in message <kmim1e$rb1$1@newscl01ah.mathworks.com>...

> The file does not seem to work on my Linux machine, any idea why this would happen?
>

My crystal ball is not effective today.

Bruno

Subject: find the column index of the first occurance of a value in each

From: Romain W

Date: 10 May, 2013 12:28:10

Message: 16 of 18

Sorry for the lack of details provided to your crystal ball input. But between us, crystal balls are becoming more and more obsolete these days.

So, the problem I have might be straighforward to solve but my lack of knowledge in the use of mex files could be the reason. Put simply, when I run the function findfirst, this error message is what I obtain:

Error using find1dmex
FIND1DMEX: incorrect int32 definition (modify MEX file is required)

I have run the install file beforehand and there was not problem at all.

Thanks in advance to those who can enlighten me!

Romain

I was thus wondering if this problem could be linked to the fact that I am a Linux user and as indicated in the file exchange page, you did not try it using a Linux machine.

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kmin35$s4$1@newscl01ah.mathworks.com>...
> "Romain W" wrote in message <kmim1e$rb1$1@newscl01ah.mathworks.com>...
>
> > The file does not seem to work on my Linux machine, any idea why this would happen?
> >
>
> My crystal ball is not effective today.
>
> Bruno

Subject: find the column index of the first occurance of a value in each

From: Bruno Luong

Date: 10 May, 2013 12:44:11

Message: 17 of 18

Try to replace the definition in line #30 of the code find1dmex.c as bellow, then recompile the code (run installation script)

/* Define correct type depending on platform
  You might have to modify here depending on your compiler */
#if defined(_MSC_VER) || defined(__BORLANDC__)
typedef __int64 int64;
typedef __int32 int32;
typedef __int16 int16;
typedef __int8 int08;
#else /* LINUX + LCC, CAUTION: not tested by the author */
#include <stdint.h>
typedef int64_t int64;
typedef int32_t int32;
typedef int16_t int16;
typedef int8_t int08;
#endif

% Bruno

Subject: find the column index of the first occurance of a value in each

From: Romain W

Date: 10 May, 2013 13:01:09

Message: 18 of 18

Neattt, this does work like a charm and will speed up my code, again thank you very much for your help.

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kmiq2r$9fa$1@newscl01ah.mathworks.com>...
> Try to replace the definition in line #30 of the code find1dmex.c as bellow, then recompile the code (run installation script)
>
> /* Define correct type depending on platform
> You might have to modify here depending on your compiler */
> #if defined(_MSC_VER) || defined(__BORLANDC__)
> typedef __int64 int64;
> typedef __int32 int32;
> typedef __int16 int16;
> typedef __int8 int08;
> #else /* LINUX + LCC, CAUTION: not tested by the author */
> #include <stdint.h>
> typedef int64_t int64;
> typedef int32_t int32;
> typedef int16_t int16;
> typedef int8_t int08;
> #endif
>
> % Bruno

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us