Think Python/字典

Think Python

一個字典類似於列表，但更通用。在列表中，索引必須是整數；在字典中，它們可以是（幾乎）任何型別。

你可以將字典視為一組索引（稱為鍵）和一組值之間的對映。每個鍵都對映到一個值。鍵和值的關聯稱為鍵值對，有時也稱為項。

例如，我們將構建一個從英語到西班牙語單詞的對映字典，因此鍵和值都是字串。

函式dict建立一個沒有專案的空字典。因為dict是內建函式的名稱，所以應避免將其用作變數名。

>>> eng2sp = dict()
>>> print eng2sp
{}

波浪括號 {} 表示空字典。要向字典中新增專案，可以使用方括號

>>> eng2sp['one'] = 'uno'

此行建立了一個從鍵’one’對映到值 'uno' 的項。如果我們再次列印字典，我們將看到一個鍵值對，鍵和值之間用冒號分隔

>>> print eng2sp
{'one': 'uno'}

此輸出格式也是輸入格式。例如，您可以建立一個包含三個專案的字典

>>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'}

但是，如果您列印eng2sp，您可能會感到驚訝

>>> print eng2sp
{'one': 'uno', 'three': 'tres', 'two': 'dos'}

鍵值對的順序不相同。事實上，如果您在您的計算機上鍵入相同的示例，您可能會得到不同的結果。通常，字典中專案的順序是不可預測的。

但這不成問題，因為字典的元素永遠不會用整數索引來索引。相反，您使用鍵來查詢對應的值

>>> print eng2sp['two']
'dos'

鍵’two’始終對映到值 'dos'，因此專案的順序無關緊要。

如果鍵不在字典中，則會引發異常

>>> print eng2sp['four']
KeyError: 'four'

該len函式適用於字典；它返回鍵值對的數量

>>> len(eng2sp)
3

該in運算子適用於字典；它告訴您某個內容是否作為字典中的鍵出現（作為值出現是不夠的）。

>>> 'one' in eng2sp
True
>>> 'uno' in eng2sp
False

要檢視某個內容是否作為字典中的值出現，您可以使用方法values，它將值作為列表返回，然後使用in運算子

>>> vals = eng2sp.values()
>>> 'uno' in vals
True

您可以對keys:

>>> kees = eng2sp.keys()
>>> ‘one’ in kees
True

該in運算子對列表和字典使用不同的演算法。對於列表，它使用搜索演算法，如第 8.6 節所述。隨著列表變長，搜尋時間與之成正比地變長。對於字典，Python 使用稱為雜湊表的演算法，該演算法具有一個顯著的特性：該in運算子花費的時間大致相同，無論字典中有多少項。我不會解釋這是如何實現的，但您可以在以下網站了解更多資訊：wikipedia.org/wiki/Hash_table.

練習 1

編寫一個函式，讀取 words.txt 中的單詞，並將它們儲存為字典中的鍵。值是什麼無關緊要。然後，您可以使用 in 運算子作為快速檢查字串是否在字典中的方法。

如果您完成了練習 '10.8'，則可以將此實現的速度與列表 'in' 運算子和二分查詢進行比較。

字典作為計數器集合

假設您給定一個字串，並且您想統計每個字母出現的次數。您可以用多種方法做到這一點

您可以為字母表中的每個字母建立一個 26 個變數。然後，您可以遍歷字串，對於每個字元，遞增相應的計數器，可能使用鏈式條件。
您可以建立一個包含 26 個元素的列表。然後，您可以將每個字元轉換為數字（使用內建函式ord），使用該數字作為列表中的索引，並遞增相應的計數器。
您可以建立一個字典，其中字元作為鍵，計數器作為對應值。第一次看到某個字元時，您會向字典中新增一個項。之後，您將遞增現有項的值。

這些選項中的每一個都執行相同的計算，但它們中的每一個都以不同的方式實現該計算。

實現是一種執行計算的方式；一些實現優於其他實現。例如，字典實現的一個優點是我們不必預先知道字串中出現了哪些字母，並且我們只需要為確實出現的字母騰出空間。

以下是程式碼可能的樣子

