python - 如何快速从集合中排除点

Question

我有一个很大的整数对列表。例如

pairs = [((3, 5), (5, 5)), ((1, 1), (2, 5)), ((5, 1), (4, 3))]

我还有一大堆整数对。例如，

nums = [(2, 5), (4, 2), (5, 2)]

我想从 pairs 中删除任何在 nums 中有任何 pair 的 pair。例如，

nums = set(nums)
pairs = [((x1,y1),(x2,y2)) for ((x1,y1),(x2,y2)) in pairs if  not (set([(x1,y1),(x2,y2)]) & nums)]

这给出了

[((3, 5), (5, 5)), ((5, 1), (4, 3))]

问题是当 pairs 和 nums 很大时，这会很慢。如何加快速度？

示例慢速输入:

import random
nums = [(random.randint(1,50000),random.randint(1,50000)) for i in xrange(1000000)]
pairs = [((random.randint(1,50000),random.randint(1,50000)), (random.randint(1,50000),random.randint(1,50000))) for i in xrange(8000000)]

Answer 1

这将是最快的

nums=set(nums)
pairs= filter(nums.isdisjoint, pairs)

时间如下:

In [1]: import random

In [2]: pairs=[(random.randint(0,50),random.randint(0,50)) for i in range (1000)]

In [3]: nums=[random.randint(0,1000) for i in range(500)]

In [4]: numset=set(nums)

In [5]: %timeit [(x,y) for (x,y) in pairs if not (set([x,y]) & numset)]
1000 loops, best of 3: 746 us per loop

In [6]: %timeit [(x,y) for (x,y) in pairs if x not in numset and y not in numset]
10000 loops, best of 3: 145 us per loop    

In [7]: %timeit filter(numset.isdisjoint, pairs)
10000 loops, best of 3: 95.1 us per loop