Per wrote: > http://jaynes.colorado.edu/PythonIdioms.html > > """Use dictionaries for searching, not lists. To find items in common > between two lists, make the first into a dictionary and then look for > items in the second in it. Searching a list for an item is linear-time, > while searching a dict for an item is constant time. This can often let > you reduce search time from quadratic to linear.""" > > Is this correct? > s = [1,2,3,4,5...] > t = [4,5,6,,8,...] > how to find whether there is/are common item(s) between two list in > linear-time? > how to find the number of common items between two list in linear-time?
I'm not sure if it works in linear time, but if there are no duplicates in each list, sets would be the easiest way to do these with. >>> s = set([1,2,3,4,5,6]) >>> t = set([4,5,6,7,8,9]) >>> s.intersection(t) set([4, 5, 6]) >>> len(s.intersection(t)) 3 Cheers, Ron -- http://mail.python.org/mailman/listinfo/python-list