Componentes internos de la lista Python, acceso y tiempos de ejecución de redimensionamiento

Question

¿Es Python [] una lista o una matriz?
¿Es el tiempo de acceso de un índice O (1) como una matriz u O (n) como una lista?
¿Se agrega/cambia el tamaño O (1) como una lista o O (n) como una matriz, o es un híbrido que puede administrar O (1) para acceder y cambiar el tamaño?

I read here que el acceso matriz es muy lento en Python. Sin embargo, cuando escribí una versión memorable de un procedimiento recursivo de fibonacci usando un diccionario (el diccionario de Python se supone que es realmente rápido) y una lista, tenían tiempos iguales. ¿Por qué es esto?

¿Tiene una tupla de Python tiempos de acceso más rápidos que una lista de Python?

Answer 1

Python's [] se implementa como una matriz , no es una lista vinculada. Aunque el cambio de tamaño es O (n), se le agrega amortizado O (1), porque los cambios ocurren muy raramente. Si no está familiarizado con cómo funciona esto, lea esto Wikipedia entry on dynamic arrays. La lista de Python no se expande por un factor de 2 cada vez, es un poco más complicado que eso, pero las expansiones todavía están diseñadas para agregar O amortizado (1).

Inserción en el medio, sin embargo, es siempre una O ineficiente (n), porque n artículos pueden tener que ser movido.

tuplas no son más rápido que las listas - son simplemente listas inmutables bajo el capó (*).

En cuanto a la prueba de diccionario: dependiendo de su aplicación exacta, el almacenamiento en caché en una lista será más rápido que con un diccionario. Sin embargo, los dictados de Python están altamente optimizados, y especialmente para pequeñas cantidades de teclas funcionarán muy bien.

---

(*) He aquí de una lista "conseguirá el artículo" función C en Python 2.6:

PyObject * 
PyList_GetItem(PyObject *op, Py_ssize_t i) 
{ 
    if (!PyList_Check(op)) { 
     PyErr_BadInternalCall(); 
     return NULL; 
    } 
    if (i < 0 || i >= Py_SIZE(op)) { 
     if (indexerr == NULL) 
      indexerr = PyString_FromString(
       "list index out of range"); 
     PyErr_SetObject(PyExc_IndexError, indexerr); 
     return NULL; 
    } 
    return ((PyListObject *)op) -> ob_item[i]; 
} 

Y esto es una tupla de:

PyObject * 
PyTuple_GetItem(register PyObject *op, register Py_ssize_t i) 
{ 
    if (!PyTuple_Check(op)) { 
     PyErr_BadInternalCall(); 
     return NULL; 
    } 
    if (i < 0 || i >= Py_SIZE(op)) { 
     PyErr_SetString(PyExc_IndexError, "tuple index out of range"); 
     return NULL; 
    } 
    return ((PyTupleObject *)op) -> ob_item[i]; 
} 

Como se puede ver, que' son casi exactamente lo mismo. Al final, después de algún tipo y comprobación encuadernada, es un acceso de puntero simple con un índice.

[Referencia: Python documentation on Time Complexity for data type operations]

Answer 2

Hay una gran lista de here esbozar la complejidad temporal de los tipos de datos pitón. En su caso, la recuperación de elementos debe ser O (1) vez.

Answer 3

Las tuplas son más rápido que las listas. No sé la implementación subyacente. He leído que en 'Inmersión en Python' en algún momento :) El extracto relevante:.

"Las tuplas son más rápidos que las listas Si está definiendo un conjunto constante de los valores y todo lo que siempre va a hacer con él se itera a través de él, usa una tupla en lugar de una lista ".

Answer 4

lista de Python es comparable a ArrayList de Java. El access time para obtener un elemento de la lista y la tupla debe O(1).El artículo de Norvig señala que la lista de Python es comparable a Vector en Java o Ajustable Array en Lisp y que realmente necesita más espacio, pero el tiempo de acceso es O(1).