Is there such an idiom?

[Bruce Cropley]

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