Jaka jest podstawowa struktura danych dla list Pythona?

Question

Jaka jest typowa struktura danych wykorzystywana do implementacji wbudowanego typu danych list Pythona?

Answer 1

Obiekty listy są zaimplementowane jako tablice . Są one zoptymalizowane do szybkiego wykonywania operacji o stałej długości i ponoszą O (n) kosztów przesuwania pamięci dla operacji wstawiania (0, v) pop (0) i , które zmieniają zarówno rozmiar, jak i położenie reprezentatywnej reprezentacji danych .

Zobacz także: http://docs.python.org/library/collections.html#collections.deque

Btw, uważam, że to ciekawe, że samouczek Python na strukturach danych zaleca stosowanie pop (0), aby symulować kolejkę, ale nie wspomina o O (n) lub opcję deque .

http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues

Answer 2

CPython:

typedef struct { 
    PyObject_VAR_HEAD 
    /* 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 
    * list.sort() temporarily sets allocated to -1 to detect mutations. 
    * 
    * Items must normally not be NULL, except during construction when 
    * the list is not yet visible outside the function that builds it. 
    */ 
    Py_ssize_t allocated; 
} PyListObject; 

Jak widać na następnej linii, lista jest zadeklarowana jako tablica wskaźników do PyObjects.

PyObject **ob_item; 

Answer 3

W Jython implementation, jest to ArrayList<PyObject>.