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

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

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

Существует ли у кортежа Python более быстрый доступ, чем список python?

4 Solutions collect form web for “Внутренние списки Python, доступ и изменение времени автономной работы”

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

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

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

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


(*) Вот список «get item» функции 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 по сложности времени для операций типа данных ]

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

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

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

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

  • Python: список списка фильтров с другим списком
  • Доступ к списку элементов со списком индексов
  • Python: как построить dict из простого списка ключей и значений
  • преобразование списка целых чисел в диапазон в python
  • python delete подстроки из списка строк
  • Сравнение двух списков в Python
  • Настройте нарезку Python, пожалуйста, сообщите
  • Самый эффективный способ поиска в списке dicts
  • Python, двумерный список и координаты
  • Ротация списка Python
  • Python - как отсортировать список числовых значений в порядке возрастания
  • Python - лучший язык программирования в мире.