def histogram(s):
    d = dict()
    for c in s:
        if c not in d:
            d[c] = 1
        else:
            d[c] += 1
    return d

函式的名稱是直方圖，它是指一組計數器（或頻率）的統計術語。

函式的第一行建立一個空字典。該for迴圈遍歷字串。每次迴圈時，如果字元c不在字典中，我們建立一個新的項，其鍵為c以及初始值 1（因為我們已經看到過這個字母一次）。如果c已經存在於字典中，我們遞增d[c].

以下是它的工作原理

>>> h = histogram('brontosaurus')
>>> print h
{'a': 1, 'b': 1, 'o': 2, 'n': 1, 's': 2, 'r': 2, 'u': 2, 't': 1}

直方圖表明字母’a’和 'b' 出現一次；'o' 出現兩次，依此類推。

練習 2

字典有一個名為 'get' 的方法，它接收一個鍵和一個預設值。如果鍵出現在字典中，'get' 返回相應的值；否則，它返回預設值。例如

''>>> h = histogram('a')
>>> print h
{'a': 1}
>>> h.get('a', 0)
1
>>> h.get('b', 0)
0
''

使用 'get' 更簡潔地編寫 'histogram'。您應該能夠消除 'if' 語句。

迴圈和字典

如果您在for語句中使用字典，它會遍歷字典的鍵。例如，print_hist 列印每個鍵及其對應的值

def print_hist(h):
    for c in h:
        print c, h[c]

輸出如下所示

>>> h = histogram('parrot')
>>> print_hist(h)
a 1
p 1
r 2
t 1
o 1

同樣，鍵沒有特定的順序。

練習 3

字典有一個名為 'keys' 的方法，它以列表的形式返回字典的鍵，沒有特定的順序。

修改 print_hist 以按字母順序列印鍵及其值。

反向查詢

給定一個字典d和一個鍵k，很容易找到對應的值v = d[k]。此操作稱為查詢。

但是，如果您有v並且您想找到k？您有兩個問題：首先，可能有多個鍵對映到值v。根據應用程式的不同，您可能能夠選擇一個，或者您可能需要建立一個包含所有這些鍵的列表。其次，沒有簡單的語法來執行反向查詢；您必須搜尋。

這是一個函式，它接收一個值並返回第一個對映到該值的鍵

def reverse_lookup(d, v):
    for k in d:
        if d[k] == v:
            return k
    raise ValueError

此函式是搜尋模式的另一個示例，但它使用了我們以前從未見過的功能，raise。該raise語句會導致異常；在這種情況下，它會導致ValueError，這通常表示引數的值存在問題。

如果我們到達迴圈的末尾，這意味著v未作為字典中的值出現，因此我們引發異常。

以下是一個成功反向查詢的示例

>>> h = histogram('parrot')
>>> k = reverse_lookup(h, 2)
>>> print k
r

以及一個不成功的示例

>>> k = reverse_lookup(h, 3)
Traceback (most recent call last):
  File "&lt;stdin>", line 1, in ?
  File "&lt;stdin>", line 5, in reverse_lookup
ValueError

引發異常時產生的結果與 Python 引發異常時相同：它列印回溯和錯誤訊息。

該raise語句可以可選地接受一個詳細的錯誤訊息作為引數。例如

>>> raise ValueError, 'value does not appear in the dictionary'
Traceback (most recent call last):
  File "&lt;stdin>", line 1, in ?
ValueError: value does not appear in the dictionary

反向查詢比正向查詢慢得多；如果您必須經常執行反向查詢，或者字典變得很大，程式的效能將會受到影響。

練習 4 修改 reverse_lookup 使其構建並返回一個包含所有對映到 v 的鍵的列表，如果沒有則返回空列表。

字典和列表

列表可以作為字典中的值出現。例如，如果您得到一個將字母對映到頻率的字典，您可能希望將其反轉；也就是說，建立一個將頻率對映到字母的字典。由於可能有多個字母具有相同的頻率，因此反轉後的字典中的每個值都應該是一個字母列表。

這是一個反轉字典的函式

def invert_dict(d):
    inv = dict()
    for key in d:
        val = d[key]
        if val not in inv:
            inv[val] = [key]
        else:
            inv[val].append(key)
    return inv

