Dlaczego związek zużywa więcej pamięci, jeśli argument jest zbiorem?

Question

Jestem zdziwiony tym zachowaniem alokacji pamięci set S:

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

Dlaczego przy użyciu set jako argument podwaja ilość pamięci używanej przez powstałą set? Wynik w obu przypadkach jest identyczny z oryginalnym set:

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

Należy zauważyć, że to samo dzieje się przy użyciu normalnego iterator:

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

iz metody update:

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

Początkowo myślałem, że to dlatego, że kiedy jest wywoływana union, widzi, że rozmiar innego set to 1000 iw ten sposób decyduje się na przydzielenie wystarczającej ilości pamięci, aby zmieścić wszystkie elementy obu set s, ale potem wykorzystuje tylko część tej pamięci, podczas gdy w przypadku iteratora po prostu iteruje nad nią i dodaje elementy jeden po drugim (co robi Zużywa więcej pamięci, ponieważ wszystkie elementy są już w wersji set).

Ale range jest również sekwencją, podobnie jak list w pierwszym przykładzie.

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

Więc dlaczego tak się nie dzieje z range i list ale tylko z set? Czy istnieje jakaś decyzja dotycząca projektu lub czy jest to błąd?

---

Testowany na pythonie 2.7.3 i pythonie 3.2.3 na linuksie 64-bitowym.

Answer 1

W języku Python 2.7.3, set.union() deleguje do funkcji C o nazwie set_update_internal(). Ten ostatni używa kilku różnych implementacji w zależności od typu argumentu Pythona. Ta mnogość implementacji tłumaczy różnicę w zachowaniu między testami, które przeprowadziłeś.

Realizacja który jest używany, gdy argument jest set sprawia następujące założenie udokumentowane w kodzie:

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

Oczywiście, założenie nie (lub kilku) nakładających kluczy jest nieprawidłowy w danym przypadku. Jest to wynik końcowej pamięci przeważającej.

Nie jestem pewien, czy nazwałbym to błędem. Wykonawca z set wybrał to, co dla mnie wygląda na rozsądny kompromis i po prostu znalazłeś się po złej stronie tego kompromisu.

Upside kompromis jest, że w wielu przypadkach wyniki wstępnego przydziału w lepszej wydajności:

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 

Tutaj wersja set jest dwukrotnie szybszy, przypuszczalnie dlatego, że nie wielokrotnie realokacji pamięci jako dodaje elementy od rhs.

Jeśli alokacja jest rozdawaniem przerwań, istnieje kilka sposobów obejścia tego problemu, niektóre z nich już odkryłeś.