Jak zaimplementowana jest lista Pythona?

Kod C jest całkiem prosty. Rozbudowując jedno makro i przycinając kilka nieistotnych komentarzy, podstawowa struktura jest w listobject.h, który definiuje listę jako:

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size;

    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     */
    Py_ssize_t allocated;
} PyListObject;

PyObject_HEAD zawiera liczbę odniesień i identyfikator typu. Więc jest to wektor / tablica, która jest nadrzędna. Kod do zmiany rozmiaru takiej tablicy gdy jest pełna jest w listobject.c. W rzeczywistości nie podwaja tablicy, ale rośnie przez przydzielenie

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;

Do pojemności za każdym razem, gdzie newsize jest żądany rozmiar (niekoniecznie allocated + 1, ponieważ można extend przez dowolną liczbę elementów zamiast append ' ing je jeden po drugim).

Zobacz także Python FAQ.

W Cpythonie listy są tablicami wskaźników. Inne implementacje Pythona mogą wybrać przechowywanie ich na różne sposoby.

Jest to zależne od implementacji, ale IIRC:

• CPython używa tablicy wskaźników
• Jython używa ArrayList
IronPython najwyraźniej również używa tablicy. Możesz przejrzeć kod źródłowy , aby się dowiedzieć.

Tak więc wszystkie mają o (1) losowy dostęp.

Proponuję artykuł Laurenta Luce ' a "implementacja listy Pythona" . Było to dla mnie bardzo przydatne, ponieważ autor wyjaśnia, w jaki sposób lista jest zaimplementowana w Cpythonie i używa do tego celu doskonałych diagramów.

Lista obiektów C struktura

Obiekt list w CPython jest reprezentowany przez następującą strukturę C. ob_item jest listą wskaźników do elementów listy. alokowany to Liczba slotów przydzielonych w pamięci.

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

Ważne jest, aby zauważyć różnicę między przydzielonymi przydziałami czasu na start lub lądowanie a wielkością listy. Rozmiar listy jest taki sam jak len(l). Liczba przydzielonych slotów jest tym, co zostało przydzielone w pamięci. Często zobaczysz, że przydzielone mogą być większe niż rozmiar. Ma to na celu uniknięcie konieczności wywoływania realloc za każdym razem, gdy nowe elementy są dodawane do listy.

...

Dołącz

Dodajemy liczbę całkowitą do listy: l.append(1). Co? dzieje się?

Kontynuujemy dodając jeszcze jeden element: l.append(2). list_resize jest wywoływany z n + 1 = 2, ale ponieważ alokowany rozmiar wynosi 4, nie ma potrzeby przydzielania większej ilości pamięci. To samo dzieje się, gdy dodajemy 2 kolejne liczby całkowite: l.append(3), l.append(4). Poniższy diagram pokazuje, co mamy do tej pory.

...

Insert

Wstawmy nową liczbę całkowitą (5) w pozycji 1: l.insert(1,5) i przyjrzyjmy się co dzieje się wewnętrznie.

...

Pop

Kiedy wyskakujesz ostatni element: l.pop(), listpop() nazywa się. {[6] } jest wywoływany wewnątrz listpop() i jeśli nowy rozmiar jest mniejszy niż połowa przydzielonego rozmiaru, lista jest zmniejszana.

Można zauważyć, że slot 4 nadal wskazuje na liczbę całkowitą, ale ważną rzeczą jest rozmiar listy, która wynosi teraz 4. Dodajmy jeszcze jeden element. W list_resize(), Rozmiar – 1 = 4-1 = 3 to mniej niż połowa przydzielonych slotów, więc lista jest zmniejszona do 6 slotów, a nowy rozmiar listy wynosi teraz 3.

Można zauważyć, że sloty 3 i 4 nadal wskazują na niektóre liczby całkowite, ale ważne jest rozmiar listy, która jest teraz 3.

...

Usuń Obiekt Python list posiada metodę usuwania określonego elementu: l.remove(5).

Zgodnie z dokumentacją ,

Listy Pythona są tablicami o zmiennej długości, a nie listami połączonymi w stylu Lispu.

Jak stwierdzili inni, listy (gdy są znacznie Duże) są implementowane przez przydzielenie określonej ilości miejsca, a jeśli to miejsce powinno się wypełnić, przydzielenie większej ilości miejsca i kopiowanie elementów.

Aby zrozumieć, dlaczego metoda jest o(1) amortyzowana, bez utraty ogólności, Załóżmy, że wstawiliśmy elementy a = 2^n i teraz musimy podwoić naszą tabelę do rozmiaru 2^(n+1). Oznacza to, że obecnie wykonujemy 2^(n+1) operacji. W ostatniej kopii wykonaliśmy 2 operacje^N. Wcześniej zrobiliśmy 2^(n-1)... / align = "left" / 84211 Jeśli dodamy je do siebie, otrzymamy 1 + 2 + 4 + 8 + ... + 2^(n+1) = 2^(n+2) - 1

Lista w Pythonie jest czymś w rodzaju tablicy, w której można przechowywać wiele wartości. Lista jest zmienna, co oznacza, że możesz ją zmienić. Najważniejszą rzeczą, którą powinieneś wiedzieć, kiedy tworzymy Listę, Python automatycznie tworzy identyfikator reference_id dla tej zmiennej list. Jeśli zmienisz ją przez przypisanie innej zmiennej, główna lista zostanie zmieniona. Spróbujmy z przykładem:

list_one = [1,2,3,4]

my_list = list_one

#my_list: [1,2,3,4]

my_list.append("new")

#my_list: [1,2,3,4,'new']
#list_one: [1,2,3,4,'new']

Dołączamy my_list ale nasza główna lista się zmieniła. Lista ta nie została przypisana jako Lista kopii przypisana jako jej Referencja.

W Cpythonie lista jest zaimplementowana jako tablica dynamiczna, a więc kiedy dodamy w tym czasie nie tylko jedno makro, ale także przydzielane jest trochę więcej miejsca, aby za każdym razem nie dodawano nowej przestrzeni.