python - 设置与 '&' 的交集如何在幕后工作？

Question

set_1 = {1, 2, 3, 4, 5, 6, 7}
set_2 = {2, 4, 6, 8, 10, 12}

intersec = set_1 & set_2

当 & 在两组之间使用时会发生什么？它的时间复杂度是多少？

Answer 1

set 数据结构及其操作是用 C 语言实现的。源代码可以在 GitHub 上的文件 Objects/setobject.c 中找到.为了方便那些不写 C 的人，这里是它在 Python 中如何工作的粗略翻译:

# helper function; only self needs to be a set
def set_intersection(self, other):
    if self is other:
        return self.copy()
    
    result = set()
    
    if isinstance(other, (set, frozenset)):
        if len(other) > len(self):
            self, other = other, self
    
    for item in other:
        if item in self:
            result.add(item)
    return result

# when using the & operator; self and other both must be sets
def set_and(self, other):
    if not isinstance(self, (set, frozenset)) or not isinstance(other, (set, frozenset)):
        return NotImplemented
    return set_intersection(self, other)

# when using the .intersection method, which accepts multiple "other" arguments
def set_intersection_multi(self, *others):
     if not others:
         return self.copy()
     
     result = self
     for other in others:
         result = set_intersection(result, other)
     return result

这不是直译； C 代码在 other 是一个集合的情况下有一个循环，如果不是，则有另一个循环，因为在前一种情况下，项目哈希是已知的，不需要重新计算.没有办法翻译那个细节，所以 C 中的两个循环都可以翻译成 Python 中的同一个循环，我对其进行了简化。另一个无法翻译的区别是，在 C 中，如果 self 是 frozenset 那么结果也是；但在这种情况下，Python 代码不能使用 .add。

因为测试集合的成员资格(in 运算符)需要 O(1) 预期时间，所以当两者都是集合时，交集的预期时间复杂度为 O(min(m, n)) , 其中 m 和 n 是 self 和 other 的长度。

当other不是集合时，交集的期望时间复杂度等于迭代other的时间复杂度加上计算哈希的时间复杂度other 中的所有项目。这通常是 O(n)，但理论上可能更高。