每次迴圈時，key從d獲取一個鍵，val獲取相應的value。如果val不在inv中，這意味著我們以前從未見過它，因此我們建立一個新項並將其初始化為一個單例（包含單個元素的列表）。否則，我們之前見過此值，因此我們將相應的鍵追加到列表中。

這是一個例子

>>> hist = histogram('parrot')
>>> print hist
{'a': 1, 'p': 1, 'r': 2, 't': 1, 'o': 1}
>>> inv = invert_dict(hist)
>>> print inv
{1: ['a', 'p', 't', 'o'], 2: ['r']}

這是一個顯示hist獲取一個鍵，inv:

字典表示為一個框，其中包含型別dict在其上方，以及框內的鍵值對。如果值是整數、浮點數或字串，我通常將它們繪製在框內，但我通常將列表繪製在框外，只是為了使圖表更簡單。

列表可以作為字典中的值，如本例所示，但不能作為鍵。以下是嘗試時發生的情況

>>> t = [1, 2, 3]
>>> d = dict()
>>> d[t] = 'oops'
Traceback (most recent call last):
  File "&lt;stdin>", line 1, in ?
TypeError: list objects are unhashable

我之前提到過字典是使用雜湊表實現的，這意味著鍵必須是可雜湊的。

雜湊是一個函式，它接受任何型別的value並返回一個整數。字典使用這些整數（稱為雜湊值）來儲存和查詢鍵值對。

如果鍵是不可變的，此係統可以正常工作。但是，如果鍵是可變的，例如列表，則會發生不好的事情。例如，當您建立鍵值對時，Python 會對鍵進行雜湊處理並將其儲存在相應的位置。如果您修改鍵然後再次對其進行雜湊處理，它將轉到另一個位置。在這種情況下，您可能對同一個鍵有兩個條目，或者您可能無法找到鍵。無論哪種方式，字典都無法正常工作。

這就是為什麼鍵必須是可雜湊的，以及為什麼像列表這樣的可變型別不是可雜湊的原因。解決此限制的最簡單方法是使用元組，我們將在下一章中看到。

由於字典是可變的，因此不能用作鍵，但可以用作值。

練習 5

閱讀字典方法 setdefault 的文件，並使用它編寫更簡潔的 invert_dict 版本。

備忘錄

如果您玩過第 6.7 節中的fibonacci函式，您可能已經注意到，您提供的引數越大，函式執行的時間就越長。此外，執行時間會非常快地增加。

要了解原因，請考慮以下fibonacci的呼叫圖，其中n=4:

呼叫圖顯示了一組函式幀，每幀都用線連線到其呼叫的函式的幀。在圖的頂部，fibonacci的呼叫圖，其中n=4呼叫fibonacci的呼叫圖，其中n=3獲取一個鍵，n=2。依此類推，fibonacci的呼叫圖，其中n=3呼叫fibonacci的呼叫圖，其中n=2獲取一個鍵，n=1。等等。

計算fibonacci(0)獲取一個鍵，fibonacci(1)被呼叫的次數。這是一個低效的解決方案，並且隨著引數的增大而變得更糟。

一種解決方案是跟蹤已經計算過的值，方法是將它們儲存在字典中。為以後使用而儲存的先前計算的值稱為備忘錄^[1]。以下是使用備忘錄實現的fibonacci。

known = {0:0, 1:1}

def fibonacci(n):
    if n in known:
        return known[n]

    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res
    return res

known是一個字典，用於跟蹤我們已經知道的斐波那契數。它以兩個專案開始：0 對映到 0，1 對映到 1。

每當fibonacci被呼叫時，它都會檢查known。如果結果已存在，則可以立即返回。否則，它必須計算新值，將其新增到字典中，然後返回它。

練習 6

執行此版本的“fibonacci”和原始版本，並使用一系列引數，比較它們的執行時間。

全域性變數

在前面的示例中，known是在函式外部建立的，因此它屬於名為 __main__ 的特殊幀。__main__ 中的變數有時稱為全域性變數，因為可以從任何函式訪問它們。與在函式結束時消失的區域性變數不同，全域性變數會從一個函式呼叫持續到下一個函式呼叫。

