vacio - guardar datos en una matriz python

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

Question

¿Python''s [] 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?

Leí aquí que el acceso a la 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

Hay una gran lista here describe la complejidad del tiempo de los tipos de datos de Python. En su caso, la recuperación de elementos debe ser O (1) vez.

Answer 2

La lista de Python es comparable a ArrayList of Java. El here 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 Matriz ajustable en Lisp y que realmente necesita más espacio, pero el tiempo de acceso es O(1) .

Answer 3

Las tuplas son más rápidas que las listas. No sé la implementación subyacente. Lo leí en ''Dive in Python'' en algún momento :) El extracto relevante:

"Las tuplas son más rápidas que las listas. Si estás definiendo un conjunto constante de valores y lo único que vas a hacer con él es iterar a través de él, utiliza una tupla en lugar de una lista".

Answer 4

Python''s [] se implementa como una matriz , no como una lista vinculada. A pesar de que el cambio de tamaño es O (n), la adición se amortiza O (1) , porque el cambio de tamaño ocurre muy raramente. Si no está familiarizado con cómo funciona esto, lea esta entrada de Wikipedia sobre matrices dinámicas . 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).

Insertar en el medio, sin embargo, siempre es un O (n) ineficiente, porque es posible que haya que mover n elementos.

Las tuplas no son más rápidas que las listas, son solo listas inmutables bajo el capó (*).

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

(*) Aquí hay una función C de "obtener elemento" de la lista 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 esta es una tupla:

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 puede ver, son casi exactamente iguales. Al final, después de algún tipo y comprobación encuadernada, es un acceso de puntero simple con un índice.

[Referencia: documentación de Python sobre Complejidad del tiempo para operaciones de tipo de datos ]