python - 优化两个列表之间的比较，给出不同的索引

Question

我有三个列表:旧的、新的和忽略的。 old 和 new 是字符串列表。 ignore 是一个索引列表，如果它们不匹配则应该忽略这些索引。目标是创建一个不同且未被忽略的索引列表。

旧的和新的可能包含不同数量的元素。如果新旧之间的尺寸存在差异，则应将差异标记为不匹配(除非被忽略)。

我目前的功能如下:

def CompareFields( old, new, ignore ):
  if ( old == None ):
    if ( new == None ):
      return [];
    else:
      return xrange( len(new) )
  elif ( new == None ):
    return xrange( len(old) )

  oldPadded = itertools.chain( old, itertools.repeat(None) )
  newPadded = itertools.chain( new, itertools.repeat(None) )
  comparisonIterator = itertools.izip( xrange( max( len(old ) , len( new ) ) ), oldPadded, newPadded )
  changedItems = [ i for i,lhs,rhs in comparisonIterator if lhs != rhs and i not in ignore ]
  return changedItems

我尝试过的各种选项的时间给出了以下 100,000 次运行的时间:

[4, 9]
CompareFields: 6.083546
set([9, 4])
Set based: 12.594869
[4, 9]
Function using yield: 13.063725
[4, 9]
Use a (precomputed) ignore bitmap: 7.009405
[4, 9]
Use a precomputed ignore bitmap and give a limit to itertools.repeat(): 8.297951
[4, 9]
Use precomputed ignore bitmap, limit padding and itertools.starmap()/operator.ne(): 11.868687
[4, 9]
Naive implementation: 7.438201

我拥有的最新版本的 python 是 2.6(它是 RHEL5.5)。我目前正在编译 Pypy 来尝试一下。

那么有没有人知道如何让这个函数运行得更快？是否值得使用 Cython？

如果我不能让它运行得更快，我会考虑用 C++ 或 Java 重写整个工具。

编辑:

好的，我为各种答案计时:

[4, 9]
CompareFields: 5.808944
[4, 9]
agf's itertools answer: 4.550836
set([9, 4])
agf's set based answer, but replaced list expression with a set to avoid duplicates: 9.149389
agf's set based answer, as described in answer: about 8 seconds
lucho's set based answer: 10.682579

因此 itertools 似乎是目前的最佳选择。令人惊讶的是，基于集合的解决方案表现如此糟糕。尽管我对使用 lambda 速度较慢并不感到惊讶。

编辑:Java 基准测试 简单的实现，有太多的 if 语句:128 毫秒

Answer 1

对于这两种解决方案，您应该:

ignore = set(ignore)

这会给你恒定的(平均)时间 in 测试。

我认为这是您正在寻找的基于 itertools/zip 的方法:

[i for i, (o, n) in enumerate(izip_longest(old, new)) 
                          if o != n and i not in ignore]

不需要 chain/repeat 来填充——这就是 izip_longest 的用途。 enumerate 也比 xrange 更合适。

还有 Lucho 的回答中 filter/set difference 方法的更 Pythonic(可能更快)版本:

[i for i, v in set(enumerate(new)).symmetric_difference(enumerate(old)) 
                                                     if i not in ignore]

在 lambda 上，列表理解优于 filter 或 map，并且不需要将两个列表都转换为 set 如果您使用 symmetric_difference 方法而不是 ^/xor 运算符。