Python算法教程第二章知識點：計時模塊、字典與散哈希表、

微信公眾號：geekkr
本文目錄：一、計時模塊；二、字典與散哈希表；三、圖與樹的實現；四、成員查詢；五、插入對象
</br>
一、計時模塊（timeit、cProfile）

import timeit
timeit.timeit('x = 1 + 2')

既然學習算法，那么來計算程序所耗費的時間是重要的，但是需要注意：timeit()計時函數會多次運行相關的代碼段并求得平均值，以提高計時的精準度，所以，我們需要預防早先的執行操作影響之后代碼的執行。舉個栗子：若我們執行排序算法，則只有第一次執行代碼時是在隨機的情況下計時，剩余的數千次運行則都在有序列表的前提下運行，這會導致最終的計時結果偏低。所以，可以嘗試使用cProfile模塊。

import cProfile
cProfile.run('函數名'）

cProfile（或profile）能夠將各函數的計時結果打印出來。
</br>
</br>
</br>
二、字典與散哈希表（hashing）
哈希表（Hash table，也叫散列表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。可以猜到，哈希表被用于Python中字典（dict）類型與集合（set）類型的實現，且我們對其元素的訪問也只是耗費常數級的時間。而Python中的hash()函數則用于獲取一個對象（字符串或者數值等）的哈希值。
</br>
</br>
</br>
三、圖與樹的實現
鄰接列表可以視為圖結構的表達方式。

# 舉個鄰接列表的栗子

a, b, c, d, e, f, g, h = range(8)
N = [
    {b, c, d, e, f}, # a節點所指向的節點，如果想要加權則利用字典類型改為{b:2, c:1, …}
    {c, e}, # b …
    aegqsqibtmh,
    {e},
    {f},
    {c, g, h},
    {f, h},
    {f, g}
]

b in N[a]
len(N[f])
N[a][b]

同時，鄰接矩陣也是圖的一種常見的表示方式。

# 舉個鄰接矩陣的栗子

a, b, c, d, e, f, g, h = range(8)
N = [[0,1,1,1,1,1,0,0],
     [0,0,1,0,1,0,0,0],
     [0,0,0,1,0,0,0,0],
     [0,0,0,0,0,1,0,0],
     [0,0,1,0,0,0,1,1],
     [0,0,0,0,0,1,0,1],
     [0,0,0,0,0,1,1,0]]

N[a][b] # Neighborhood membership, answer is 1
sum(N[f]) # Degree, answer is 3

二叉樹的表示方式。

class Tree：
    def __init__(self, left, right):
        self.left = left
        self.right = right

t = Tree(Tree('a', 'b'), Tree('c', 'd'))
t.right.left # answer is 'c'

多路搜索樹的表達方式。

class Tree:
    def __init__(self, kids, next=None):
        self.kids = kids
        self.next = next

t = Tree(Tree('a', Tree('b', Tree('c', Tree('d')))))
t.kids.next.next.kids # answer is 'c'

</br>
</br>
</br>
四、成員查詢

from random import randrange
L = [randrange(10000) for i in range(1000)]

1 in L # 第一種查詢操作

S = set(L)
1 in S # 第二種查詢操作

看起來第二種查詢操作多此一舉，但要知道，在數列中查詢成員所耗費的時間是線性級的，而在集合中則是常數級的。
</br>
</br>
</br>
五、插入對象

# 比較兩段代碼

# 第一段代碼
s = ''"
for chunk in string_producer():
    s += chunk

# 第二段代碼
chunks = []
for chunk in string_producer():
    chunks.append(chunk)
s = ' '.join(chunks)

相比較之下，第二段代碼是更為高效的解決方案。因為在執行第一段代碼時，我們每次執行“+=”時都需要新建一個字符串并對其進行轉移性質的賦值，以至于其時間復雜度為平方級。同樣，在對數列進行相加操作時，使用extend()函數要比sum()函數高效得多。