Question about vectorizing a search function

1 view (last 30 days)
Brian on 25 Jun 2013
I have a Nx2 matrix, and I want to check for the existence of elements in the second column in my first column.
What I have set up is a binary tree, with a Nx2 matrix of point indices indicating which point is connected to what. (i.e.[1 2] means point 1 is connected to point 2, etc). For my terminal end points, they never exist as beginning points, only end points, so with the way I have it set up, they will never be found in the first column.
What I want to use is the find function, which is fast. I have something working with the ismember function, but that can get to be very slow with larger trees. Some sample code I have is:
terminalIndices = ismember(connMx(:,2), connMx(:,1))
where connMx is my Nx2 matrix of point connection indices.
Other than that, what I would do (and saves some time with overlarge trees, but is too verbose) is looping from 1 to nPoints with the code:
counter = 1;
for i=1:nPoints
a = find(ccoFaceMx(:,1) == i)
if a ~= []
termIdxArray(counter) = a
counter = counter+1;
Again, for smaller trees this is fine, but I can at times have trees larger than 1000 elements, and this function begins to slow down considerably then.
Are there any alternatives to this? Thanks for your advice!

Answers (1)

Andrei Bobrov
Andrei Bobrov on 25 Jun 2013
[a,b] = ismember(ccoFaceMx(:,1),1:nPoints);
[a1,c,c] = unique(b(a));
d = (1:numel(a))';
out = [num2cell(a1), accumarray(c,d(a),[],@(x){x})];
  1 Comment
Brian on 25 Jun 2013
This worked pretty well, but it seemed to do the exact opposite of what I wanted: it gave me entries that existed in the first column, when I wanted those that did not.
Still, though, thanks, this seems to be an improvement over what I had before.

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by