Jak jest implementowana lista Pythona?

Czy to jest połączona lista, tablica? Rozejrzałem się i znalazłem tylko zgadujących ludzi. Moja znajomość języka C nie jest wystarczająco dobra, aby spojrzeć na kod źródłowy.

To tablica dynamiczna . Praktyczny dowód: indeksowanie trwa (oczywiście z bardzo małymi różnicami (0,0013 µs!)) W tym samym czasie niezależnie od indeksu:

...>python -m timeit --setup="x = [None]*1000" "x[500]"
10000000 loops, best of 3: 0.0579 usec per loop

...>python -m timeit --setup="x = [None]*1000" "x[0]"
10000000 loops, best of 3: 0.0566 usec per loop

Byłbym zdumiony, gdyby IronPython lub Jython korzystały z list połączonych - zrujnowałyby one wydajność wielu wielu powszechnie używanych bibliotek zbudowanych przy założeniu, że listy są tablicami dynamicznymi.

W rzeczywistości kod C jest dość prosty. Rozszerzając jedno makro i przycinając nieistotne komentarze, znajduje się podstawowa struktura listobject.h, która 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_HEADzawiera liczbę odwołań i identyfikator typu. Jest to więc wektor / tablica z nadmierną alokacją. Kod służący do zmiany rozmiaru takiej tablicy, gdy jest pełna, znajduje się w listobject.c. W rzeczywistości nie podwaja tablicy, ale rośnie poprzez przydzielanie

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

do pojemności za każdym razem, gdzie newsizejest żądany rozmiar (niekoniecznie allocated + 1dlatego, że extendzamiast tego można podać dowolną liczbę elementówappend je pojedynczo).

Zobacz także Python FAQ .

W CPythonie listy są tablicami wskaźników. Inne implementacje Pythona mogą przechowywać je na różne sposoby.

Jest to zależne od implementacji, ale IIRC:

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

W ten sposób wszyscy mają dostęp losowy O (1).

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

Lista struktury obiektu C.

Obiekt listy w CPythonie jest reprezentowany przez następującą strukturę C. ob_itemto lista wskaźników do elementów listy. alokowane to liczba gniazd przydzielonych w pamięci.

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

Należy zwrócić uwagę na różnicę między przydzielonymi gniazdami a rozmiarem listy. Rozmiar listy jest taki sam, jak len(l). Liczba przydzielonych gniazd to liczba przydzielona w pamięci. Często zobaczysz, że przydzielone może być większe niż rozmiar. Ma to na celu uniknięcie konieczności wywoływania za reallockażdym razem, gdy do listy dodawany jest nowy element.

...

Dodać

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

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

...

Wstawić

Wstawmy nową liczbę całkowitą (5) na pozycję 1: l.insert(1,5)i spójrzmy, co dzieje się wewnętrznie.

...

Muzyka pop

Kiedy zdejmiesz ostatni element l.pop(), listpop()zostanie wywołany:. list_resizejest wywoływana wewnątrz listpop()i jeśli nowy rozmiar jest mniejszy niż połowa przydzielonego rozmiaru, lista jest zmniejszana.

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

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

...

Usuń Python lista obiekt ma sposobu, aby usunąć element specyficzny: l.remove(5).

Zgodnie z dokumentacją ,

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

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

Aby zrozumieć, dlaczego metoda jest amortyzowana O (1), bez utraty ogólności, załóżmy, że wstawiliśmy a = 2 ^ n elementów, a teraz musimy podwoić naszą tabelę do rozmiaru 2 ^ (n + 1). Oznacza to, że obecnie wykonujemy 2 ^ (n + 1) operacje. W ostatniej kopii wykonaliśmy 2 ^ n operacji. Wcześniej zrobiliśmy 2 ^ (n-1) ... aż do 8,4,2,1. Teraz, jeśli dodamy to, otrzymamy 1 + 2 + 4 + 8 + ... + 2 ^ (n + 1) = 2 ^ (n + 2) - 1 <4 * 2 ^ n = O (2 ^ n) = O (a) suma wpłat (tj. O (1) amortyzowany czas). Należy również zauważyć, że jeśli tabela umożliwia usuwanie, zmniejszanie tabeli musi być wykonane przy innym współczynniku (np. 3x)

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ć. Co ważniejsze, powinieneś wiedzieć, kiedy tworzymy listę, Python automatycznie tworzy reference_id dla tej zmiennej listy. Jeśli zmienisz to poprzez przypisanie innym zmiennej, lista główna ulegnie zmianie. Spróbujmy na przykładzie:

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']

Dodajemy, my_listale nasza główna lista uległa zmianie. Oznacza to, że lista środków nie została przypisana jako lista kopii przypisana jako odniesienie.

W CPythonie lista jest zaimplementowana jako tablica dynamiczna, a więc kiedy dodajemy w tym czasie nie tylko dodawane jest jedno makro, ale przydzielane jest trochę więcej miejsca, aby za każdym razem nie dodawać nowego miejsca.