[python] [VI coding] 第十一章 字典 - 教學區

[python] [VI coding] 第十一章 字典

文章瀏覽次數 138

特種兵

特種兵圖像(預設)

2021-07-30 15:59:54

From:211.23.21.202

第十一章 字典

本章介紹 python 另一個內建複合型態,稱為字典。它擁有強大的功能,並且是許多有效演算法的基礎。

11-1 字典是一種對應

字典有點像列表,但比列表更靈活且通用。列表的索引只能是整數,但字典可以是各種型態的值。

字典的索引稱為鍵,鍵對應的稱為值,所以有人稱這樣的組合為 鍵值對

同一個字典中的鍵不能重複,每個鍵各自對應一個值。一個值包含一個數組或列表,甚至另一個字典。

在數學的語言中,稱鍵與值的關係為映射,可以讀成 鍵對應值

dict 是一個內建函數,可建立空字典,所以避免使用這個名稱來當作變數名,下面是定義空字典的範例:

>>> eng2sp = dict()
>>> eng2sp
{}
>>> type(eng2sp)
<class 'dict'>

使用大括號當作字典,空的 {} 就是空的字典。所以初始化一個空字典,也可以這樣做:

>>> d = {}
>>> d
{}
>>> type(d)
<class 'dict'>

下面的例子是一個英文對應西班牙文的字典,其中鍵與值都是字串型態。可試著直接使用中括號的索引方式,來增加字典中的元素:

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

上面的例子,把鍵 'one' 字串對應到值 'uno' 字串上,此時印出字典內容,就能看到這個新添加的鍵值對,python 在大括號中使用冒號 : 來分隔鍵與值。

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

當指定的鍵已存在,就會直接去改變這個鍵的值:

>>> eng2sp['one'] = 'onu'
>>> eng2sp
{'one': 'onu'}

這個輸出格式其實也是輸入格式,可一次產生三個字典中的項目:

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

空格不是語法規定,只是習慣,全部黏在一起不好閱讀。想要用字典添加到字典也可以,需要使用 update() 字典方法:

>>> d = {'one' : 1}
>>> d
{'one': 1}
>>> d1 = {'two' : 2, 'three' : 3}
>>> d1
{'two': 2, 'three': 3}
>>> d.update(d1)
>>> d
{'one': 1, 'two': 2, 'three': 3}
>>> d1
{'two': 2, 'three': 3}
# d 更新了,不過 d1 不變
>>> d = {'one' : 1}
>>> d1 = {'one': 10, 'two' : 2, 'three' : 3}
>>> d.update(d1)
>>> d
{'one': 10, 'two': 2, 'three': 3}
# d 原本的 'one' 索引對應的值會被 d1 相同的索引更新

再回到 eng2sp 的例子,現在打算印出來,注意一下順序:

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

你發現了嗎?字典項目的順序跟原本設定的不太一樣,而且每次執行的順序可能不同,表示字典是無序的。這也是字典和列表很不一樣的地方,列表的數字索引是有序的,所以通常使用字典的鍵來查找值。

不需在意字典的順序,也很少拿整數來當作字典的鍵,而是使用更直觀的字串。想用整數當作字典的鍵也可以,在 python 3.7 以後,字典就會按照添加的順序來排序了。

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

一個鍵總是對應到一個值,但要注意,如果該字典沒有這個鍵,就會產生錯誤訊息:

>>> eng2sp['four']
KeyError: 'four'
# 錯誤的鍵 'four'

之前提過的 len 函數也能作用在字典上,可計算返回該字典有多少個鍵值對:

>>> len(eng2sp)
3

in 運算子也可以用在字典上,確認一個鍵是否存在於字典當中:

>>> 'one' in eng2sp
True
>>> 'uno' in eng2sp
False
# 'uno' 是值,不是鍵

如果想知道這個值有沒有包含在字典中,可以使用 values 方法取出所有值,再搭配 in 運算子,查看該值的集合是否包含其值:

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

因此,前述提到的用 in 來確認字典的鍵是否存在, 'one' in eng2sp 其實是 'one' in eng2sp.keys() 的簡寫。

in 運算子使用不同的演算法來處理列表與字典。以列表而言,在列表中按數字索引順序查找元素,但隨著列表的元素越來越多,查找的時間也會越來越長。

