什么是Python列表功能运行时的复杂性？(What is the runtime complexi

我在写这看起来是这样的一个Python功能

def foo(some_list):
   for i in range(0, len(some_list)):
       bar(some_list[i], i)

这样它被称为用

x = [0, 1, 2, 3, ... ]
foo(x)

我原以为列表索引访问为O(1)却惊讶地发现，对于大名单，这是比我预想的要慢显著。

我的问题，那么，是如何Python列表实现，什么是以下的运行复杂性

• 索引： list[x]
• 从端部弹出： list.pop()
• 从一开始就弹出： list.pop(0)
• 扩展列表： list.append(x)

对于额外的信用，剪接或任意持久性有机污染物。

Answer 1:

有Python的维基一个非常详细的表格 ，回答你的问题。

然而，在你的具体的例子，你应该使用enumerate的循环中得到一个迭代的索引。 像这样：

for i, item in enumerate(some_seq):
    bar(item, i)

Answer 2:

答案是“不确定”。 Python语言没有定义的底层实现。 这里有一些链接，你可能会感兴趣的邮件列表线程。

• 的确，Python的名单已实现在Python的C实现至今连续载体。

• 我不是说这些东西的O（）行为应保持秘密或任何东西。 但是，你需要解释他们的Python的一般是如何工作的背景。

此外，在编写循环的更Python的方法是这样的：

def foo(some_list):
   for item in some_list:
       bar(item)

Answer 3:

列表确实是O（1）指数 - 他们与比例过度分配的载体来实现，所以执行正如你所期望太多。 你发现这个代码速度低于预期可能的原因是调用“ range(0, len(some_list)) ”。

range()创建指定大小的新名单，因此，如果some_list共有1,000,000项，您将创建一个新的百万项目列表前面。 这python3行为的变化（范围是一个迭代器），以该python2相当于是x范围 ，甚至对你的情况比较好， 枚举

Answer 4:

无法发表评论还，所以

如果你需要索引和值，那么使用枚举：

for idx, item in enumerate(range(10, 100, 10)):
    print idx, item

Answer 5:

Python列表其实也没什么，但阵列。 从而，

索引花费O（1）

对于流行并再次追加它应该是O（1），按照该文档

看看下面的链接了解详细信息：

http://dustycodes.wordpress.com/2012/03/31/pythons-data-structures-complexity-analysis/

文章来源: What is the runtime complexity of python list functions?