Qu'est-ce que les données sous-jacentes de la structure pour Python listes?

Question

Quel est le type de sous-jacent structure de données utilisée pour mettre en œuvre Python intégré dans la liste type de données?

Answer 1

Les objets de la liste sont mises en œuvre comme les tableaux de. Ils sont optimisés pour rapide de longueur fixe et d'engager des opérations de O(n) la mémoire des coûts de mouvement pour la pop(0) et insert(0, v) les opérations de changement de la taille et la position de la sous-jacente de la représentation des données.

Voir aussi: http://docs.python.org/library/collections.html#collections.deque

Btw, je trouve intéressant que le tutoriel Python sur des structures de données recommande l'utilisation de la pop(0) pour simuler une file d'attente, mais ne fait pas mention de O(n) ou de la deque option.

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

Answer 2

Disponible:

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;

Comme on peut le voir sur la ligne suivante, la liste est déclarée comme un tableau de pointeurs PyObjects.

PyObject **ob_item;

Answer 3

Dans le Jython mise en œuvre, c'est un ArrayList<PyObject>.