Quando stavo imparando a programmare, le liste in Python mi sembravano totalmente magiche. Le immaginavo implementate da una sorta di magica infrastruttura di dati che era in parte lista collegata, in parte array, perfetta per tutto.

Come sono cresciuto come ingegnere, ho capito che questo era improbabile. Ho indovinato (correttamente) che piuttosto che una sorta di implementazione magica, era semplicemente supportata da un array ridimensionabile. Ho deciso di leggere il codice e scoprirlo.

Una delle cose belle di CPython è l’implementazione leggibile. Sebbene il file in questione sia più di 2000 righe di C, si tratta per lo più dell’algoritmo di ordinamento, e di boilerplate per rendere le funzioni richiamabili dal codice Python.1 Le operazioni principali della lista sono brevi e semplici.

Ecco alcune cose interessanti che ho trovato leggendo l’implementazione. I frammenti di codice che seguono provengono dal sorgente CPython con commenti esplicativi aggiunti da me.

Ridimensionamento della lista

Se si aggiunge ad una lista Python e l’array di supporto non è abbastanza grande, l’array di supporto deve essere espanso. Quando questo accade, l’array di supporto cresce di circa il 12%. Personalmente, avevo pensato che questo fattore di crescita fosse molto più grande. In Java ArrayList cresce del 50% quando viene espanso2 e in Ruby, Array cresce del 100%.3

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

link al codice di riallocazione di CPython

Ho fatto alcuni esperimenti di performance – preallocare gli array con costrutti come *500 non sembra fare alcuna differenza evidente. Nel mio benchmark non scientifico di appendere ad una lista 100 milioni di volte, Python 3 era molto più lento di Python 2 che era molto più lento di Ruby, tuttavia, è necessaria molta più ricerca per determinare l’impatto (se esiste) del fattore di crescita sulle prestazioni di inserimento.

Inserire all’inizio della lista

Inserire all’inizio di una lista richiede tempo lineare – questo non è così sorprendente dato il resto dell’implementazione, ma è bene sapere che some_list.insert(0,value) è raramente una buona idea. Un utente di Reddit mi ha ricordato i Deques che scambiano tempo costante di inserimento e rimozione da entrambe le estremità in cambio di tempo costante di indicizzazione.

// 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 al codice di inserimento di CPython

Creazione di fette di lista

Prendere una fetta di una lista es. some_listè anche un’operazione a tempo lineare nella dimensione della fetta, quindi di nuovo, nessuna magia. Si potrebbe immaginare di ottimizzare questo con una sorta di semantica copy-on-write, ma il codice CPython favorisce la semplicità:

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

link to CPython slice code

Slice Assignment

È possibile assegnare ad una fetta! Sono sicuro che questo è comunemente noto tra gli sviluppatori Python professionisti, ma non mi sono mai imbattuto in diversi anni di programmazione python, l’ho scoperto solo quando mi sono imbattuto nella funzione list_ass_slice(...) nel codice. Tuttavia, attenzione alle liste grandi – ha bisogno di copiare tutti gli elementi cancellati dalla lista originale, il che raddoppierà brevemente l’uso della memoria.

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

Ordinamento

Gli array Python sono ordinati con un algoritmo conosciuto come “timsort”. È selvaggiamente complicato e descritto in dettaglio in un documento laterale nell’albero dei sorgenti. Approssimativamente, costruisce serie sempre più lunghe di elementi sequenziali e li fonde. A differenza dell’ordinamento normale, inizia cercando sezioni della lista che sono già ordinate (runs nel codice). Questo gli permette di trarre vantaggio dai dati di input che sono già parzialmente ordinati.Una chicca interessante: Per ordinare piccoli array (o piccole sezioni di un array più grande) fino a 64 elementi4, timsort usa l'”ordinamento binario”. Questo è essenzialmente l’ordinamento a inserimento, ma usando la ricerca binaria per inserire l’elemento nella posizione corretta. In realtà è un algoritmo O(n^2)! Un interessante esempio di performance nel mondo reale che vince sulla complessità algoritmica nella pratica. link

Mi sono perso qualcosa di interessante sulle liste CPython? Fatemelo sapere nei commenti.

Grazie a Leah Alpert per aver fornito suggerimenti su questo post.

Vuoi essere informato via email sui nuovi post del blog?

Posto circa una volta ogni poche settimane su argomenti come i database, gli interni del linguaggio e gli algoritmi, e recentemente l’apprendimento profondo.Vuoi assumermi? Sono disponibile per impegni da 1 settimana a qualche mese. Assumetemi!