Dlaczego krotki zajmują mniej miejsca w pamięci niż listy?


105

A tuplezajmuje mniej miejsca w pamięci w Pythonie:

>>> a = (1,2,3)
>>> a.__sizeof__()
48

podczas gdy lists zajmuje więcej miejsca w pamięci:

>>> b = [1,2,3]
>>> b.__sizeof__()
64

Co dzieje się wewnętrznie w zarządzaniu pamięcią w Pythonie?


1
Nie jestem pewien, jak to działa wewnętrznie, ale obiekt listy ma przynajmniej więcej funkcji, takich jak na przykład dołączanie, których nie ma krotka. Dlatego ma sens, aby krotka jako prostszy typ obiektu była mniejsza
Metareven

Myślę, że zależy to również od maszyny do maszyny .... dla mnie, gdy sprawdzę, a = (1,2,3) zajmuje 72, a b = [1,2,3] zajmuje 88.
Amrit

6
Krotki Pythona są niezmienne. Zmienne obiekty mają dodatkowe obciążenie związane ze zmianami w czasie wykonywania.
Lee Daniel Crocker

@Metareven liczba metod, które ma typ, nie wpływa na miejsce w pamięci zajmowane przez instancje. Lista metod i ich kod są obsługiwane przez prototyp obiektu, ale instancje przechowują tylko dane i zmienne wewnętrzne.
jjmontes

Odpowiedzi:


144

Zakładam, że używasz CPython i 64-bitowego (mam takie same wyniki na moim CPythonie 2.7 64-bitowym). Mogą występować różnice w innych implementacjach języka Python lub jeśli masz 32-bitowy język Python.

Niezależnie od implementacji, lists mają zmienną wielkość, a tuples mają stałą wielkość.

Więc tuples może przechowywać elementy bezpośrednio w strukturze, z drugiej strony listy wymagają warstwy pośredniej (przechowuje wskaźnik do elementów). Ta warstwa pośrednia jest wskaźnikiem, w systemach 64-bitowych jest 64-bitowa, a więc 8-bajtowa.

Ale jest jeszcze jedna rzecz, którą listrobią: nadmiernie przydzielają. W przeciwnym razie list.appendbyłaby to O(n)operacja zawsze - aby ją zamortyzować O(1)(znacznie szybciej !!!), nadmiernie alokuje. Ale teraz musi śledzić przydzielony rozmiar i wypełniony rozmiar ( tuplewystarczy przechowywać jeden rozmiar, ponieważ przydzielony i wypełniony rozmiar są zawsze identyczne). Oznacza to, że każda lista musi przechowywać inny „rozmiar”, który w systemach 64-bitowych jest 64-bitową liczbą całkowitą, ponownie 8 bajtów.

Więc lists potrzebują co najmniej 16 bajtów więcej pamięci niż tuples. Dlaczego powiedziałem „przynajmniej”? Z powodu nadmiernej alokacji. Nadmierna alokacja oznacza, że ​​przydziela więcej miejsca niż potrzeba. Jednak wielkość nadmiernej alokacji zależy od tego, „jak” utworzysz listę i historię dodawania / usuwania:

>>> l = [1,2,3]
>>> l.__sizeof__()
64
>>> l.append(4)  # triggers re-allocation (with over-allocation), because the original list is full
>>> l.__sizeof__()
96

>>> l = []
>>> l.__sizeof__()
40
>>> l.append(1)  # re-allocation with over-allocation
>>> l.__sizeof__()
72
>>> l.append(2)  # no re-alloc
>>> l.append(3)  # no re-alloc
>>> l.__sizeof__()
72
>>> l.append(4)  # still has room, so no over-allocation needed (yet)
>>> l.__sizeof__()
72

Zdjęcia

Postanowiłem stworzyć obrazy towarzyszące powyższemu wyjaśnieniu. Może te są pomocne

Oto jak (schematycznie) jest on przechowywany w pamięci w twoim przykładzie. Podkreśliłem różnice z czerwonymi (z wolnej ręki) cyklami:

wprowadź opis obrazu tutaj

