[Tutor] efficient method to search between two lists

Kent Johnson kent37 at tds.net
Thu Mar 23 11:58:46 CET 2006

```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.
>>
>>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

```