为什么Python的集合差异方法在空集合时需要时间？

Question

这就是我的意思：

> python -m timeit "set().difference(xrange(0,10))"   
1000000 loops, best of 3: 0.624 usec per loop

> python -m timeit "set().difference(xrange(0,10**4))"
10000 loops, best of 3: 170 usec per loop

显然，Python会遍历整个参数，即使在事先已知结果为空集的情况下。这样做有什么好处吗？此代码在Python 2.7.6中运行。

即使对于非空集合，如果您发现在迭代过程中已经删除了第一个集合的所有元素，立即停止迭代也是有意义的。

- dafinguzman

---

Python 3 中速度更慢 :) - Jean-François Fabre

顺便说一下，最近的PyPy也是如此。 - alecxe

即使对于非空集合，如果您发现在迭代过程中已经删除了第一个集合的所有元素，那么立即停止是有意义的。@Jean-FrançoisFabre - dafinguzman

我不确定这是否是一个“好”的理由，但set.difference函数的参数可以是任意可迭代对象，而不仅仅是集合。在迭代某些对象时可能会产生副作用，保证对于所有情况下函数具有相同的行为，而不是只有一种情况下参数被“未使用”，可能更重要。 - chepner

@user2357112：这不仅适用于这种特殊情况。例如，{1,2,3}.difference(range(0,10**4)) 可以在范围的第四个元素后停止并返回空集。 - dafinguzman

Answer 1

这样做有什么好处吗？

在迭代空集方面，以前没有出现过特殊路径。

即使对于非空集合，如果您发现在迭代过程中已经删除了第一个集合的所有元素，立即停止也是有意义的。

这是一个合理的优化请求。我已经制作了补丁，很快将应用它。以下是应用补丁后的新时间：

 $ py -m timeit -s "r = range(10 ** 4); s = set()" "s.difference(r)"
10000000 loops, best of 3: 0.104 usec per loop
 $ py -m timeit -s "r = set(range(10 ** 4)); s = set()" "s.difference(r)"
10000000 loops, best of 3: 0.105 usec per loop
 $ py -m timeit -s "r = range(10 ** 4); s = set()" "s.difference_update(r)"
10000000 loops, best of 3: 0.0659 usec per loop
 $ py -m timeit -s "r = set(range(10 ** 4)); s = set()" "s.difference_update(r)"
10000000 loops, best of 3: 0.0684 usec per loop

- Raymond Hettinger

---

不错！空集情况已经通过补丁进行了处理。那么其他情况呢？例如，s = set([1])，r = set(range(10**4))。 - dafinguzman

我在上一条评论中使用 r 和 s 进行了简单的测试，显然当两者都是集合时，即使第一个集合不为空，它也可以非常快速地工作。 - dafinguzman

@RaymondHettinger，新的实现是否保证迭代器总是被完全消耗，还是将其留作未定义？ - Tony Suffolk 66

Answer 2

我认为这是一个专业化的问题，考虑以下因素:

In [18]: r = range(10 ** 4)

In [19]: s = set(range(10 ** 4))

In [20]: %time set().difference(r)
CPU times: user 387 µs, sys: 0 ns, total: 387 µs
Wall time: 394 µs
Out[20]: set()

In [21]: %time set().difference(s)
CPU times: user 10 µs, sys: 8 µs, total: 18 µs
Wall time: 16.2 µs
Out[21]: set()

显然，差异操作 set - set 有一个特定的实现。

请注意，差异 运算符 要求右侧参数为一个集合，而差异允许使用任何可迭代对象。

根据@wim，实现在https://github.com/python/cpython/blob/master/Objects/setobject.c#L1553-L1555

- Dima Tisnek

---

特殊情况 在此处进行了处理。 - wim

Answer 3

当Python核心开发人员添加新功能时，首要考虑的是正确的代码和全面的测试覆盖率。这本身就很困难。加速通常在某人有想法和倾向后才会出现。我打开了一个跟踪问题28071，总结了这里讨论的提议和反对理由。我将在这里尝试总结它的处理情况。

更新：为3.6.0b1添加了一个早期退出空集的功能，大约在一天内到期。

- Terry Jan Reedy