44

我正在编写一个看起来像这样的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)

为了额外的信用,拼接或任意弹出。

4

5 回答 5

37

python wiki上有一个非常详细的表格可以回答您的问题。

但是,在您的特定示例中,您应该使用它enumerate来获取循环内可迭代的索引。像这样:

for i, item in enumerate(some_seq):
    bar(item, i)
于 2009-06-17T07:57:35.523 回答
8

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

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

def foo(some_list):
   for item in some_list:
       bar(item)
于 2009-06-17T07:37:59.370 回答
6

列表确实是 O(1) 索引 - 它们被实现为具有比例过度分配的向量,因此执行得如您所愿。您发现此代码比您预期慢的可能原因是对“ range(0, len(some_list))”的调用。

range()创建一个指定大小的新列表,因此如果 some_list 有 1,000,000 个项目,您将在前面创建一个新的百万项目列表。这种行为在 python3 中发生了变化(范围是一个迭代器),python2 的等效项是xrange,或者更适合您的情况,枚举

于 2009-06-17T08:49:57.837 回答
3

如果您需要索引和值,请使用枚举:

for idx, item in enumerate(range(10, 100, 10)):
    print idx, item
于 2009-06-17T07:53:01.417 回答
1

Python list 实际上只是数组。因此,

索引需要 O(1)

根据文档,对于 pop 并再次追加,它应该是 O(1)

查看以下链接了解详情:

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

于 2012-03-31T11:04:51.360 回答