在 Y 而不是 Z 中为 x 编写 Pythonic 方法

Question

最近遇到一个看似简单的情况，就是找不到好的pythonic写法。我想问问他们的解决方案，哪个最快。

我有两个数组，比如 Arr1 = [-1, 0, 1, 2, 3] 和 Arr2 = [1, 2, 3]。我想获取 Arr1 中但不是 Arr2 中的元素数组。同样，超级简单的情况，但实施起来却很棘手。

我尝试了 [x in Arr1 and not Arr2] 的变体，但是因为 not 求值为布尔值，所以会引发错误。我觉得 python 对此有一个非常好的和干净的解决方案，但它正在逃避我的想法。

（我的解决方案是 filter(lambda x: x not in Arr2, Arr1)。它有效，但不是一个令人满意的解决方案。SO 有更 pythonic 的方法吗？）

Answer 1

Python list 不支持减法运算符，但 set 支持。所以，将 lists 转换为 sets，减去它们并将结果转换为列表。

Arr1 = [-1, 0, 1, 2, 3]
Arr2 = [1,2,3]
difference = list(set(Arr1) - set(Arr2))
print difference
>>[-1,0]

这种方法比使用压缩列表更快，因为您需要检查 Arr1 中的每个元素是否在 Arr2 中，N*M 也是如此。

Answer 2

列表理解看起来像这样

>>> [item for item in Arr1 if item not in Arr2]
[-1, 0]

但是，这是非常低效的，因为在最坏的情况下它必须进行 M * N 次迭代，因为 in 运算符将必须按顺序迭代 Arr2 的元素。所以，最好将 Arr2 转换为一个集合，然后以相同的方式进行

>>> set2 = set(Arr2)
>>> [item for item in Arr1 if item not in set2]
[-1, 0]

由于我们在这里使用一个集合，它使用散列来进行查找，因此它比线性列表搜索方法更快。

如果您可以自由地将两个列表转换为集合，并且结果中元素的顺序无关紧要，只需将两个列表转换为集合，然后求集差，像这样

>>> set1, set2 = set(Arr1), set(Arr2)
>>> set1 - set2
set([0, -1])

只是为了展示线性列表搜索在这个列表理解中的影响，只需检查这个时间比较。

>>> import random
>>> import timeit
>>> 
>>> def get_random_numbers(count=100):
>>>     return [random.randint(0, 10000) for _ in range(count)]
>>> 
>>> data1, data2 = get_random_numbers(10000), get_random_numbers(10000)
>>> set1, set2 = set(data1), set(data2)
>>> 
>>> timeit.timeit("[item for item in data1 if item not in data2]",
                    setup="from __main__ import data1, data2", number=100)
>>> 47.4242498875
>>> timeit.timeit("[item for item in data1 if item not in set2]",
                    setup="from __main__ import data1, set2", number=100)
>>> 0.0595960617065
>>> timeit.timeit("list(set1 - set2)",
                    setup="from __main__ import set1, set2", number=100)
>>> 0.033539056778

所有结果都以秒为单位。查看使用集合获得的性能提升幅度。

Answer 3

>>> S = set(Arr2)
>>> [x for x in Arr1 if x not in S]
[-1, 0]

如果 Arr2 的元素不可哈希，则直接使用它而不是从中生成一个集合。集合是首选，因为对集合的包含测试大约为 O(1)，而列表为 O(n)。

在 Y 而不是 Z 中为 x 编写 Pythonic 方法

Pythonic way to write for x in Y and not in Z

python

list-comprehension

list