Python: Most efficient way to compare two lists of integers

Question

I'm trying to compare two lists of integers, each the same size, in Python 2.6. The comparison I need is to compare the first item in List 1 with the first item in List 2, the second item in List 1 with the second item in List 2, and so on, and returns a result if ALL of the list items follow the same comparison criteria. It should behave as follows:

list1 = [1,1,1,1]
list2 = [2,1,2,3]
compare(list1,list2) 
# returns a "list 1 is <= list 2" response.

list1 = [4,1,4,3]
list2 = [2,1,2,3]
compare(list1,list2) 
# returns a "list 1 is >= list 2" response.

list1 = [3,2,3,2]
list2 = [1,4,1,4]
compare(list1,list2) 
# returns None— some items in list1 > list2, and some items in list2 > list1.

I figured I could write the code like the following block, but I don't know if it's the most efficient. My program is going to be calling this method a LOT so I want to streamline this as much as possible.

def compare(list1,list2):
    gt_found = 0
    lt_found = 0
    for x in range(len(list1)):
        if list1[x] > list2[x]:
            gt_found += 1
        elif list1[x] < list2[x]:        
            lt_found += 1
        if gt_found > 0 and lt_found > 0:
            return None   #(some items >, some items <)
    if gt_found > 0:
        return 1          #(list1 >= list2)
    if lt_found > 0:
        return -1         #(list1 <= list2)
    return 0              #(list1 == list2)

Is it already as good as it's going to get (big-O of n), or is there a faster way to go about it (or a way that uses system functions instead)?

CLARIFICATION: I expect the case that returns 'None' to happen the most often, so it is important.

Answer 1

You can consider a numpy-based vectorized comparison.

import numpy as np

a = [1,1,1,2]
b = [2,2,4,3]

all_larger = np.all(np.asarray(b) > np.asarray(a))  # true if b > a holds elementwise

print all_larger

        True

Clearly, you can engineer the thing to have your answer.

all_larger = lambda b,a : np.all(np.asarray(b) > np.asarray(a))

if all_larger(b,a):
       print "b > a"
elif all_larger(a,b):
       print "a > b"

else
       print "nothing!"

Every type of comparison such as <, >, <=, >=, can be done.

Answer 2

Are you familiar with the wonderful zip function?

import itertools

def compare(xs, ys):
  all_less = True
  all_greater = True

  for x, y in itertools.izip(xs, ys):
    if not all_less and not all_greater:
      return None
    if x > y:
      all_less = False
    elif x < y:
      all_greater = False

  if all_less:
    return "list 1 is <= list 2"
  elif all_greater:
    return "list 1 is >= list 2"
  return None  # all_greater might be set False on final iteration

Zip takes two lists (xs and ys in this case, but call them whatever you want) and creates an iterator for a sequence of tuples.

izip([1,2,3,4], [4,3,2,1]) == [(1,4), (2,3), (3,2), (4,1)]

This way you can iterate through both lists simultaneously and compare each value in tandem. The time complexity should be O(n), where n is the size of your lists.

It will return early in cases where neither the >= or <= condition are met.

Update

As James Matta points out, itertools.izip performs better than the standard zip in Python 2. This isn't true in Python 3, where the standard zip works the way izip does in older versions.