Optimising list comparison

[Graham Ashton]

A friend of mine is using Python in a research project where he needs to
compare each element of two vectors, such that comparing [a, b, c] and 
[d, e, f] would involve comparing a with d, b with e and c with f.

The only possible values in either list are 0, 1 and -1. When comparing
two values, if either value is set to -1 then both values are deemed to be
equal. So we've got:

    0 ==  0
    0 == -1
    1 ==  1
    1 == -1
    1 !=  0

What he wants to know is simply whether all the values in the two lists
are "equal", in which case the comparison returns 1, otherwise it returns
0.

Now, having read Skip M's python optimisation page I would have thought
that the following example could be beaten into the ground by an
alternative involving map(). Obviously, a C extension would win the grand
prize, but I'm interested in learning some map() tricks....

    list1 = [1] * 20
    list2 = [1] * 19 + [0]

    def compare():
        for i in range(len(list1)):
            a = list1[i]
            b = list2[i]
            if (a != b) and (a != -1) and (b != -1):
                return 0
        return 1

Neither of us have yet managed to come up with anything to beat it (we've
been timing the alternatives over 100000 itterations).

Any hints? What I can't work out how to do is how to break out of a call
to map() if two values don't match. The only thing I've come up with so 
far is this:

    func = lambda a, b: (a == b) or (a == -1) or (b == -1) or 1 / 0
    try:
        map(func, list1, list2)
    except ZeroDivisionError:
        pass

and though I felt quite smug when I'd thought of it, it's more than a bit
hacky. The raise and except also double the execution time on my machine.

Here's my complete script:

----cut----
#!/usr/bin/env python

import time

list1 = [1] * 20
## list1 = [1] * 9 + [0] + [1] * 10
list2 = [1] * 19 + [0]

def benchmark(func, iters=100000):
    start = time.time()
    for i in range(iters):
        r = func()
    end = time.time()
    print "%d iterations of %s took: %.3f secs" % (iters, func, end - start)

def attempt1():
    for i in range(len(list1)):
        if (list1[i] != list2[i]) and (list1[i] != -1) and (list2[i] != -1):
            return 0
    return 1

func = lambda a, b: (a == b) or (a == -1) or (b == -1) or 1 / 0

def attempt2():
    try:
        map(func, list1, list2)
    except ZeroDivisionError:
        pass

if __name__ == "__main__":
    benchmark(attempt1)
    benchmark(attempt2)
----cut----

Cheers,

Graham.