通常使用全域性變數作為標誌；也就是說，布林變數指示（標誌）某個條件是否為真。例如，某些程式使用名為verbose的標誌來控制輸出的詳細程度

verbose = True

def example1():
    if verbose:
        print 'Running example1'

如果您嘗試重新分配全域性變數，您可能會感到驚訝。以下示例旨在跟蹤函式是否已被呼叫

been_called = False

def example2():
    been_called = True         # WRONG

但是，如果您執行它，您會發現 been_called 的值不會改變。問題在於example2建立了一個名為 been_called 的新區域性變數。區域性變數在函式結束時消失，並且對全域性變數沒有影響。

要在函式內部重新分配全域性變數，您必須在使用它之前宣告全域性變數

been_called = False

def example2():
    global been_called 
    been_called = True

該global語句告訴直譯器類似於“在此函式中，當我使用 been_called 時，我的意思是全域性變數；不要建立區域性變數”。

這是一個嘗試更新全域性變數的示例

count = 0

def example3():
    count = count + 1          # WRONG

如果您執行它，您將獲得

UnboundLocalError: local variable 'count' referenced before assignment

Python 假設count是區域性的，這意味著您在寫入之前正在讀取它。解決方案，同樣，是宣告countglobal。

def example3():
    global count
    count += 1

如果全域性值是可變的，則可以在不宣告它的情況下修改它

known = {0:0, 1:1}

def example4():
    known[2] = 1

因此，您可以新增、刪除和替換全域性列表或字典中的元素，但如果您想重新分配變數，則必須宣告它

def example5():
    global known
    known = dict()

長整數

如果您計算fibonacci(50)，您將獲得

>>> fibonacci(50)
12586269025L

該L結尾處的表示結果是長整數^[2]，或型別long.

型別為int的值具有有限的範圍；長整數可以任意大，但隨著它們變得越來越大，它們會消耗更多空間和時間。

數學運算子適用於長整數，以及math模組中的函式，因此一般來說，任何與int一起工作的程式碼也將與long.

一起工作。任何時候計算結果太大而無法用整數表示時，Python 會將結果轉換為長整數

>>> 1000 * 1000
1000000
>>> 100000 * 100000
10000000000L

在第一種情況下，結果的型別為int；在第二種情況下，它是long.

練習 7

大整數的指數運算是一些常用公鑰加密演算法的基礎。閱讀維基百科上關於 RSA 演算法^[3]的頁面，並編寫用於編碼和解碼訊息的函式。

除錯

當您使用更大的資料集時，手動列印和檢查資料進行除錯可能會變得笨拙。以下是一些除錯大型資料集的建議

縮減輸入: 如果可能，請減少資料集的大小。例如，如果程式讀取文字檔案，請從前 10 行開始，或使用您可以找到的最小的示例。您可以編輯檔案本身，或者（更好）修改程式，使其僅讀取前n行。如果存在錯誤，您可以將n減少到能夠顯示錯誤的最小值，然後在找到並糾正錯誤時逐漸增加它。
檢查摘要和型別: 與其列印和檢查整個資料集，不如考慮列印資料的摘要：例如，字典中的專案數或數字列表的總和。執行時錯誤的常見原因是值型別不正確。為了除錯此類錯誤，通常足以列印值的型別。
編寫自檢: 有時你可以編寫程式碼來自動檢查錯誤。例如，如果你正在計算一組數字的平均值，你可以檢查結果是否不超過列表中的最大元素或小於最小元素。這被稱為“健全性檢查”，因為它檢測“不合理”的結果。另一種檢查方法是比較兩個不同計算的結果，以檢視它們是否一致。這被稱為“一致性檢查”。
漂亮列印輸出: 格式化除錯輸出可以更容易地發現錯誤。我們在第 6.9 節中看到了一個示例。pprint模組提供了一個pprint函式，該函式以更易於人類閱讀的格式顯示內建型別。

同樣，花在構建腳手架上的時間可以減少花在除錯上的時間。

詞彙表