W rzeczywistości jest to tylko przybliżenie, ponieważ intobiekty są również obiektami Pythona, a CPython nawet ponownie wykorzystuje małe liczby całkowite, więc prawdopodobnie dokładniejsza reprezentacja (chociaż nie tak czytelna) obiektów w pamięci byłaby:

wprowadź opis obrazu tutaj

Przydatne linki:

Zwróć uwagę, że __sizeof__tak naprawdę nie zwraca „prawidłowego” rozmiaru! Zwraca tylko rozmiar przechowywanych wartości. Jednak gdy używasz, sys.getsizeofwynik jest inny:

>>> import sys
>>> l = [1,2,3]
>>> t = (1, 2, 3)
>>> sys.getsizeof(l)
88
>>> sys.getsizeof(t)
72

Istnieją 24 „dodatkowe” bajty. Te są prawdziwe , to jest narzut modułu odśmiecania pamięci, który nie jest uwzględniony w __sizeof__metodzie. Dzieje się tak, ponieważ generalnie nie powinieneś używać magicznych metod bezpośrednio - użyj funkcji, które wiedzą, jak sobie z nimi poradzić, w tym przypadku: sys.getsizeof(co faktycznie dodaje narzut GC do wartości zwracanej z __sizeof__).


Re: „ Więc listy potrzebują co najmniej 16 bajtów więcej pamięci niż krotki. ”, Czy nie byłoby to 8? Jeden rozmiar dla krotek i dwa rozmiary dla list oznaczają jeden dodatkowy rozmiar dla list.
ikegami

1
Tak, lista ma jeden dodatkowy "rozmiar" (8 bajtów), ale także przechowuje wskaźnik (8 bajtów) do "tablicy PyObject" zamiast przechowywać je bezpośrednio w strukturze (co robi krotka). 8 + 8 = 16.
MSeifert

2
Kolejny przydatny link o stackoverflow przylist alokacji
pamięci.com

@vishes_shell To nie jest tak naprawdę związane z pytaniem, ponieważ kod w pytaniu w ogóle nie przydziela nadmiernej ilości . Ale tak, jest to przydatne w przypadku, gdy chcesz dowiedzieć się więcej na temat nadmiernej alokacji podczas korzystania z list()lub rozumienia listy.
MSeifert

1
@ user3349993 Krotki są niezmienne, więc nie możesz dołączyć do krotki ani usunąć elementu z krotki.
MSeifert

31

Zagłębię się w podstawę kodu CPython, aby zobaczyć, jak obliczane są rozmiary. W swoim konkretnym przykładzie , nie nadmierne przydziały zostały wykonane, więc nie będę dotykać na tym .

Użyję tutaj wartości 64-bitowych, tak jak ty.


Rozmiar lists jest obliczany z następującej funkcji list_sizeof:

static PyObject *
list_sizeof(PyListObject *self)
{
    Py_ssize_t res;

    res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * sizeof(void*);
    return PyInt_FromSsize_t(res);
}

Oto Py_TYPE(self)makro, które przechwytuje ob_typeof self(zwracające PyList_Type), podczas gdy _PyObject_SIZEjest kolejnym makrem, które pobiera tp_basicsizez tego typu. tp_basicsizejest obliczana jako sizeof(PyListObject)gdzie PyListObjectjest strukturą instancji.

PyListObjectStruktura ma trzy pola:

PyObject_VAR_HEAD     # 24 bytes 
PyObject **ob_item;   #  8 bytes
Py_ssize_t allocated; #  8 bytes

te mają komentarze (które przyciąłem) wyjaśniające, czym są, kliknij powyższy link, aby je przeczytać. PyObject_VAR_HEADrozszerza się w trzech dziedzinach bajtowych (8 ob_refcount, ob_typei ob_size) tak 24wkładu bajtów.

Więc na razie resjest:

sizeof(PyListObject) + self->allocated * sizeof(void*)

lub:

40 + self->allocated * sizeof(void*)

Jeśli instancja listy zawiera przydzielone elementy. druga część oblicza ich wkład. self->allocatedjak sama nazwa wskazuje, zawiera liczbę przydzielonych elementów.

Bez żadnych elementów rozmiar list jest obliczany jako:

>>> [].__sizeof__()
40