python 的字典使用了一種稱為 雜湊表 的資料結構,具備特殊屬性,不管字典有多大,使用 in 運算子查找的速度都差不多。

11-2 作為計數器的字典集合

如果現在有一個字串,你想知道在這個字串中每個字母各出現了幾次,有以下幾種做法可以參考:

  1. 定義 26 個變數各代表 26 個字母的計數器,然後使用迴圈跑完整個字串來一一比對,有出現的字母就加一。
  2. 做一個含有 26 個字母的列表,將字元轉成數值來比對,然後用計數器累加字母出現的次數。
  3. 做一個鍵為字母、值為計數器的字典,檢查字串的每個字元,並累加計數器的值。

上面的方法都能執行相同的要求,但背後的運算方式不一樣。

使用字典的做法是最方便的,因為只要做好第一次出現與後續累加的處理,程式碼也簡潔很多。

試著打破慣性思維,事實上問題比想像的簡單,完全不需要先把 26 個字母都定義好,而是利用字典的特性來簡化程式。

程式碼類似這樣:

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

函數一開始定義一個空字典變數,然後遍歷這個帶進來的字串。

當字母第一次出現時,新增該字母作為字典的鍵,值則設置為 1。如果已經出現過,就將值累加1, 在迴圈跑完離開後,回傳整個字典。

來看看執行的狀況:

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

字典有一個方法名為 get(), 第一個參數是一個字典的鍵。如果該鍵存在,則回應相對的值;若該鍵不存在,則回應第二個參數作為預設值。

例如:

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

如果沒有給第二個參數,在沒有該鍵的情況下,會回應 None:

>>> h.get('c')
>>>

試著使用 get() 方法改寫 histogram() 函數,應該可以不使用 if 敘述。

11-3 循環和字典

在 for 迴圈敘述中用到字典時,會遍歷字典的鍵,像這樣印出字典的鍵與值:

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

等同於用 keys() 方法來遍歷字典的鍵。下面是它的輸出:

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

再次強調,python 3.7 之前的字典是沒有特定順序的,如果想依特定的順序來排列顯示,必須使用內建函數 sorted():

>>> for key in sorted(h):
...     print(key, h[key])
a 1
o 1
p 1
r 2
t 1

11-4 反向查找

給 d 字典一個鍵 k ,可以很容易地找到對應的值 v ,也就是 d[k] = v

這樣的動作,我們稱為查詢或查找。但會不會有一種需求,就是給 d 字典值 v ,反過來查找 v 的鍵 k 呢?

此時要考慮兩個點,首先,不同的鍵的值或許是一樣的,因為對一個字典來說,鍵是唯一的,但值不是,可能需要建立一個列表來包含它們。

接著,沒有簡單的語法可以完成這個反向查詢的動作,必須自己慢慢搜尋。

這邊有一個自定函數,接受一個作為字典值的參數,然後回傳這個字典最早對應到的鍵:

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

這個函數遍歷所有字典的鍵,並且判斷,若該鍵對應的值是我們想要查找的,就回傳該鍵。

在這個例子中,當所有的鍵都不符合條件時,我們使用 raise 關鍵字來引發 LookupError 這種錯誤。這種類型的錯誤,此時表示找不到符合的鍵值對。

下面是反向查詢成功的執行結果:

>>> h = histogram('parrot')
>>> key = reverseLookup(h, 2)
>>> key
'r'

下面是失敗的執行結果:

>>> key = reverseLookup(h, 3)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 5, in reverse_lookup
LookupError

使用 raise 引發錯誤的效果,與 python 本身發生異常所產生的錯誤原理類似。在這裡, LookupError 函數名稱,就是引發錯誤時的訊息字串。

當然我們也可以指定引發錯誤時所要顯示的訊息,修改 reverse_lookup 函數的最後一行,並執行無法找到對應鍵的範例:

>>> raise LookupError('指定的值不在字典中')
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
LookupError: 指定的值不在字典中

反向搜尋的速度比正向搜尋慢,特別是字典很大的時候,用這種方式比較沒有效率。

小總結一下,使用 keys() 可以遍歷鍵,values() 遍歷值,最後還有個 items() 同時遍歷鍵與值:

