优化大型集合的交集

Question

前提很简单：我有两个整数a和b，我想找到一个i，使得a + i和b + i都在给定的列表中。该列表rs非常庞大（10亿项）。以下是我的代码：

def getlist(a,b):
    a1 = set([i - a for i in rs if i>a])
    b1 = set([i-b for i in rs if i>b]) 

    tomp = list(a1.intersection(b1))
    return tomp

问题在于a1和b1首先被预先计算，这会创建一个内存问题。我能否以某种方式优化我的代码？对该方法的一般评论也受欢迎。

示例输入：

rs = [4,9,16]
a = 3
b = 8

期望的输出结果：

getlist(3,8) = [1]

- S. L.

---

这会产生预期的输出吗？ - Dani Mesejo

是的，只要 len(rs) <=10e6。 - S. L.

我猜你不需要创建两个集合，你可以尝试：tomp = [i - b for i in rs if i - b in a1] - Dani Mesejo

如何看待 a1 = set([i - a for i in rs if i>a]) 和 b1 = set([i-b for i in a1 if i>b])？ - Ravi Teja

@Daniel，不完全是这样，总和不是一个确定的值，而可以是大数组中的一个。但就性能而言，我已经看到了优化代码片段的改进。 - S. L.

Answer 1

您可以通过跳过第二个集合（和中间列表）的创建来优化内存使用：

def getlist(a, b):
    a1 = {i - a for i in rs if i > a}
    return [i - b for i in rs if i > b and i - b in a1]

这个解决方案的时间和空间复杂度为O(n)。

- Eugene Yarmash

---

可以。你认为还有什么方法可以进一步降低复杂度吗？ - S. L.

我猜，只有在时间和空间之间做出权衡（反之亦然），才能实现。 - Eugene Yarmash

Answer 2

如果rs已经是一个set，那么这样做会更快：

Original Answer翻译成"最初的回答"

def getlist(a, b):
    return [i - a for i in rs if i > a and b + (i - a) in rs]

如果没有设置，那么您必须首先进行设置（否则上述算法将非常缓慢），性能本质上与之前相同： "最初的回答"

def getlist(a, b):
    rs_set = set(rs)
    return [i - a for i in rs_set if i > a and b + (i - a) in rs_set]

最初的回答：如果你要为不同的a和b值使用相同的函数，但是相同的rs值，你可以将rs转换为一个集合并在每次重用它。

- jdehesa

---

这实际上比任何其他答案快至少2.5倍，即使考虑到转换为set()的时间。 - S. L.