how to efficiently find the indices?

Hi,

I have a matrix of N-by-M with integers. I need to efficiently find the indices for all of the unique elements in the matrix. The solution I have is via a "for" loop:

uM = unique (M(:));

for i = 1 : length(uM)
    I(i) = find(M == uM(i)); 
end

This works fine, but with a large matrix, this is slow. I wonder if there are better solutions. thanks very much!

[Geoff]

One way to make this code faster without changing anything fundamental would be to preallocate the cell array before your loop:

I = cell(length(uM),1);

Answer 1

[Richard Brown]

sort is your friend:

First we sort the entries of A so that like entries are adjacent

[S, iSorted] = sort(A(:));

Then we find the markers - where the value changes, plus the endpoints

markers = [0; find(diff(S)); numel(A)];

All we need to do is find the entries of iSorted corresponding to each block.

for i = 1:numel(markers)-1
  uM(i) = S(markers(i)+1);
  I{i} = iSorted(markers(i)+1:markers(i+1));
end

[Pinpress]

Great! This turns out to be working fine for me. It's still a "for" loop, but the computational efficiency is OK.

[Richard Brown]

for loops get a bit of an unnecessarily bad rap sometimes

Answer 2

[Leah]

Matlab has a nice function built in for this

 [B,I,J] = UNIQUE(...) also returns index vectors I and J such
    that B = A(I) and A = B(J) (or B = A(I,:) and A = B(J,:)).

Answer 3

[Andrei Bobrov]

[uM,n,n] = unique (M(:));
I = accumarray(n,1:numel(n),[],@(x){sort(x)});

[Richard Brown]

I think even @(x) {x} would meet the brief for your function

[Andrei Bobrov]

Hi Richard! I agree with you.

Answer 4

[Richard Brown]

Depending on whether you want the first or the last occurence

[uM, I] = unique(M, 'first')
[uM, I] = unique(M)

Answer 5

[Walter Roberson]

Your suggested code will not work if there are any duplicates, as the find() would return multiple values in that case and multiple values cannot be stored into a single numeric array element.

Have you considered using the second or third return value from unique() ?

Answer 6

[Pinpress]

Thanks guys -- forgot to mention that I need to find the indices for all of the elements if there are multiple occurrences. So simply using "unique" doesn't seem to work.

And yes, the original code I had will not work when more than one indices returns (which was precisely the reason I did not use [A, I, J] = unique (B);].

Any other thoughts?

[Oleg Komarov]

A and J will give you what you want.

[Richard Brown]

Not really - J is just A(:), but with the unique elements replaced with 1:nUnique. So it's no better

Answer 7

[Geoff]

This comes straight out of some of my own code... I guess it's the reverse of what you want though.

uM = unique(M);
I = arrayfun(@(x) find(uM==x,1), M);

For every element in M, it gives an index into uM. I use this to reduce columns of data in a matrix that are common to multiple targets.

So you seem to want: for every element in uM an array of indices into M. The result of course would be a cell array.

This would be:

I = arrayfun(@(x) find(M==x), uM, 'UniformOutput', false);

[Richard Brown]

I think that's what he was trying before, but found the repeated calls to find to be too slow

[Pinpress]

Calling "find" thousands of times will be slow.