>>> d = {'a' : 1, 'b' : 2}
>>> for i, j in d.items():
...     print(i, j)
...
a 1
b 2
# i 是鍵,j 是值

11-5 字典的常用方法

其實有些方法跟列表滿像的:

  1. clear() 清除字典
  2. copy() 回傳一個複製的字典
  3. fromkeys() 回傳複製字典特定的鍵值
  4. get() 回傳特定鍵的值
  5. items() 以 items 物件回傳字典的鍵值對
  6. keys() 以 keys 物件回傳字典的鍵
  7. pop() 給予字典的鍵,並刪除該鍵值對,且回傳其值 (使用關鍵字 del dic['key'] 也行)
  8. popitem() 刪除字典最後的鍵值對,並回傳數組 (python 3.7)
  9. setdefault() 設定字典的鍵值對,該鍵存在則回傳其值,否則直接插入字典中,亦可指定預設值
  10. update() 用字典的形式來更新字典
  11. values() 以 values 物件回傳字典的值

11-6 字典與列表

字典的值也可以是一個列表。之前我們有一個給予字串產生字母出現次數的字典對照表,也就是函數 histogram()

翻轉它的鍵值,也就是字母出現的次數當作鍵,字母當作值。在這樣的情況下,可能會有許多字母出現的次數是一樣的,一個次數對應到多個字母,使用列表值儲存值,就顯得很方便。

請看以下函數:

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

每次循環,我們遍歷原本的字典的鍵,然後把它的值當作新字典的鍵。

那新字典的值該怎麼產生呢?利用一個判斷式,假如字母出現的字數不是新字典的鍵,就把這個鍵值對存到新字典中,並且值是一個列表的形式。

否則把值,也就是字母加入該列表中,表示這些字母出現的次數是相同的,最後回傳新產生的字典。

以下是執行的例子參考:

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

如果把列表當作字典的鍵呢?試試看會發生什麼事:

>>> t = [1, 2, 3]
>>> d = dict()
>>> d[t] = 'oops'
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
TypeError: list objects are unhashable
# 型態錯誤:列表物件是非哈希值

事實上,之前我們已經了解,鍵必須具備不可變的屬性,因為字典是使用雜湊表的方式來處理數據的。

當鍵是可改變的情況下,沒有辦法執行雜湊查找,很可能會對應到錯誤的值。

列表是可以被隨意更動的,可用來當作字典的值,但不能當作鍵。解決這個問題的方法是使用數組來當作鍵,這部分下個章節會描述。

當字典的值是列表的情況下,應該怎麼取值呢?其實原理都是一樣的,先使用字典的鍵呼叫出值,接著加一個 index ,也就是索引,來指定列表的值即可:

d = {
    'a' : 'about',
    'b' : ['book', 'bring', 'bye'],
    'c' : 'cook'
    }
print(d['a'])
# about
print(d['b'][1])
# bring

當然也可以使用迴圈來遍歷它:

for i in d['b']:
	print(i)
# book 
# bring
# bye

如果是列表中的字典,要注意初始化的方式不同,結果也會完全不同:

d = [{}] * 3
print(d)
# [{}, {}, {}] 一個列表中包含三個元素,每個元素都是一個字典,三個元素相等且相同
d[0]['one'] = 1
print(d)
# [{'one': 1}, {'one': 1}, {'one': 1}] 
dd = []
for i in range(3):
	dd.append({})
print(dd)
# [{}, {}, {}] 一個列表中包含三個元素,每個元素都是一個字典,三個元素相等但不同
dd[0]['one'] = 1
print(dd)
# [{'one': 1}, {}, {}]

必須釐清列表中的元素是不是同一個,如果是同一塊記憶體,只要改變其中一個,就會連動影響全部的元素,這部分在上一章中已經提過。

11-7 備忘錄

在第六章中(6-8),我們研究了 fibonacci 數列,當時使用遞迴的方式來撰寫這個功能,但當數字帶入得越大,程式執行的時間也會越長。數字大到一定程度時,這程式顯得很沒效率。

使用遞迴的方式會將數值放於堆疊(stack)當中,一層層的堆疊,數字越大,則需要呼叫更多次函數,也需要更多空間,拉長執行時間。

