什麼是python列表函數的運行時複雜性？

Question

我在寫這看起來是這樣的

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函數對於大型列表，這比我預期的要慢得多。

我的問題，那麼，是如何Python列表實現，什麼是以下

• 索引運行的複雜性：list.pop()
• 從膨爆：list[x]
• 從最終膨化開始：list.pop(0)
• 擴展列表：list.append(x)

用於額外信用，拼接或任意彈出。

Answer 1

有a very detailed table on python wiki這回答你的問題。

但是，在您的特定示例中，您應該使用enumerate來獲取循環內可迭代的索引。像這樣：

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

Answer 2

答案是「未定義」。 Python語言沒有定義底層實現。這裏有一些鏈接到郵件列表線程您可能會感興趣的

• It is true that Python's lists have been implemented as contiguous vectors in the C implementations of Python so far.

• I'm not saying that the O() behaviours of these things should be kept a secret or anything. But you need to interpret them in the context of how Python works generally.

而且，寫你的循環會是這樣的更Python的方式：

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

Answer 3

還不能評論，所以

，如果你需要索引和值，那麼使用枚舉：

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

Answer 4

列表確實是O（1）指數 - 他們與比例過度分配的載體來實現，所以執行正如你所期望太多。您找到此代碼比您預期的要慢的可能原因是致電「range(0, len(some_list))」。

range()創建指定大小的新列表，因此如果some_list包含1,000,000個項目，您將在前面創建一個新的百萬項目列表。這種行爲在python3（範圍是一個迭代器）中發生變化，python2相當於xrange，或者更適合您的情況，enumerate

Answer 5

Python列表實際上只是數組。因此，

索引需要O（1）

的流行，再次追加它應該是O（1）按照文檔

退房下面的鏈接瞭解詳細信息：

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