为什么 A.issuperset(B) 比 all(b in A for b in B) 慢得多？

Question

考虑测试集合 A 是否是可迭代对象 B 的超集，一次是使用集合的方法，一次是使用超集定义的我自己的表达式：

>>> A = set(range(1000))
>>> B = range(-1000, 0)
>>> A.issuperset(B)
False
>>> all(b in A for b in B)
False

现在让我们计时：

>>> from timeit import timeit
>>> timeit(lambda: A.issuperset(B))
52.666367300000005
>>> timeit(lambda: all(b in A for b in B))
0.9698789999999917

set自己的方法慢多了。为什么？据推测它 can/should 做同样的事情，但是以 C 速度，所以应该更快 .

我正在使用 CPython 3.8.1。

Answer 1

似乎差异来自于这样一个事实，即在您的测试中，您实际上并不是在两个集合之间运行 issuperset，而是在一个集合和一个范围之间。大部分时间花在将范围转换为集合。考虑以下时间安排：

A = set(range(1000))
B_set = set(range(-1000, 0))
B_range = range(-1000, 0)
B_list = list(range(-1000, 0))

%%timeit 
A.issuperset(B_set)
654 ns ± 6.09 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%%timeit 
A.issuperset(B_range)
29.9 µs ± 259 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%%timeit 
A.issuperset(B_list)
15.4 µs ± 233 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)


# Creating a set from a range. 
%%timeit
B_set = set(B_range)
29.2 µs ± 209 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%%timeit 
all(b in A for b in B_set)
816 ns ± 16.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%%timeit 
all(b in A for b in B_range)
474 ns ± 4.74 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Answer 2

set.issubset和set.issuperset的implementation坚持先从论证中建立一个集合：

static PyObject *
set_issubset(PySetObject *so, PyObject *other)
{
    setentry *entry;
    Py_ssize_t pos = 0;
    int rv;

    if (!PyAnySet_Check(other)) {
        PyObject *tmp, *result;
        tmp = make_new_set(&PySet_Type, other);
        if (tmp == NULL)
            return NULL;
        result = set_issubset(so, tmp);
        Py_DECREF(tmp);
        return result;
    }
    if (PySet_GET_SIZE(so) > PySet_GET_SIZE(other))
        Py_RETURN_FALSE;

    while (set_next(so, &pos, &entry)) {
        rv = set_contains_entry((PySetObject *)other, entry->key, entry->hash);
        if (rv < 0)
            return NULL;
        if (!rv)
            Py_RETURN_FALSE;
    }
    Py_RETURN_TRUE;
}

PyDoc_STRVAR(issubset_doc, "Report whether another set contains this set.");

static PyObject *
set_issuperset(PySetObject *so, PyObject *other)
{
    PyObject *tmp, *result;

    if (!PyAnySet_Check(other)) {
        tmp = make_new_set(&PySet_Type, other);
        if (tmp == NULL)
            return NULL;
        result = set_issuperset(so, tmp);
        Py_DECREF(tmp);
        return result;
    }
    return set_issubset((PySetObject *)other, (PyObject *)so);
}

PyDoc_STRVAR(issuperset_doc, "Report whether this set contains another set.");

issuperset 从参数中创建一个集合，然后调用 other.issubset(self)。（issubset 也坚持将一个集合作为它的参数，但它得到了一个，所以在这种情况下不需要转换。）他们本可以很容易地添加一个代码路径到 issuperset 到在没有设置转换的情况下处理非设置参数，但他们没有。

我怀疑这样做的原因可能是在像 {1}.issuperset([2, [3]]) 这样的调用中抛出错误，其中参数包含不可散列的元素。但是，也可能没有人费心去优化它。在 Python issue tracker for issuperset turns up 0 issues about optimizing issuperset, not even closed issues. There's a closed issue 中搜索关于 issubset 的更多困难的优化，令人惊讶的是，虽然它会导致类似的异常行为更改，但 none 的回复在这个问题上说了些什么。

为什么 A.issuperset(B) 比 all(b in A for b in B) 慢得多？

Why is A.issuperset(B) much slower than all(b in A for b in B)?

python

performance

set

python-internals