Ответ 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 по сложности времени для операций с типом данных]