Jak uczyłem się programować, listy w Pythonie wydawały mi się całkowicie magiczne. Wyobrażałem je sobie jako zaimplementowane przez jakąś magiczną strukturę danych, która była częścią linked-list, częścią array, która była idealna do wszystkiego.

Jak rosłem jako inżynier, przyszło mi do głowy, że jest to mało prawdopodobne. Domyśliłem się (poprawnie), że zamiast jakiejś magicznej implementacji, był on po prostu wspierany przez tablicę o zmiennym rozmiarze. Postanowiłem przeczytać kod i dowiedzieć się.

Jedną z miłych rzeczy w CPython jest czytelna implementacja. Chociaż odpowiedni plik ma ponad 2000 linii C, to w większości jest to algorytm sortowania i szata graficzna, aby funkcje można było wywoływać z kodu Pythona.1 Podstawowe operacje na listach są krótkie i proste.

Oto kilka interesujących rzeczy, które znalazłem czytając implementację. Poniższe fragmenty kodu pochodzą ze źródła CPython z komentarzami objaśniającymi dodanymi przeze mnie.

Rozmiar listy

Jeśli dołączasz do listy Pythona, a tablica pomocnicza nie jest wystarczająco duża, tablica pomocnicza musi zostać rozszerzona. Kiedy to się dzieje, tablica pomocnicza jest powiększana o około 12%. Osobiście zakładałem, że ten współczynnik wzrostu jest znacznie większy. W Javie ArrayList rośnie o 50%, gdy jest rozszerzana2, a w Ruby, Array rośnie o 100%.3

// essentially, the new_allocated = new_size + new_size / 8new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

link do kodu realokacji CPython

Wykonałem kilka eksperymentów wydajnościowych – wstępna alokacja tablic za pomocą konstrukcji takich jak *500 nie wydaje się robić żadnej zauważalnej różnicy. W moim nienaukowym benchmarku dołączania do listy 100 milionów razy, Python 3 był znacznie wolniejszy niż Python 2, który był znacznie wolniejszy niż Ruby, jednak potrzeba dużo więcej badań, aby określić wpływ (jeśli w ogóle) czynnika wzrostu na wydajność wstawiania.

Inserting at the beginning of the list

Inserting at the beginning of a list takes linear time – this isn’t that surprising given the rest of the implementation, but it’s good to know that some_list.insert(0,value) is rarely a good idea. Użytkownik Reddit przypomniał mi o Deques, które handlują stałym czasem wstawiania i usuwania z obu końców w zamian za stały czas indeksowania.

// First, shift all the values after our insertion point// over by onefor (i = n; --i >= where; ) items = items;// Increment the number of references to v (the value we're inserting)// for garbage collectionPy_INCREF(v);// insert our actual itemitems = v;return 0;

link do kodu wstawiania CPython

Tworzenie plasterków listy

Branie plasterka listy np. some_list jest również liniową operacją czasową w rozmiarze plasterka, więc znowu nie ma magii. Można sobie wyobrazić optymalizację tego za pomocą jakiejś semantyki copy-on-write, ale kod CPython faworyzuje prostotę:

for (i = 0; i < len; i++) { PyObject *v = src; Py_INCREF(v); dest = v;}

link do kodu CPython slice

Slice Assignment

Możesz przypisać do plasterka! Jestem pewien, że jest to powszechnie znane wśród profesjonalnych programistów Pythona, ale nigdy nie natknąłem się na to w ciągu kilku lat programowania python.Odkryłem tylko, gdy natknąłem się na funkcję list_ass_slice(...) w kodzie. Uważaj jednak na duże listy – musi ona skopiować wszystkie elementy usunięte z oryginalnej listy, co na krótko podwoi zużycie pamięci.

>>> a = >>> a = 'a'>>> a>>> a = >>> a = >>> a

Sortowanie

Tablice Pythona są sortowane za pomocą algorytmu znanego jako “timsort”. Jest on szalenie skomplikowany i opisany szczegółowo w dokumencie pobocznym w drzewie źródeł. Z grubsza, buduje on coraz dłuższe ciągi sekwencyjnych elementów i łączy je. W przeciwieństwie do zwykłego sortowania scalającego, zaczyna od szukania fragmentów listy, które są już posortowane (runs w kodzie). Pozwala to na skorzystanie z danych wejściowych, które są już częściowo posortowane.Interesująca ciekawostka: Do sortowania małych tablic (lub małych sekcji większej tablicy) o długości do 64 elementów4, timsort używa “sortowania binarnego”. Jest to w zasadzie sortowanie przez wstawianie, ale używające wyszukiwania binarnego do wstawienia elementu w odpowiednie miejsce. W rzeczywistości jest to algorytm O(n^2)! Interesujący przykład wydajności w świecie rzeczywistym wygrywającej nad złożonością algorytmiczną w praktyce. link

Czy przegapiłem coś fajnego w listach CPythona? Daj mi znać w komentarzach.

Dzięki Leah Alpert za sugestie dotyczące tego posta.

Chcesz otrzymywać e-maile o nowych postach na blogu?

Postuję mniej więcej raz na kilka tygodni na tematy związane z bazami danych, wnętrzami języków i algorytmami, a ostatnio z głębokim uczeniem.Chcesz mnie zatrudnić? Jestem dostępny na zlecenia od 1 tygodnia do kilku miesięcy. Zatrudnij mnie!

.