MATLAB Central Newsreader - Finding matrix elements in another

Finding matrix elements in another

dellyseas Finschild — Sat, 27 Dec 2008 16:33:01 +0000

Hi,
I have two matrices like a=[1,2,3,4,5] and b=[3,1,5].I want to find the indices of elements of b in a. I mean what is the indice of 3,1 and 5 in matrix a.I tried to use "find" but can not succeed.I dont want to use loops,is it possible in efficient way?
Thanks,

Re: Finding matrix elements in another

ImageAnalyst — Sat, 27 Dec 2008 17:09:27 +0000

On Dec 27, 11:33=A0am, "dellyseas Finschild" <amgt...@yahoo.com> wrote:
> Hi,
> I have two matrices like a=3D[1,2,3,4,5] and b=3D[3,1,5].I want to find t=
he indices of elements of b in a. I mean what is the indice of 3,1 and 5 in=
matrix a.I tried to use "find" but can not succeed.I dont want to use loop=
s,is it possible in efficient way?
> Thanks,

------------------------------------
How big are your arrays? For the example like you posted, you'll
never notice any time difference between vectorizing or using a for
loop. We're talking microseconds versus nanoseconds. Now, if your
arrays are tens of thousand of elements long, then vectorizing would
help. I don't know of a way off the top of my head where you don't
use at least one for loop, but maybe someone else does. And if
someone does come up with some elegant but tricky one-liner then
you'll have to weigh if the possible loss of straightforward,
intuitive readability is worth the time reduction against a more
understandable and readable for loop method. Could be an issue if
you're writing code that might need to be maintained by other people
months or years from now.

Re: Finding matrix elements in another

dellyseas Finschild — Sat, 27 Dec 2008 17:22:01 +0000

hi,
thanks for reply,actually you are right but the matrices i gave was just an example.Although they are not ten thousands of elements,its approximately a thousand.therefore i wanted to learn an efficient way.

thanks,

Re: Finding matrix elements in another

Roger Stafford — Sat, 27 Dec 2008 17:32:01 +0000

"dellyseas Finschild" <amgturk@yahoo.com> wrote in message <gj5lbt$sip$1@fred.mathworks.com>...
> Hi,
> I have two matrices like a=[1,2,3,4,5] and b=[3,1,5].I want to find the indices of elements of b in a. I mean what is the indice of 3,1 and 5 in matrix a.I tried to use "find" but can not succeed.I dont want to use loops,is it possible in efficient way?
> Thanks,

The 'loc' in

[tf, loc] = ismember(b, a);

should do the trick for you. It gives the highest index in a if there are more than one. It gives a zero if there are none.

Roger Stafford

Re: Finding matrix elements in another

Roger Stafford — Sat, 27 Dec 2008 17:57:01 +0000

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gj5oqh$o33$1@fred.mathworks.com>...
> The 'loc' in
>
> [tf, loc] = ismember(b, a);
>
> should do the trick for you. It gives the highest index in a if there are more than one. It gives a zero if there are none.
>
> Roger Stafford

Additional note. Using a 'find' in a for-loop can be a highly inefficient way of solving your problem for large vectors. The problem is not the for-loop overhead. It is the repeated scans over the same territory for the 'find' operation. For na and nb elements, that makes it an order na*nb algorithm. The 'ismember' function uses a more efficient preliminary sort operation which probably yields something like an order (na+nb)*log(na+nb) algorithm, much smaller for large na and nb.

Roger Stafford

Re: Finding matrix elements in another

dellyseas Finschild — Sat, 27 Dec 2008 19:21:01 +0000

Thanks, Roger for your help.

Re: Finding matrix elements in another

Nasser Abbasi — Sat, 27 Dec 2008 21:10:02 +0000

"dellyseas Finschild" <amgturk@yahoo.com> wrote in message
news:gj5lbt$sip$1@fred.mathworks.com...
> Hi,
> I have two matrices like a=[1,2,3,4,5] and b=[3,1,5].I want to find the
> indices of elements of b in a. I mean what is the indice of 3,1 and 5 in
> matrix a.I tried to use "find" but can not succeed.I dont want to use
> loops,is it possible in efficient way?
> Thanks,
>

use arrayfun:

a=[4,3,2,1] ;
b=[1,4];

arrayfun(@(x) find(a==x),b)

ans =
     4 1

Note that if an entry is repeated more than once in 'a', then you might want
to use 'UniformOutput',false in the above call to allow for more than one
index to be found:

a=[4,3,2,1,1] ;
b=[1,4];
arrayfun(@(x) find(a==x),b,'UniformOutput',false)

ans =
    [1x2 double] [1]

EDU>> ans{1}

ans =
     4 5

--Nasser

Re: Finding matrix elements in another

Roger Stafford — Sat, 27 Dec 2008 21:44:01 +0000

"Nasser Abbasi" <nma@12000.org> wrote in message <pMw5l.9865$D32.3056@flpi146.ffdc.sbc.com>...
> use arrayfun:
> .......

Nasser, the "'UniformOutput',false" option on 'arrayfun' notwithstanding, there is something inherently inefficient in an algorithm that repeatedly does finds over the same large array. Whatever algorithm is used, it would be better to first sort all the elements of both arrays together so that afterwards a single scan through the whole thing can elicit all the required equalities (or inequalities or whatever) without having to be repeated. Whether these results are then fed into a single vector or a cell array depends on the needs of the problem. But in my opinion that initial sort is vital for preserving efficiency for large arrays. Roughly speaking, it's the difference between an order n*m algorithm versus an order (n+m)*log(n+m) algorithm.

Roger Stafford

Re: Finding matrix elements in another

Nasser Abbasi — Sat, 27 Dec 2008 23:50:40 +0000

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message news:gj67j1$orl$1@fred.mathworks.com...
> "Nasser Abbasi" <nma@12000.org> wrote in message
> <pMw5l.9865$D32.3056@flpi146.ffdc.sbc.com>...
>> use arrayfun:
>> .......
>
> Nasser, the "'UniformOutput',false" option on 'arrayfun' notwithstanding,
> there is something inherently inefficient in an algorithm that repeatedly
> does finds over the same large array. Whatever algorithm is used, it
> would be better to first sort all the elements of both arrays together so
> that afterwards a single scan through the whole thing can elicit all the
> required equalities (or inequalities or whatever) without having to be
> repeated. Whether these results are then fed into a single vector or a
> cell array depends on the needs of the problem. But in my opinion that
> initial sort is vital for preserving efficiency for large arrays. Roughly
> speaking, it's the difference between an order n*m algorithm versus an
> order (n+m)*log(n+m) algorithm.
>
> Roger Stafford
>

Roger;

You are quite correct ofcourse that arrayfun is not efficient in this case
(O(N^2)), but the OP wanted to find all locations in 'a' without using a
loop. There was no requirements it be efficient as well :)

ismember is MUCH faster, but it only finds, as you said, one location, and
if there repeated entries, it will not show them. btw, here is a small test
on timing, showing ismember much faster:

clear all
a=rand([10^6,1]);
b=rand([10^4,1]);
tic;
arrayfun(@(x) find(a==x),b,'UniformOutput',false);
toc
%Elapsed time is 29.701860 seconds. <============

clear all
a=rand([10^6,1]);
b=rand([10^4,1]);
tic;
[tf, loc] = ismember(b, a);
toc
%Elapsed time is 0.243247 seconds. <==============

May be Matlab should have an option to ismember, or a new function, which
returns all entries found, but can be done in a more optimized way?

btw, all of this on XP on Intel 2 core E6850 3 GHz)

--Nasser