Внутренние списки Python, доступ и изменение времени автономной работы

Является ли Python [] списком или массивом?
Является ли время доступа индекса O (1) как массив или O (n) похожим на список?
Является ли добавление/изменение размера O (1) подобно списку или O (n), как массив, или же это гибрид, который может управлять O (1) для доступа и изменения размера?

I читайте здесь, что доступ к массиву на Python очень медленный. Однако, когда я написал мемуаризованную версию рекурсивной процедуры фибоначчи, используя как словарь (словарь Python, по-видимому, очень быстрый), так и список, они имели одинаковое время. Почему это?

Есть ли у кортежа Python более быстрое время доступа, чем список python?

Ответ 1

Python [] реализуется как массив, а не связанный список. Хотя изменение размера является O (n), добавление к нему амортизируется O (1), поскольку изменения размеров происходят очень редко. Если вы не знакомы с тем, как это работает, прочитайте эту запись в Википедии о динамических массивах. Список Python не расширяется в 2 раза каждый раз, это немного сложнее, но расширения все еще предназначены для добавления амортизируемого O (1).

Вставка в середине, однако, всегда является неэффективной O (n), поскольку элементы n могут быть перемещены.

Кортежи не быстрее, чем списки - это просто неизменные списки под капотом (*).

Что касается теста словаря: в зависимости от вашей конкретной реализации кеширование в списке будет быстрее, чем с помощью dict. Тем не менее, Python dicts сильно оптимизирован, и особенно для небольших количеств клавиш будет отлично работать.

(*) Здесь список "получить элемент" функции C в 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];
}

И это кортеж:

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];
}

Как вы можете видеть, они почти точно такие же. В конце концов, после некоторой проверки типа и привязки, это простой доступ указателя с индексом.

[Ссылка: Документация Python по сложности времени для операций с типом данных]

Ответ 2

Здесь представлен отличный список в котором изложена временная сложность типов данных python. В вашем случае поиск предметов должен быть O (1).

Ответ 3

Список Python сопоставим с ArrayList Java. время доступа для получения элемента из списка и кортежа должно O(1). В статье Norvig указывается, что список Python сопоставим с Vector в Java или Adjustable Array в Lisp, и вам действительно нужно больше места, но время доступа O(1).

Ответ 4

Кортежи быстрее, чем списки. Я не знаю основной реализации. Я читал это в "Dive into Python" в какой-то момент:) Соответствующий отрывок:

"Кортежи быстрее, чем списки. Если вы определяете постоянный набор значений и все, что вы когда-либо собираетесь делать с ним, итерации через него, используйте кортеж вместо списка".