Per wrote:
> http://jaynes.colorado.edu/PythonIdioms.html
[snip]
> 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?
A common technique if both lists are sorted is to iterate through both
lists in parallel, advancing the smaller iterator each time. This is
the merge algorithm that is used by a merge sort, and it is O(s+t).
For two lists, the algorithm would go something like:
while not finished:
if s_iter_val < t_iter_val:
move s_iter on
elif s_iter_val > t_iter_val:
move t_iter on
else:
include / yield the value
move both iters on
For more on the standard merge algorithm, see:
http://en.wikipedia.org/wiki/Merge_algorithm
For an intersection merge, I hacked the recursive solution from
there...
def merge(a, b):
if len(a) == 0: return []
if len(b) == 0: return []
if a[0] < b[0]: return merge(a[1:], b)
elif a[0] > b[0]: return merge(a, b[1:])
else: return a[0:1] + merge(a[1:], b[1:])
#-------------------------8<-------------------------
import unittest
class TestMerge(unittest.TestCase):
def test_merge(self):
self.assertEquals(merge([1,2],[]), [])
self.assertEquals(merge([],[1,2]), [])
self.assertEquals(merge([1,3,5],[2,4,6]), [])
self.assertEquals(merge([1,2,3],[3,4,5]), [3])
self.assertEquals(merge([1,2,3,5,6,7],[3,4,5,7,8]), [3,5,7])
if __name__ == "__main__":
unittest.main()
HTH,
Bruce
--
http://mail.python.org/mailman/listinfo/python-list
