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.