tj. rozmiar struktury instancji.


tupleobiekty nie definiują tuple_sizeoffunkcji. Zamiast tego używają object_sizeofdo obliczenia swojego rozmiaru:

static PyObject *
object_sizeof(PyObject *self, PyObject *args)
{
    Py_ssize_t res, isize;

    res = 0;
    isize = self->ob_type->tp_itemsize;
    if (isize > 0)
        res = Py_SIZE(self) * isize;
    res += self->ob_type->tp_basicsize;

    return PyInt_FromSsize_t(res);
}

To, podobnie jak w przypadku lists, pobiera tp_basicsizei, jeśli obiekt ma wartość tp_itemsizeróżną od zera (co oznacza, że ​​ma instancje o zmiennej długości), mnoży liczbę elementów w krotce (którą otrzymuje za pośrednictwem Py_SIZE) tp_itemsize.

tp_basicsizeponownie używa, sizeof(PyTupleObject)gdzie PyTupleObjectstruktura zawiera :

PyObject_VAR_HEAD       # 24 bytes 
PyObject *ob_item[1];   # 8  bytes

Więc bez żadnych elementów (czyli Py_SIZEzwraca 0) rozmiar pustych krotek jest równy sizeof(PyTupleObject):

>>> ().__sizeof__()
24

co? Cóż, tutaj jest dziwactwo, dla którego nie znalazłem wyjaśnienia, tp_basicsizez tuples jest obliczane w następujący sposób:

sizeof(PyTupleObject) - sizeof(PyObject *)

dlaczego 8usuwane są dodatkowe bajty, to tp_basicsizejest coś, czego nie byłem w stanie znaleźć. (Zobacz komentarz MSeiferta w celu uzyskania możliwego wyjaśnienia)


Ale to w zasadzie różnica w twoim konkretnym przykładzie . lists również trzymać wokół wielu przydzielonych elementów, co pomaga określić, kiedy ponownie należy nadmiernie alokować.

Teraz, kiedy dodawane są dodatkowe elementy, listy rzeczywiście wykonują tę nadmierną alokację w celu osiągnięcia dołączeń O (1). Skutkuje to większymi rozmiarami, ponieważ MSeifert ładnie pokrywa się w jego odpowiedzi.


Uważam, że ob_item[1]jest to głównie symbol zastępczy (więc ma sens, aby został odjęty od rozmiaru podstawowego). tuplePrzeznaczono użyciu PyObject_NewVar. Nie rozgryzłem szczegółów, więc to tylko zgadywanie ...
MSeifert

@MSeifert Przepraszamy za to, naprawione :-). Naprawdę nie wiem, pamiętam, że kiedyś go znalazłem, ale nigdy nie poświęcałem mu zbyt wiele uwagi, może po prostu zadam pytanie w pewnym momencie :-)
Dimitris Fasarakis Hilliard

29

Odpowiedź MSeiferta obejmuje to szeroko; aby to uprościć, możesz pomyśleć o:

tuplejest niezmienna. Po ustawieniu nie możesz go zmienić. Dzięki temu wiesz z góry, ile pamięci musisz przydzielić dla tego obiektu.

listjest zmienna. Możesz dodawać lub usuwać elementy do lub z niego. Musi znać jego rozmiar (dla celów wewnętrznych). W razie potrzeby zmienia rozmiar.

Nie ma darmowych posiłków - te możliwości kosztują. Stąd nadmiar pamięci w przypadku list.


3

Rozmiar krotki jest poprzedzony prefiksem, co oznacza, że ​​podczas inicjalizacji krotki interpreter przydziela wystarczającą ilość miejsca na zawarte dane, i to jest koniec tego, dając je niezmienne (nie można ich modyfikować), podczas gdy lista jest zmiennym obiektem, co oznacza dynamikę alokacja pamięci, aby uniknąć przydzielania miejsca za każdym razem, gdy dodajesz lub modyfikujesz listę (przydziel wystarczającą ilość miejsca na zmienione dane i skopiuj do niej dane), przydziela dodatkowe miejsce na przyszłe dodawanie, modyfikacje, ... to prawie podsumowuje.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.