Python [] реализован в виде массива , а не связанного списка.Хотя изменение размера равно O (n), к нему добавляется амортизированный O (1) , поскольку изменение размера происходит очень редко.Если вы не знакомы с тем, как это работает, прочитайте эту запись в Википедии о динамических массивах .Список Python не увеличивается в 2 раза каждый раз, он немного сложнее, но расширения по-прежнему предназначены для добавления амортизируемого O (1).
Вставка в середине, однако,всегда неэффективно O (n), потому что n элементов, возможно, придется перемещать.
Кортежи не быстрее списков - это просто неизменяемые списки под капотом (*).
Относительно вашего словарного теста: в зависимости от вашей конкретной реализации, кэширование в списке будетбыстрее чем с диктом.Тем не менее, команды Python высоко оптимизированы, и особенно для небольших количеств ключей будут работать отлично.
(*) Вот функция C "get item" списка в 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 по сложности времени для операций с типами данных ]