python - 在 Python 中检查两个集合是否相等的时间复杂度

Question

阅读这个问题，我想知道 Python 需要多少时间（渐近地说）来评估表达式，例如

{1,2}=={2,1}

也就是说，检查集合类的两个实例是否相等。

Answer 1

集合之间的比较由第1848 行中的函数set_richcomparesetobject.c实现。你会看到相等的实现如下：

1. 如果集合的大小不同，则返回 false。

2. 如果两个集合都已被散列，并且散列不同，则返回 false。

3. 打电话set_issubset。

两组的子集测试如下所示：

while (set_next(so, &pos, &entry)) {
    int rv = set_contains_entry((PySetObject *)other, entry);
    if (rv == -1)
        return NULL;
    if (!rv)
        Py_RETURN_FALSE;
}
Py_RETURN_TRUE;

您会看到它是通过迭代第一组的所有元素然后在另一组中查找每个元素来工作的。所以（除非有很多哈希冲突）这在第一组的大小上是线性的。