什么是运行复杂的蟒蛇列职能？

Question

我正在写一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), 但是，惊讶地发现，对于大型列出了这个明显的速度比我预期的。

我的问题是如何是蟒蛇列出的实现，和什么是运行复杂程度以下

• 索引： list[x]
• 出从结束： list.pop()
• 出现，从开始： list.pop(0)
• 延伸的清单： list.append(x)

额外的信贷，接或任意的持久性有机污染物。

Answer 1

那里是 一个非常详细的表格上python wiki 回答你的问题。

然而，在你的特别的实例应用 enumerate 得到一个指数的一个迭代内一个循环。像这样：

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

Answer 2

答案是"不确定".蟒蛇的语言没有定义的基础实施。这里有一些链接到一个邮件列表螺纹你可能会感兴趣。

• 这是真的，蟒蛇的名单 已经实施的作为连续的 矢量在C的实现 蟒为止。

• 我不是说O() 行为的这些事情应该是 保持秘密的或任何东西。但是你 需要解释他们在上下文 如何蟒蛇的工作。

此外，更多的功能已大大增强的方式编写你的循环将是这样的：

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

Answer 3

列出的确是O(1)index-他们实现作为一种矢量的比例度分配，以执行多，你会期望。可能的原因，你找到这段代码比你预期的是呼吁"range(0, len(some_list))".

range() 创建一个新的名单指定大小的，因此，如果some_list有1,000,000个项目，将创建一个新的万的项目清单最前面。这种行为的变化python3(范围是一个迭代)，对此python2等同的是 xrange, 或甚至更好的对于你的情况， 枚举

Answer 4

不能评论，所以

如果你需要的索引和价值，然后用枚举:

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

Answer 5

蟒蛇名单实际上没有什么但阵列。因此，

编制索引需要O(1)

pop和追加再次应该O(1)为每个文档

查阅以下链接的详细信息：

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