set issubset 性能差异取决于参数类型

Question

为什么提出此问题呢 ？

我试图回答这个问题：检查所有值是否作为字典中的键存在，并提供比生成器理解更好的东西all（Python 循环，即使在理解中，与某些函数执行的隐式循环相比，也会减慢执行速度）：

all(i in bar for i in foo)

其中bar是一个字典，foo是一个列表，通过使用set.issubset（转换为setoffoo才能使用foo.issubset(bar)），并且没有成功击败解决all方案的时代（除非两个容器都转换为sets）。

我的问题：

来自以下文档set：

请注意，union()、intersection()、difference() 和 symmetry_difference()、issubset() 和 issuperset() 方法的非运算符版本将接受任何 iterable 作为参数。相反，基于运算符的对应部分需要设置其参数。这排除了像 set('abc') 和 'cbs' 这样容易出错的结构，有利于更具可读性的 set('abc').intersection('cbs')。

好的，但性能实际上取决于参数的类型，即使复杂性并不如此（Python 的复杂性 issubset()）：

import timeit
foo = {i for i in range(1, 10000, 2)}
bar = foo - {400}
n=10000
x = timeit.timeit(setup="foo = {str(i) for i in range(1, 10000, 2)};bar = foo - {'400'}",stmt="bar.issubset(foo)",number=n)
print("issubset(set)",x)
x = timeit.timeit(setup="foo = {str(i) for i in range(1, 10000, 2)};bar = foo - {'400'};foo=list(foo)",stmt="bar.issubset(foo)",number=n)
print("issubset(list)",x)
x = timeit.timeit(setup="foo = {str(i):i for i in range(1, 10000, 2)};bar = set(foo) - {'400'}",stmt="bar.issubset(foo)",number=n)
print("issubset(dict)",x)
x = timeit.timeit(setup="foo = {str(i):i for i in range(1, 10000, 2)}.keys();bar = set(foo) - {'400'}",stmt="bar.issubset(foo)",number=n)
print("issubset(dict_keys)",x)

我的结果（Python 3.4）：

issubset(set) 1.6141405847648826
issubset(list) 3.698748032058883
issubset(dict) 3.6300025109004244
issubset(dict_keys) 4.224299651223102

因此，如果将 aset作为参数传递，结果会非常快。

使用 alist速度要慢得多。我发现这是因为必须在字符串上完成的哈希成本很高。所以我用这样的整数更改了我的测试输入：

foo = {i for i in range(1, 10000, 2)}
bar = foo - {400}

结果在全球范围内更快，但仍然存在巨大的时差：

issubset(set) 0.5981848205989139
issubset(list) 1.7991591232742143
issubset(dict) 1.889119736960271
issubset(dict_keys) 2.2531574114632678

dict我还尝试通过Python 3中的键进行更改，dict.keys()据说键是（https://www.python.org/dev/peps/pep-3106/）“类似集合或无序的容器对象”。

但在这种情况下，结果甚至比使用dict或更糟糕list。

那么为什么传递 a 会set比传递 alist或 adict或 adict_keys对象要好呢？我没有在文档中看到任何关于此的内容。

Answer 1

该set.issubset算法需要一个集合来工作（冻结集和子类计数）；如果你传递其他东西，它就会组成一个集合。它基本上是all(elem in other for elem in self)，并且它需要知道它elem in other是有效的并且意味着它对于集合意味着什么。它知道如何保证这一点的唯一方法是确保other是一个集合。制作一套很贵。

（我已经掩盖了一些细节。如果您想确切地知道发生了什么，特别是如果您有一个奇怪的集合子类，请阅读链接中的源代码。）