使用字典的鍵值對特性來處理這個問題,稱為 備忘錄,把計算過的值儲存下來供下一次利用。試著寫一個這種版本的 fibonacci 遞迴函數:

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}

使用 known 把最初的兩組鍵值對存到字典中,當帶入的值已經存在字典的鍵,直接回傳其值。

若該值不是該鍵,則執行公式,以遞迴呼叫。不同的是,把結果存到字典當中,當有紀錄的值存在時,就可以直接調用。

大家可以比較一下這兩種版本執行的效率,有很明顯的差別。

11-8 全域變數

上個例子的 known 就是個全域變數,全域變數定義在所有函數之外,也就是名為 name 的系統變數若為 'main' 時,表示處在全域的空間中,每個函數都可以使用它。

不像一般區域變數,當函數結束時,區域變數也隨之消失。

全域變數可以被不同的函數使用,使用時機通常是在做一些狀態的控制,這個狀態可能會影響多個函數的執行條件。因為需要跨函數的確認狀態,所以會把這個變數定義成全域變數,供需要的函數使用。

類似這樣:

verbose = True

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

example1()
# Running example1

如果試圖重新賦值給全域變數,會有什麼結果:

been_called = False

def example2():
	been_called = True # 僅作用於函數內
	print('在函數內', been_called)

example2()
print('在函數外', been_called)
# 在函數內 True
# 在函數外 False

你會發現全域變數的值沒有被改變,因為此時在該函數中創建了一個名字與全域變數相同的區域變數。

因此設定區域變數的值,並不影響全域變數的值。函數結束後,區域變數也隨之消失。

如果想在函數中改變全域變數的值也可以,但需要使用 global 這個關鍵字來宣告變數:

been_called = False

def example3():
	global been_called
	been_called = True
	print('在函數內', been_called)

example3()
print('在函數外', been_called)
# 在函數內 True
# 在函數外 True

global 關鍵字告訴程式這個變數是全域變數,不要建立一個區域變數,這樣後面的操作就是針對這個全域變數了。

count = 0

def example4():
	count = count + 1 # 錯誤

example4()

如果執行上面的程式,你會得到一個錯誤:

UnboundLocalError: local variable 'count' referenced before assignment

未綁定的區域錯誤:區域變數 count 必須先賦值才能被參照

python 會預設這個 count 是一個區域變數,因為沒有事先定義這個區域變數的值就累加它,所以產生錯誤。

解決方案就是如上所述,使用 global 關鍵字來宣告這個變數是一個全域變數:

def example5():
	global count
	count += 1

count = 0
example5()
print(count)
# 1

如果全域變數擁有可變值的特性,那麼可以在不使用 global 宣告為全域變數時,直接改變其值:

known = {0:0, 1:1}

def example6():
	known[2] = 1

example6()
print(known)
# {0: 0, 1: 1, 2: 1}

因此,可以直接去改變全域列表或字典,因為它們都是可變的變數。之前的例子不行,是因為它們指向了常數或字串。

新增、取代和刪除原本的元素都可以,但想指向另一個字典或列表,還是必須用 global 宣告才行:

known = [1, 2, 3]

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

example7()
print(type(known))
# <class 'dict'>

儘管全域變數帶來了方便性,但若有兩個以上的函數去改變它的值,這樣就很容易出錯,而且除錯上也會增加難度,所以必須小心使用。

除錯

當資料量較大時,手動列印一些值出來確認是困難且不切實際的,以下幾點供參:

  1. 縮小輸入的範圍:
    要讀取檔案做處理時,先讀進幾行數據來模擬就好,發生錯誤會比較容易查找與調校。當功能皆正常時,再擴大資料量以求穩固。
  2. 檢查摘要及類型:
    列印數值的摘要,會比列印整個字典或列表來得有效率,例如檢查列表的長度或字典的鍵值對個數等。通常這種執行錯誤都是值的型態不正確,所以印出值的類型就可以了。
  3. 自己寫測試程式碼:
    有時可以自己寫一些簡單的測試碼,來檢驗程式的正確性,例如計算一個列表的平均值,測試這個平均值是否大於該列表的最大值或者小於最小值,這稱為 合理測試,可檢查出這個值的合理性。另一種測試法是比較兩個結果是否一致,稱為一致性檢查。
  4. 格式化輸出:
    格式化的輸出比較容易幫助我們發現錯誤。之前在第六章的除錯中,已經分享過撰寫格式化的輸出方式來除錯。還有一個 pprint 模組裡的 pprint 函數,可以更人性化地輸出,縮寫正是 pretty-print 的意思。

