4

我正在尝试在 Python 2.6 中比较两个大小相同的整数列表。我需要的比较是将列表 1 中的第一项与列表 2 中的第一项进行比较，将列表 1 中的第二项与列表 2 中的第二项进行比较，依此类推，如果所有列表项都遵循，则返回结果相同的比较标准。它的行为应该如下：

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.

我想我可以编写如下代码块，但我不知道它是否最有效。我的程序会经常调用这个方法，所以我想尽可能地简化它。

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)

它是否已经达到预期效果（n 的大 O），还是有更快的方法（或使用系统函数的方法）？

澄清：我希望返回“无”的情况最常发生，所以这很重要。

4

3 回答 3

5

你熟悉奇妙的zip功能吗？

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 接受两个列表（xs在ys这种情况下，可以随意调用它们）并为元组序列创建一个迭代器。

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

这样，您可以同时遍历两个列表并串联比较每个值。时间复杂度应该是 O(n)，其中 n 是列表的大小。

如果不满足 >= 或 <= 条件，它将提前返回。

更新

正如James Matta所指出的，itertools.izip它的性能优于zipPython 2 中的标准。这在 Python 3 中并非如此，标准在旧版本中的zip工作方式是一样的。izip

于 2013-10-09T21:24:05.550 回答
5

您可以考虑基于 numpy 的矢量化比较。

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

显然，你可以设计这个东西来得到你的答案。

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!"

可以进行每种类型的比较<, >, <=, >=,。

于 2013-10-09T21:41:19.293 回答
0

对于任何对这两种方法的性能感兴趣的人，我将迭代方法命名为“tortoise”，将 numpy 方法命名为“hare”，并使用下面的代码对其进行了测试。

起初，“乌龟”赢得了 [.009s [T] vs .033s [H]]，但我检查了它，发现 asarray() 被调用的频率超过了它需要的频率。通过该修复，“野兔”再次获胜，[.009s [T] vs .006s [H]]。

数据在这里：http
://tny.cz/64d6e5dc 它由 28 行组成，长度约为 950 个元素。其中四行共同 >= 所有其他行。

看看性能如何在更大的数据集上工作可能会很有趣。

import itertools, operator, math
import cProfile
import numpy as np

data = #SEE PASTEBIN

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

    for x, y in zip(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_greater and all_less:
        return 0
    if all_greater:
        return 1
    if all_less:
        return -1
    return None  # all_greater might be set False on final iteration


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

def find_uniques_tortoise():
    include_list = range(len(data))
    current_list_index = 0
    while current_list_index < len(data):
        if current_list_index not in include_list:
            current_list_index += 1
            continue
        for x in range(current_list_index+1,len(data)):
            if x not in include_list:
                continue
            result = tortoise(data[current_list_index], data[x])
            if result is None: #no comparison
                continue 
        elif result == 1 or result == 0: # this one beats the other one
            include_list.remove(x)
            continue
        elif result == -1: #the other one beats this one
            include_list.remove(current_list_index)
            break
    current_list_index +=1
return include_list

def find_uniques_hare():
    include_list = range(len(data))
    current_list_index = 0
    #do all asarray()s beforehand for max efficiency
    for x in range(len(data)): 
        data[x] = np.asarray(data[x])
    while current_list_index < len(data):
        if current_list_index not in include_list:
            current_list_index += 1
            continue
        for x in range(current_list_index+1,len(data)):
            if x not in include_list:
                continue
            if hare(data[current_list_index], data[x]): # this one beats the other one, or it's a tie
                include_list.remove(x)
            #   print x
                continue
            elif hare(data[x], data[current_list_index]): #the other one beats this one
                include_list.remove(current_list_index)
            #   print current_list_index
                break
            else: #no comparison
                continue
        current_list_index +=1
    return include_list             



cProfile.run('find_uniques_tortoise()')
cProfile.run('find_uniques_hare()')

print find_uniques_tortoise()
print   
print find_uniques_hare()
于 2013-10-10T02:05:47.860 回答