python列表函数的运行时复杂性是多少？

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),但是很惊讶地发现,对于大型列表,这比我预期的要慢得多.

那么,我的问题是如何实现python列表,以及下面的运行时复杂性是什么

• 索引: 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

答案是"未定义".Python语言没有定义底层实现.以下是您可能感兴趣的邮件列表主题的一些链接.

• 确实,到目前为止,Python的列表已经在Python的C实现中实现为连续向量.

• 我并不是说这些东西的O()行为应该保密或其他任何东西.但是你需要在Python如何工作的上下文中解释它们.

此外,更多Pythonic编写循环的方式是:

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等价物是xrange,或者甚至更适合你的情况,枚举