12

我对sets 的这种内存分配行为感到困惑：

>>> 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

为什么使用setas 参数会使结果使用的内存量加倍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，因此决定分配足够的内存来容纳两个sets 的所有元素，但后来它只使用了该内存的一部分，而在迭代器情况下，它只是对其进行迭代并逐个添加元素（这不会消耗更多内存，因为所有元素都已经在set.

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

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

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

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

4

1 回答 1

9

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

当参数是 a 时使用的实现set在代码中记录了以下假设：

/* 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.

如果过度分配是一个交易破坏者，有很多方法可以解决它，其中一些你已经发现了。

于 2013-03-04T09:24:28.090 回答