Zużycie pamięci Pythona: dict Lista krotek VS

Question

Istnieje wiele pytań i dyskusji na temat zużycia pamięci różnych typów danych Pythona. Jednak niewielu z nich (jeśli takie istnieją) doszło do bardzo konkretnego scenariusza. Jeśli chcesz przechowywać WIELKIE dane klucz-wartość w pamięci, która struktura danych jest bardziej wydajna pod względem pamięci, dykta lub lista krotek?

Na początku myślałem, że dict jest silniejszy niż lista krotek i ta moc musi pochodzić z pewną ceną, a właściwie pusty dykta zajmuje więcej pamięci niż pusta lista lub krotka (patrz In-memory size of a Python structure), więc pomyślałem, że przy użyciu [(key1, value1), (key2, value2), ...] byłaby bardziej wydajna pod względem pamięci niż {key1: value1, key2: value2, ...}.

Wygląda na to, że się myliłem. Po prostu uruchom poniższy fragment kodu i zobacz zużycie pamięci zgłoszone przez Twój system operacyjny. Używam systemu Windows XP, więc menedżer zadań mówi mi, że duży dyktuje "tylko" 40MB pamięci RAM i 40MB VIRTURAL RAM, ale lista krotek pożera 60MB RAM i 60MB Virtual RAM.

Jak to możliwe?

from sys import getsizeof as g 
raw_input('ready, press ENTER') 
i = 1000000 
#p = [(x, x) for x in xrange(i)] # Will print 4,348,736 40,348,736 
p = dict((x, x) for x in xrange(i)) # Will print 25,165,964 37,165,964 
print g(p), g(p) + sum(g(x) for x in p) 
raw_input("Check your process's memory consumption now, press ENTER to exit") 

Aktualizacja:

Dzięki dla niektórych komentarzach poniżej. Chcę wyjaśnić: mówię o wydajności pamięci. I nie, w tym przypadku nie trzeba się martwić o skuteczność wyszukiwania wartości klucz-wartość, załóżmy, że mój algorytm pochłonie je jeden po drugim za pomocą iteratora.

Answer 1

Twoja list z tuple s dodaje dodatkową warstwę. Trzeba warstw przedmiotów:

• Zewnętrzna listę długości 1 mln, więc 1 milion wskazówek
  • 1 milion 2-slot krotki, SO2 mln pointers
    • 2 mln odniesienia do 1 milion wartości całkowite

natomiast swoją dict posiada tylko:

• dict (w tym 1 mln buforowanych mieszań) z 2 milionów wskaźników + dodatkowa przestrzeń rośnie stołowi
  • 2000000 odniesień do 1 mln całkowitej wartości

To 1 milion krotek plus lista zawierająca odniesienia do nich, które zajmują więcej pamięci niż 1 milion buforowanych skrótów. Istnieje tutaj około 50% więcej wskaźników, co łatwo oznacza 50% więcej pamięci, jaką widzisz.

Jest kolejna wada do twojej listy krotek: czas wyszukiwania. Aby znaleźć pasujący klucz w dykcie, istnieje koszt złożoności O (1). Aby zrobić to samo na liście krotek, musisz potencjalnie zeskanować całą listę, aby uzyskać koszt O (n). Nie używaj listy krotek, jeśli chcesz odwzorowywać klucze na wartości.

Answer 2

W tym przypadku uzyskujesz niekompletny obraz użycia pamięci.Całkowita wielkość słownika ponad dwukrotnie wzrasta w nieregularnych odstępach czasu, a jeśli porównasz rozmiar tych dwóch struktur zaraz po zwiększeniu rozmiaru słownika, znowu jest większy. Prosty skrypt z funkcją wielkości rekurencyjnego (patrz kod poniżej) pokazuje bardzo wyraźny wzór:

i: 2 list size: 296 dict size: 328 difference: -32 
i: 3 list size: 392 dict size: 352 difference: 40 
i: 4 list size: 488 dict size: 376 difference: 112 
i: 5 list size: 616 dict size: 400 difference: 216 
i: 7 list size: 808 dict size: 1216 difference: -408 
i: 10 list size: 1160 dict size: 1288 difference: -128 
i: 13 list size: 1448 dict size: 1360 difference: 88 
i: 17 list size: 1904 dict size: 1456 difference: 448 
i: 23 list size: 2480 dict size: 3904 difference: -1424 
i: 31 list size: 3328 dict size: 4096 difference: -768 
i: 42 list size: 4472 dict size: 4360 difference: 112 
i: 56 list size: 5912 dict size: 4696 difference: 1216 
i: 74 list size: 7880 dict size: 5128 difference: 2752 
i: 100 list size: 10520 dict size: 14968 difference: -4448 
i: 133 list size: 14024 dict size: 15760 difference: -1736 
i: 177 list size: 18672 dict size: 16816 difference: 1856 

Wzór ten trwa tak i rośnie. (Możesz przetestować to za pomocą swojej metody - spróbuj ustawić i w pobliżu 2636744.Rozmiar słownika jest większy w tym punkcie, przynajmniej dla mnie.) Martijn ma rację, że krotki z listy krotek dodają do pamięci narzut, anulowanie przewagi pamięci list przez słowniki. Jednak średni wynik nie polega na tym, że słownik jest lepszy; to, że słownik jest mniej więcej taki sam. Więc w odpowiedzi na twoje pierwotne pytanie:

Kiedy chcesz przechowywać WIELE cennych danych klucz-wartość w pamięci, która struktura danych jest bardziej wydajna pod względem pamięci, dykta lub lista krotek?

Nie ma znaczenia, czy wszystko, co cię niepokoi, to pamięć.

Jednak, należy zauważyć, że powtarzanie w słowniku jest często nieco wolniejsze od iterowania na liście, ponieważ nie ma dobrego sposobu na uniknięcie iteracji wszystkich pustych binów w słowniku. Istnieje więc pewna kompromitacja - słowniki są (znacznie) szybsze w wyszukiwaniu losowych kluczy, ale listy są (nieco) szybsze w iteracji. Słownik prawdopodobnie będzie lepszy w większości przypadków, ale w niektórych rzadkich przypadkach lista może zawierać mikrooptymalizację.

---

Oto kod testujący rozmiar. Prawdopodobnie nie wygeneruje poprawnych wyników dla wszystkich przypadków narożnych, ale powinien poradzić sobie z prostymi strukturami takimi jak ta bez żadnych problemów. (Ale daj mi znać, jeśli zauważysz jakieś problemy.)

import sys, collections, itertools, math 

def totalsize(x): 
    seen = set() 
    return ts_rec(x, seen) 

def ts_rec(x, seen): 
    if id(x) in seen: 
     return 0 
    else: 
     seen.add(id(x)) 

    x_size = sys.getsizeof(x) 
    if isinstance(x, collections.Mapping): 
     kv_chain = itertools.chain.from_iterable(x.iteritems()) 
     return x_size + sum(ts_rec(i, seen) for i in kv_chain) 
    elif isinstance(x, collections.Sequence): 
     return x_size + sum(ts_rec(i, seen) for i in x) 
    else: 
     return x_size 

for i in (10 ** (e/8.0) for e in range(3, 19)): 
    i = int(i) 
    lsize = totalsize([(x, x) for x in xrange(i)]) 
    dsize = totalsize(dict((x, x) for x in xrange(i))) 

    print "i: ", i, 
    print " list size: ", lsize, " dict size: ", dsize, 
    print " difference: ", lsize - dsize