當實現 list 的數據結構的時候Python 的設計者有很多的選擇. 每一個選擇都有可能影響著 list 操作執行的快慢. 當然他們也試圖優化一些不常見的操作. 但是當權衡的時候，它們還是犧牲了不常用的操作的性能來成全常用功能.
本文地址：http://m.survivalescaperooms.com/archimedes/p/python-datastruct-algorithm-list-dictionary.html，轉載請注明源地址。
設計者有很多的選擇，使他們實現list的數據結構。這些選擇可能對如何快速列表操作的影響進行。幫助他們做出正確的選擇，他們看著人們最常使用的列表數據結構的方式和他們優化列表的實現，導致最常見的操作速度非常快。當然他們也試圖優化不常見的操作，但當一個權衡不得不作一個不太常見的操作的性能往往是犧牲在更常見的操作支持。
兩種常見的操作的索引和分配給索引位置。不管列表多大這兩個操作所需時間相同。稱一個獨立于list大小的操作時間復雜度為O(1).
另一個常見的編程操作是增長一個 list. 有兩種方法來創建一個更長的list.你可以使用附加尾部的方法或串聯運算符。附加的方法是O(1)。然而，連接操作是 O(k) 其中k是需要連接列表的尺寸。這對你很重要，因為它可以幫助你選擇正確的工具的工作來使自己的節目更有效。
讓我們看一下四種不同的方法構造一個包含 n 個數字起始為 0 的list. Listing 1 展示了list的四種不同的方法實現：
Listing 1
def test1(): l = [] for i in range(1000): l = l + [i]def test2(): l = [] for i in range(1000): l.append(i)def test3(): l = [i for i in range(1000)]def test4(): l = list(range(1000))
想要計算每個函數的執行時間, 我們可以使用Python 的 timeit 模塊. timeit 模塊設計的目的是允許程序員在一致的環境下跨平臺的測量時間.
要使用 timeit 你必須先創建一個 Timer 對象，參數為兩個Python聲明. 第一個參數是你想計算時間是函數聲明; 第二個參數是設置測試的次數. timeit 模塊將計算執行時間. timeit 默認情況下執行聲明參數代表的操作100萬次. 當它完成時將返回一個浮點類型的秒數. 然而,因為它執行聲明一百萬次，你可以將結果理解為每執行一次花費多少毫秒. 你還可以傳遞給 timeit 函數一個名叫 number 的參數，它可以允許你指定多少次測試語句來執行. 下面顯示運行每一個測試函數1000次需要多長時間.
t1 = Timer("test1()", "from __main__ import test1")PRint("concat ",t1.timeit(number=1000), "milliseconds")t2 = Timer("test2()", "from __main__ import test2")print("append ",t2.timeit(number=1000), "milliseconds")t3 = Timer("test3()", "from __main__ import test3")print("comprehension ",t3.timeit(number=1000), "milliseconds")t4 = Timer("test4()", "from __main__ import test4")print("list range ",t4.timeit(number=1000), "milliseconds")concat 6.54352807999 millisecondsappend 0.306292057037 millisecondscomprehension 0.147661924362 millisecondslist range 0.0655000209808 milliseconds
上面是實驗中，函數聲明是 test1(), test2(), 等等. 設置的聲明會讓你感覺很怪, 所以讓我們來深入理解一下.你可能很熟悉 from, import 語句, 但這通常是用在一個Python程序文件開始. 在這種情況下, from __main__ import test1 從 __main__命名空間將 test1 調入到 timeit 所在的命名空間.
關于這個小實驗的最后提到的是, 你看到的關于調用也包含一定的開銷時間, 但是我們可以假設, 函數調用的開銷在所有四種情況下是相同的, 我們仍然可以得到比較有意義的操作比較結果. 所以不會說串聯操作精確地需要6.54毫秒, 而說串聯測試函數需要6.54毫秒.
從下表我們可以看到list中所有操作的 Big-O 效率。經過仔細觀察，你可能想知道兩個不同pop的執行時間的差異。當pop在list的尾部操作需要的時間復雜度為O(1), 當pop在list的頭部操作需要的時間復雜度為O(n), 其原因在于Python選擇如何實現列表。
| 操作 | 效率 |
|---|---|
| index [] | O(1) |
| index assignment | O(1) |
| append | O(1) |
| pop() | O(1) |
| pop(i) | O(n) |
| insert(i,item) | O(n) |
| del Operator | O(n) |
| iteration | O(n) |
| contains (in) | O(n) |
| get slice [x:y] | O(k) |
| del slice | O(n) |
| set slice | O(n+k) |
| reverse | O(n) |
| concatenate | O(k) |
| sort | O(n log n) |
| multiply | O(nk) |
為了演示性能上的不同，讓我們使用 timeit模塊做另一個實驗. 我們的目的是能夠證實在一個已知大小的list，從list的尾部和從list的頭部上面 pop 操作, 我們還要測量不同list尺寸下的時間. 我們期望的是從list的尾部和從list的頭部上面 pop 操作時間是保持常數，甚至當list的大小增加的時候, 然而運行時間隨著list的大小的增大而增加.
下面的代碼讓我們可以區分兩種pop操作的執行時間. 就像你看到的那樣，在第一個例子中, 從尾部pop操作花費時間為0.0003 毫秒, 然而從首部pop操作花費時間為 4.82 毫秒.
Listing 2
popzero = timeit.Timer("x.pop(0)", "from __main__ import x")popend = timeit.Timer("x.pop()", "from __main__ import x")x = list(range(2000000))popzero.timeit(number=1000)4.8213560581207275x = list(range(2000000))popend.timeit(number=1000)0.0003161430358886719
上面的代碼可以看到 pop(0)確實比 pop()效率低, 但沒有驗證 pop(0) 時間復雜度為 O(n) 然而 pop() 為 O(1). 要驗證這個我們需要看一個例子同時調用一個list. 看下面的代碼：
popzero = Timer("x.pop(0)", "from __main__ import x")popend = Timer("x.pop()", "from __main__ import x")print("pop(0) pop()")for i in range(1000000,100000001,1000000): x = list(range(i)) pt = popend.timeit(number=1000) x = list(range(i)) pz = popzero.timeit(number=1000) print("%15.5f, %15.5f" %(pz,pt))
Python 第二個主要的數據結構是字典. 你可能記得, 詞典不同于列表的是你可以通過關鍵字而不是位置訪問字典中的項. 最重要的是注意獲得鍵和值的操作的時間復雜度是O(1). 另一個重要的字典操作是包含操作. 查看鍵是否在字典中的操作也為 O(1). 所有的字典操作效率如下表所示：
| 操作 | 效率 |
|---|---|
| copy | O(n) |
| get item | O(1) |
| set item | O(1) |
| delete item | O(1) |
| contains (in) | O(1) |
| iteration | O(n) |
我們最后的性能實驗比較了包含了列表和字典之間的操作性能. 在這個過程中我們將證實, 列表包含操作是O（N）詞典的是O（1）.實驗中我們將使用簡單的比較. 我們會列出一包含一系列數據的list. 然后, 我們將隨機選擇數字并查看數據是否在 list中. 如果我們之前的結論正確, 隨著list的容量的增大, 所需要的時間也增加.
我們將一個dictionary 包含相同的鍵做重復的實驗. 在這個實驗中，我們可以看到, 確定一個數是否在字典中不僅速度快得多, 而且檢查的時間甚至不會隨著字典容量的增加而改變.
下面的代碼實現了這種比較. 注意我們執行相同非操作, number in container. 不同的是第7行 x 是一個list, 第9行 x 是一個dictionary.
import timeitimport randomfor i in range(10000,1000001,20000): t = timeit.Timer("random.randrange(%d) in x"%i, "from __main__ import random,x") x = list(range(i)) lst_time = t.timeit(number=1000) x = {j:None for j in range(i)} d_time = t.timeit(number=1000) print("%d,%10.3f,%10.3f" % (i, lst_time, d_time))
您還可能感興趣：
新聞熱點
疑難解答
