Optimising list comparison

[Tim Peters]

[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

I assume

     -1 == -1

too.

> 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

This will run *significantly* faster if you pass list1 and list2 to
compare() as arguments (access to function locals is much quicker than
access to globals).  You could also exploit Python's chained comparisons:

    if -1 != a != b != -1:
        return 0

However, the order in which you wrote your compares strongly favors your
specific test input, and the chained comparison would be significantly
slower given your specific test input for that reason alone.  If real life
throws a "random" mix of -1, 0 and 1 at you, different ways of spelling the
compares would be more effective.

For example, your rules are such that "!=" is the correct result if and only
if the sum of two elements is 1 (think about it:  0+0=0, 1+1=2, -1+i <= 0
for every i in {-1, 0, 1}, and 1+0=0+1=1; the last is the only case in which
the sum is 1).  So

    if list1[i] + list2[i] == 1:
        return 0

should work fine, and runs at the same speed regardless of relative
frequency of the various input-pair possibilities.

Then it's actually quite difficult to explain why

import operator
def attempt5(list1, list2, sum=operator.__add__):
    return 1 not in map(sum, list1, list2)

isn't quicker than an explicit loop doing the same thing.

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

Keep trying <wink>.  Also give

    for a, b in zip(list1, list2):

a shot.  It may surprise you <wink>.

> 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.

You can't, short of raising an exception.  Whether you *want* to break out
early depends on the expected distribution of input pairs; e.g., if, like
the example you're timing, it's typical that the vectors start with a long
stretch of equal elements, breaking early would be much more useful if you
started comparing at the end.

> 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.

Well, your specific test case always raises an exception.  Exceptions are
cheaper if they're not raised.  In the intended application, what percentage
of the time do you expect inequality to occur?  An exception gets more
attractive the less often inequality obtains.

Note that having to use a lambda is also a drag on speed.  map() speed
tricks are much more effective if a builtin function can be mapped.  However
(and this is a clue to an earlier mystery), an infix "+" applied to integers
is much quicker than operator.__add__ applied to integers.

> Here's my complete script:
> ...

Thanks!  That's very helpful.