字典: 從一組鍵到其對應值的對映。
鍵值對: 從鍵到值的對映的表示。
專案: 鍵值對的另一個名稱。
key: 作為鍵值對第一部分出現在字典中的物件。
值: 作為鍵值對第二部分出現在字典中的物件。這比我們之前使用“值”一詞更具體。
實現: 執行計算的一種方法。
雜湊表: 用於實現 Python 字典的演算法。
雜湊函式: 雜湊表用來計算鍵位置的函式。
可雜湊的: 具有雜湊函式的型別。不可變型別（如整數、浮點數和字串）是可雜湊的；可變型別（如列表和字典）不可雜湊。
查詢: 字典操作，它接收一個鍵並找到對應的值。
反向查詢: 字典操作，它接收一個值並找到對映到它的一個或多個鍵。
單例: 具有單個元素的列表（或其他序列）。
呼叫圖: 一個圖表，顯示程式執行期間建立的每個框架，從每個呼叫者到每個被呼叫者都有一條箭頭。
直方圖: 一組計數器。
備忘錄: 儲存的計算值，以避免不必要的未來計算。
全域性變數: 在函式外部定義的變數。可以從任何函式訪問全域性變數。
標誌: 用於指示條件是否為真的布林變數。
宣告: 像global這樣的語句告訴直譯器有關變數的資訊。

練習-8

        Dictionaries have a method called 'keys' that returns the keys of the dictionary, in

沒有特定的順序，作為列表。修改 print_hist 以按字母順序列印鍵及其值。

練習 9

如果您可以旋轉其中一個單詞並得到另一個單詞，則兩個單詞是“旋轉對”（請參閱練習 '8.12' 中的 rotate_word ）。

編寫一個程式，讀取單詞列表並找到所有旋轉對。

練習 10

這是來自 Car Talk^[4]的另一個難題：

這是丹·奧利裡傳送的。他最近遇到一個常見的單音節五字母詞，它具有以下獨特屬性。當您刪除第一個字母時，剩餘的字母構成原始單詞的同音詞，即發音完全相同的詞。替換第一個字母，即放回它並刪除第二個字母，結果是原始單詞的另一個同音詞。問題是，這個詞是什麼？
現在我將舉一個不成功的例子。讓我們看看五字母詞“wrack”。W-R-A-C-K，你知道，就像“wrack with pain”。如果我刪除第一個字母，我將得到一個四字母詞，“R-A-C-K”。就像“天哪，你看到那隻雄鹿的角了嗎？它一定是一個九點！”這是一個完美的同音詞。如果你把“w”放回去，然後刪除“r”，你就會得到“wack”這個詞，它是一個真實的詞，但它不是其他兩個詞的同音詞。
但是，確實至少有一個單詞，丹和我們知道的，如果你刪除前兩個字母中的任何一個以建立兩個新的四字母詞，它將產生兩個同音詞。問題是，這個詞是什麼？

您可以使用練習 '11.1' 中的字典來檢查字串是否在單詞列表中。

要檢查兩個單詞是否為同音詞，您可以使用 CMU 發音詞典。您可以從 www.speech.cs.cmu.edu/cgi-bin/cmudict 或 thinkpython.com/code/c06d 下載它，您還可以下載 thinkpython.com/code/pronounce.py ，它提供了一個名為 read_dictionary 的函式，該函式讀取發音詞典並返回一個 Python 字典，該字典將每個單詞對映到描述其主要發音的字串。

編寫一個程式，列出解決此難題的所有單詞。您可以在 thinkpython.com/code/homophone.py 上看到我的解決方案。

註釋

↑ 請參閱 wikipedia.org/wiki/Memoization
↑ 在 Python 3.0 中，long 型別消失了；所有整數，即使是非常大的整數，也都是 int 型別。
↑ wikipedia.org/wiki/RSA
↑ www.cartalk.com/content/puzzler/transcripts/200717

[1] 請參閱 wikipedia.org/wiki/Memoization

[2] 在 Python 3.0 中，long 型別消失了；所有整數，即使是非常大的整數，也都是 int 型別。

[3] wikipedia.org/wiki/RSA

[4] www.cartalk.com/content/puzzler/transcripts/200717

[1]

[2]

[3]

[4]