當然,花在構建測試程式碼的時間越長,程式出錯的機率就越小,需要花費的除錯時間也會減少很多。

動動腦

1.建立一個虛擬的簡單郵遞區號查詢系統,使用字典包含字典的架構,讓使用者輸入縣市名稱時,列出該縣市的郵遞區號表。輸入的縣市不存在則報錯,輸入的值可以相容使用者意外的空格。

# 定義縣市與地區的郵遞區號 字典包字典架構 (簡單一兩個即可)
zip = {
	'台北市' :
		{'松山區' : 105, '士林區' : 111,},
	'新北市' :
		{'新莊區' : 123, '三重區' : 888,},
}

# 縣市輸入錯誤就重新讓使用者輸入,直到正確為止
while True:
	area = input('請輸入縣市:')
	area = area.replace(' ', '') # 整個字串的空白取代
	d = zip.get(area, '沒有該縣市,請重新輸入')
	if isinstance(d, dict): # 回傳字典表示有找到,否則就是一個錯誤訊息字串
		break
	else:
		print(d)
# 印出郵遞區號列表
for k, v in d.items():
	print(k, v)

練習

練習 1 檔名 11-1.py

寫一個函數,讀取 words.txt 的單字當作一個字典的鍵與值。

最後使用 in 敘述來判斷該鍵是否存在於該字典中,比較一下這個方式跟第 10 章的第 9 題練習二分搜尋法,哪一個查詢的速度比較快?

練習 2 檔名 11-2.py

大家應該都玩過井字遊戲吧,來寫一個兩人對戰的井字遊戲程式,井字遊戲的棋盤像這樣:

   |   |   
---+---+---
   |   |   
---+---+---
   |   |   

先下的人是 o ,後下的人是 x。

輸入位置來下子,左上角是 1 ,往右是2 ,最右邊是 3。

中間那排由左到右就是 4, 5, 6 ,最下面是 7, 8, 9。

有三種結束遊戲的狀況:

  1. 輸入 q 結束遊戲
  2. 三個相同符號連成一線時,結束比賽並顯示勝方
  3. 九個格子都下滿後顯示平手,結束遊戲

當後兩種情況都發生時,顯示連成一線的勝方。

遊戲開始,需要有遊戲規則的簡短說明。

棋盤必須整齊,將每個字元、符號與空白都當成同一個大小來對齊。

下子時,輸入的不是 1 到 9 ,或者輸入的位置已經有 o 或 x 了,都需要提示,並且讓使用者重新輸入位置下子。

每次下完子,都要顯示井字棋盤最新的狀況,也就是要把子放進正確的位置,還要顯示回合數與換誰下子。

練習 3 檔名 11-3.py

給你一篇英文文章,請計算這篇文章哪個單字出現最多次,並列出結果。

大小寫不同視為同一個單字,忽略標點符號,輸出時使用小寫即可。

文章內容如下:(小心,裡面有很多陷阱)

Using Python Interactive Mode
Opening Terminal 
Getting your Python version 
Going into the Python Interpreter
Entering commands
Using qPython built-in help
Exiting interactive help
Searching for specific help topics online
Lots of free cheat sheets
Creating a Python Development Workspace
Creating a Folder for your Python Code
Typing, Editing, and Debugging Python Code
Writing Python code
Saving your code
Running Python in VS Code
Simple debugging
The VS Code python debugger
Table of Contents for PYTHON                                 
Writing Code in a Jupyter Notebook
Creating a folder for Jupyter Notebook
Creating and saving a Jupyter notebook
Typing and running code in a notebook
Adding some Markdown text
python markdown process
Saving and opening notebooks
python, it's power program language
about pythonic

執行結果類似這樣:

>>> countWord(str)
該文章出現最多次的單字是 python ,共出現 12 次

參考資料

什麼是雜湊表(哈希表)

pprint

最後更新:2021-07-31 21:31:51

From: 111.249.155.232

By: 特種兵