是Python的[]列表还是数组？
索引O（1）的访问时间是否像数组或O（n）一样？
是否像列表或O（n）一样追加/调整O（1）的大小，还是可以管理O（1）访问和调整大小的混合？Python内部内部列表，访问和调整运行时间
我该数组访问在Python中非常慢。然而，当我使用字典（Python的字典假设非常快）和列表编写一个递归斐波那契过程的记忆版本时，他们有相同的时间。为什么是这样？
Python元组的访问时间比python列表更快吗？
Python的[]实现为数组，而不是链接列表。虽然调整大小为O（n），但追加到它的是摊销O（1），因为调整很少发生。如果您不熟悉它的工作原理，请阅读Wikipedia entry on dynamic arrays。 Python的列表每次不会扩大2倍，但比这更复杂一点，但扩展仍然是为了使附加分期偿还O（1）而设计的。
但是，在中间插入总是效率低下的O（n），因为n项可能需要移动。
元组不会比列表快 - 它们只是引擎盖下的不可变列表（*）。
关于你的字典测试：根据你的确切实现，列表中的缓存将比字典更快。但是，Python的字典是高度优化的，特别是对于少量的密钥将会表现出色。
（*）这里有一个列表的 “获取项目” 的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 documentation on Time Complexity for data type operations]
+1提供了一个更好，更详细的解释！ – GWW 2011-05-09 04:13:35
有一个伟大的名单here概述了Python数据类型的时间复杂度。在你的情况下，物品检索应该是O（1）时间。
元组是比列表更快。我不知道底层的实现。我在某处读到了'潜入Python':)相关摘录：
“元组比列表要快，如果你定义了一组常量值，并且你将要使用它遍历它，使用一个元组而不是一个列表。“
没有。阅读我更新的答案 – 2011-05-09 04:10:27
对于访问，是的，你是对的。道歉 ：）。我发现http://stackoverflow.com/questions/68630/are-tuples-more-efficient-than-lists-in-python这似乎表明它取决于有问题的操作。 – 2011-05-09 04:15:31
这个答案不是很准确，因为它从头开始建立一个常量列表 - 这是需要更多时间的。然而，这不是实际代码中的常见操作。一旦你有了一份清单，就没有区别。 – 2011-05-09 04:19:44
Python的列表相当于Java的ArrayList。从列表和元组中获取项目的access time应该为O(1)。Norvig的文章指出，Python的列表与Java中的Vector或Lisp中的可调整阵列相当，您确实需要更多空间，但访问时间为O(1)。
每次当您在问题中提及“list”时，是不是指“链接列表”？ – MAK 2011-05-09 06:14:47