W jaki sposób listy Pythona są implementowane wewnętrznie?


Najlepsza odpowiedź

Wbrew temu, co sugeruje ich nazwa, listy Pythona są w rzeczywistości tablicami, co nigdy nie przestaje mnie irytować (nie „Nie jak mylące nazwy). W szczególności są to dynamiczne tablice z wykładniczym nadmiernym przydziałem, dzięki czemu kod podobny do poniższego ma liniową złożoność:

lst = []

for i in xrange(0, 100000):

lst.append(i)

Co ciekawe, nadmierna alokacja w CPython jest niezwykle konserwatywny, ponieważ przydziela 1,125 * nowy\_rozmiar + 6 (lub + 3, gdy tablica jest mniejsza niż 9 elementów). Ta stała 1,125 jest raczej rzadka i, jak powiedziałem, jest bardzo konserwatywna i dlatego wydaje się zakładać serię append wywołania nie są tak powszechne. Implementacje tablic dynamicznych zwykle używają stałej, takiej jak 2 lub 1.5 (właśnie sprawdziłem implementację std :: vector w gcc / clang i używa 2, wydaje mi się, że implementacja kompilatora Microsoft używa 1.5 ). Nie wiem, skąd wzięły się stałe + 3 i + 6, ale przypuszczam, że ktokolwiek to napisał, w jakiś sposób odkrył, że + 3 było najlepszą zasadą dla małych tablic, że + 6 było najlepsze dla raczej małych tablic ( powiedzmy, mniej niż 100) i że naprawdę nie ma to żadnego znaczenia dla dużych tablic, więc dlaczego nie po prostu go zachować.

Alternatywne implementacje, takie jak Jython i IronPython, wydają się używać dowolnej rodzimej klasy tablic dynamicznych, z której są język (odpowiednio Java i C #), więc mają tę samą charakterystykę wydajności (dokładne klasy bazowe wydają się być ArrayList dla Jython i C # List dla IronPython).

Ktoś zapytał w komentarzach, jak to możliwe mieć tablice elementów typu heterogenicznego ([1, „hello”] to poprawna lista w Pythonie). Odpowiedź na to pytanie jest taka, że ​​tablice technicznie przechowują wskaźniki, a nie same obiekty, co pozwala na to, aby tablica zawierała tylko elementy o określonym rozmiarze. Umieszczanie wskaźników w każdym miejscu w podstawowej implementacji jest wspólną cechą języków z dynamicznym typowaniem, aw rzeczywistości każdego języka, który próbuje udawać, że nie ma wskaźników.

Odpowiedź

Jak powiedział Adrien Lucas Ecoffet, listy Pythona to nic innego jak tablice o zmiennej długości. Zagłębiam się w kod źródłowy cpythona i rozwijam makro, podstawowa struktura jest zdefiniowana jako:

typedef struct {

PyObject\_VAR\_HEAD

PyObject **ob\_item;

Py\_ssize\_t allocated;

} PyListObject;

Komentarze zostały przycięte, odwołaj się do oryginału kod tutaj. 6c2e2de5ab8e Include / listobject.h

PyObject\_VAR\_HEAD zawiera liczbę odwołań i identyfikator typu. Jest to więc wektor / tablica że przydziela. Kod służący do zmiany rozmiaru takiej tablicy, gdy jest ona pełna, znajduje się w listobject.c . Nadmiernie przydziela pamięć, aby uniknąć zbyt częstego wywoływania list\_resize. Wzorzec wzrostu listy to: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88,…

arguments: list object, new size

returns: 0 if OK, -1 if not

list\_resize:

new\_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6)

new\_allocated += newsize

resize ob\_item (list of pointers) to size new\_allocated

return 0

Aby zobaczyć wszystkie wymienione metody implementacji list Pythona, w tym dołączanie, wstawianie, usuwanie, rozszerzanie i inne, zapoznaj się z tym doskonałym postem na blogu.

Implementacja listy Pythona

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *