CODEWITHSUNDEEP
matlabsortingfind
Reza Sh
Reza Sh

Reputation: 77

Faster alternative for find and sort in MATLAB

I am working on community detection with a genetic algorithm. Communities are represented in locus-based representation, that each index(gene) and it's value are in same community.

For example in the figure below, if the chromosome is (b) the communities will be (d)

locus-based representation

So to extract communities from a chromosome, I need to iteratively find the indexes and values, to do this, I have written this code:

while (SumComms)~=nVar
    j=find(Sol>0,1,'first');%find the first node which has not placed in any community
    Com=[j,Sol(j)];%index of the node and it's value
    Comsize=0;
    while Comsize<numel(Com)
        Comsize=numel(Com);
        x=find(ismembc(Sol,sort([Com,Sol(Com)])));%Indexes which Com occure in Sol
        Com=unique([Com,x,Sol(x)]);
    end
    Sol(Com)=0;
    i=i+1;
    SumComms=SumComms+numel(Com);
    Communities{i}=Com;
end

But x=find(ismembc(Sol,sort([Com,Sol(Com)]))) is very time consuming in even mid-size networks. Do you know any faster way?

Upvotes: 0

Views: 332

Answers (1)

rahnema1
rahnema1

Reputation: 15837

Here is a solution using logical vector. Instead of operation on indices we can define Com as a logical vector so operations on indices such as ismember can be reduced to indexing operations:

i=0;
SumComms=0;
nVar = 9;
Sol = [3 0 3 1 5 6 4 7 7]+1;
while SumComms ~= nVar
    j=find(Sol>1,1,'first');
    Com = false(1,nVar);
    Com([j Sol(j)])=true;
    Comsize=0;
    sumcom = 2;
    while Comsize<sumcom
        Comsize=sum(Com);
        Com(Sol(Com))=true;
        Com = Com(Sol);
        Com(Sol(Com))=true;
        sumcom = sum(Com);
    end
    Sol(Com)=1;
    i = i + 1;
    SumComms=SumComms+sumcom;
    Communities{i}=find(Com);
end

Result of a test in Octave shows that the proposed method is at least 10x faster than the original method .

Upvotes: 1

Related Questions