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

Question

为什么问这个问题？

我试图回答这个问题:Check if All Values Exist as Keys in Dictionary用比生成器理解更好的东西提供给 all (与某些函数执行的隐式循环相比，python 循环即使在理解中也会减慢执行速度):

all(i in bar for i in foo)

哪里bar是一本字典并且foo是使用 set.issubset 的列表(转换为 set 的 foo 才能使用 foo.issubset(bar) )，并没有成功击败 all 的时代解决方案(除非两个容器都转换为 set s)。

我的问题:

来自 set 的文档:

Note, the non-operator versions of union(), intersection(), difference(), and symmetric_difference(), issubset(), and issuperset() methods will accept any iterable as an argument. In contrast, their operator based counterparts require their arguments to be sets. This precludes error-prone constructions like set('abc') & 'cbs' in favor of the more readable set('abc').intersection('cbs').

好吧，但性能确实取决于参数的类型，即使复杂度不高(The complextiy of 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

所以如果 set作为参数传递，结果非常快。

使用 list慢得多。我发现这是因为必须对字符串进行哈希运算的代价很高。所以我用这样的整数更改了我的测试输入:

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通过 dict.keys()与在 python 3 中一样，键被称为 ( https://www.python.org/dev/peps/pep-3106/ )“类似集合或无序的容器对象”。

但在那种情况下，结果比 dict 更糟糕或 list .

那么为什么传递 set击败通过 list或 dict或 dict_keys对象？我在文档中没有看到任何关于此的内容。

Answer 1

set.issubset algorithm需要一组才能使用(卡住集和子类计数)；如果你传递其他东西，它会成为一个集合。它基本上是 all(elem in other for elem in self)，并且它需要知道 elem in other 是高效的并且意味着它对集合的意义。它知道如何保证的唯一方法是确保 other 是一个集合。制作一套很昂贵。

(我忽略了一些细节。如果您想确切地知道发生了什么，特别是如果您有一个奇怪的 set 子类，请阅读链接中的源代码。)