python - 如果参数是一个集合，为什么 union 会消耗更多内存？

Question

我对 set 的内存分配行为感到困惑:

>>> set(range(1000)).__sizeof__()
32968
>>> set(range(1000)).union(range(1000)).__sizeof__()       # expected, set doesn't change
32968
>>> set(range(1000)).union(list(range(1000))).__sizeof__() #expected, set doesn't change
32968
>>> set(range(1000)).union(set(range(1000))).__sizeof__()  # not expected
65736

为什么使用set 作为参数加倍结果set 使用的内存量？ 两种情况下的结果都与原始 set 相同:

>>> set(range(1000)) == set(range(1000)).union(range(1000)) == set(range(1000)).union(set(range(1000)))
True

请注意，使用普通迭代器也会发生同样的情况:

>>> set(range(1000)).union(iter(list(range(1000)))).__sizeof__()
32968

并使用 update 方法:

>>> a.update(range(1000))
>>> a.__sizeof__()
32968
>>> a.update(set(range(1000)))
>>> a.__sizeof__()
65736

起初我以为是因为调用union时，它看到另一个set的大小是1000，因此决定分配足够的内存来容纳两个 set 的所有元素，但之后它只使用该内存的一部分，而在迭代器的情况下，它只是对其进行迭代并一个一个地添加元素(这不会消耗更多内存，因为所有元素都已在 set 中)。

但是 range 也是一个序列，第一个示例中的 list 也是一个序列。

>>> len(range(1000))
1000
>>> range(1000)[100]
100

那么，为什么这不会发生在 range 和 list 上，而只会发生在 set 上？ 这背后是否有任何设计决策或它是一个错误？

---

在 64 位 linux 上的 python 2.7.3 和 python 3.2.3 上测试。

Answer 1

在 Python 2.7.3 中，set.union()委托(delegate)给一个名为 set_update_internal() 的 C 函数.后者根据其参数的 Python 类型使用几种不同的实现。这种实现的多样性解释了您进行的测试之间的行为差​​异。

当参数是一个集合时使用的实现在代码中记录了以下假设:

/* Do one big resize at the start, rather than
 * incrementally resizing as we insert new keys.  Expect
 * that there will be no (or few) overlapping keys.
 */

显然，在您的特定情况下，没有(或很少)重叠键的假设是不正确的。这就是导致最终 set 过度分配内存的原因。

不过，我不确定我是否会将其称为错误。 set 的实现者选择了在我看来合理的权衡，而您只是发现自己站在了权衡的错误一边。

权衡的好处是，在许多情况下，预分配会带来更好的性能:

In [20]: rhs = list(range(1000))

In [21]: %timeit set().union(rhs)
10000 loops, best of 3: 30 us per loop

In [22]: rhs = set(range(1000))

In [23]: %timeit set().union(rhs)
100000 loops, best of 3: 14 us per loop

在这里，set 版本的速度是原来的两倍，大概是因为它在从 rhs 添加元素时不会重复重新分配内存。

如果过度分配会破坏交易，有多种方法可以解决它，其中一些您已经发现。