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 _______________________________________________ Tutor maillist - [email protected] http://mail.python.org/mailman/listinfo/tutor
