[Tutor] efficient method to search between two lists

[Kent Johnson]

Terry Carroll wrote:
> On Wed, 22 Mar 2006, Srinivas Iyyer wrote:
> 
> 
>>I cannot think of any other smart method since these
>>are the only two ways I know possible. 
>>
>>Would any one please help me suggesting a neat and
>>efficient way.  
> 
> 
> I'm thinking:
> 
> 1) use sets to get subsets of both lists down to only those elements that 
> will match at least one element in another list; 
> 
> 2) loop and compare, but only on those elements you know will match 
> somewhere (because of step #1)

This is more efficient than the original algorithm because it reduces 
the size of the loops to the number of matching elements rather than the 
whole number of elements. But if there are a large number of matches it 
will still be a lot of loops!

If the number of elements in a and b is na and nb and the number of 
matching elements is nmatch, then the original algorithm executes the 
inner loop na*nb times. Terry's algorithm reduces this to nmatch*nmatch 
which still grows quickly as nmatch gets bigger.

The virtue of Srinivas' second solution (using a helper dict) is that it 
has two loops that iterate na and nb times separately, so it eliminates 
the multiplicative time. This is a huge win when na, nb and nmatch are 
large.

Kent