Implementing an efficient Pair-Matching Algorithm

Question

Suppose that I have two lists of objects and I would like to match every object in list one with every object in list two.

This would probably be the algorithm that one would immediately come up with.

for( it_1=list_1.begin() ; it_1!=list_1.end() ; it_1++ )
  {
      for( it_2=list_2.begin() ; it_2!=list_2.end() ; it_2++ )
      {
          //now match 
           match(*it_1,*it_2);
      }

  }

I wonder if there is any better way of doing this. This requires O(n1*n2), where n1 and n2 are the length of list_1 and list_2, respectively.

The actual algorithm I am dealing with is not exactly the same as this one. So the body inside these nested for loops is a lot more complicated than this one. But the idea is the same, that is, matching every object in List1 with every in List 2. The match function could be just a simple addition or anything. Just ignore it. The focus should be on the loops and how to match. — cpp_noname
– cpp_noname, Commented Jul 10, 2012 at 13:19
If match can be anything, then this algorithm (ignoring the typos in the outer loop increment) is asymptotically optimal. To improve it, you need to have knowledge of what the code inside the loop is doing. — Fred Foo
– Fred Foo, Commented Jul 10, 2012 at 13:24
I see. The only way to improve this should be to parallelize the loops then. Thanks for your answer, larsmans. — cpp_noname
– cpp_noname, Commented Jul 10, 2012 at 13:26

javanx · Accepted Answer · 2012-07-10 19:08:23Z

1

You can make use of multi threading here by diving the list1 to 2 or 3 parts depending on the size and efficiency u r looking for , and run the match algorithm in each thread with list2 and collating the results back to the caller.

See if it helps..

answered Jul 10, 2012 at 19:08

javanx

6981 gold badge5 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Implementing an efficient Pair-Matching Algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related