12

sのメモリ割り当てのこの動作に困惑しています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引数としてa を使用すると、結果として使用されるメモリ量が2 倍になるのはなぜ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、もう一方のサイズがイテレータの場合は、単純にイテレータを実行し、要素を 1 つずつ追加します (すべての要素が既に にあるため、より多くのメモリを消費しません)。set1000setset

しかしrangeもシーケンスでありlist、最初の例の もそうです。

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

では、なぜこれは and では起こらずrange、 でlistのみ起こるのsetでしょうか? これの背後にある設計上の決定はありますか、それともバグですか?

Linux 64 ビットの python 2.7.3 および python 3.2.3 でテスト済み。

4

1 に答える 1

9

Python 2.7.3 では、set.union()と呼ばれる C 関数に委譲し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バージョンが 2 倍高速になっています。これは、 から要素を追加する際にメモリを繰り返し再割り当てしないためと考えられrhsます。

割り当て超過が契約の破綻の原因となっている場合は、それを回避する方法がいくつかありますが、そのうちのいくつかはすでに発見されています。

于 2013-03-04T09:24:28.090 に答える