在 Python 中高效比较两个集合

Question

我有两个大整数集，

set1

和

set2

。以下哪一项效率更高？

示例：

if(set1 == set2)

或

if(len(set1)==len(set2))

Answer 1

两种说法完全不同。

if(set1==set2)

比较两个集合中每个元素的相等性，当且仅当两个集合完全相同时评估结果为 true。

而

if(len(set1)==len(set2))

仅比较两个集合的长度。 即使您有两套长度相同的产品，也可能会出现不同的情况。例如考虑这个：

集合1：[1,3,6,29,31]

集合2：[1,3,7,10,15]

虽然这些集合的长度相同，但它们并不相同。

您可以这样做以节省时间。

if len(set1) == len(set2):
    if set1 == set2:
        //TODO when sets are equal
    else
        //TODO when sets are not equal.
else
    //TODO when sets are not equal

Answer 2

正如 Nikhil Wagh 已经解释的那样，在最初的问题中，比较集合的长度和检查两个集合的相等性之间存在混淆。我只想补充一点，简单的

s1 == s2

就足够了并且高效，因为 __eq__() （及其相反的 __ne__()）方法已经执行了此优化。它首先检查集合是否具有相同的长度，然后检查集合是否具有相同的哈希值，然后才执行

set_issubset

检查。

您可以在文件

set_richcompare()

中找到函数

setobject.c

中集合相等性检查的实现。您不需要成为 C 语言的期望者才能理解该算法 - https://github.com/python/cpython/blob/master/Objects/setobject.c