Python基礎_103.數據結構與演算法_查找

02-27

我們只看常用的三種演算法：順序查找（sequential search）、二分查找（binary_search）、哈希表查找（hashing）。並簡單分析三種演算法的效率。

1. 順序查找：從頭向尾逐次查找，直到找到為止。我們使用Python實現順序查找功能。

import timedef sequential_search(a_list,item): pos = 0 # 當前指針位置 found = False # 如果指針未歷遍列表,且當前位置以前未找到該元素，則 while pos < len(a_list) and not found: if a_list[pos] == item: # 如果當前位置是需要查找的元素 found = True else: pos = pos + 1 # 否則指針指向下一個元素 return foundtest_list = [1,2,32,8,17,19,42,13,0]print(sequential_search(test_list,3))print(sequential_search(test_list,13))

上述是通用的順序查找演算法，針對於一些特殊的列表，如順序列表（order list），順序查找演算法做出一些微小的調整：如果當前位置的元素大於要查找的元素，則停止，不必再向後檢索，因為後面的元素肯定都大於要查找的元素。下面我們來看一個例子。

import timedef ordered_sequential_search(a_list,item): pos = 0 # 當前指針位置 found = False stop = False while pos < len(a_list) and not found and not stop: if a_list[pos] == item: found = True else: if a_list[pos] > item: stop = True # 如果當前位置的元素大於要查找的元素，則停止 else: pos = pos + 1 # 指針指向下一個元素 return foundtest_list = [0,2,3,8,13,17,19,32,42]print(ordered_sequential_search(test_list,1))print(ordered_sequential_search(test_list,32))

2. 二分查找：在一個順序列表中，從中位數開始查找，並比較所查找的元素與中位數的大小，將列表二分為含查找元素的區間C1，以及不含查找元素的區間C2。然後再對C1進行二分，直到找到為止。

例如有一個列表[0,2,3,8,13,17,19,32,42]，假設需要查找到32，若使用順序查找法，要先歷遍0，2，3，8，13，17，19共7個元素。若使用二分法，則首先找到列表中點（0+9）//2=4（實際上是第5個元素13）。

此時中點為13，小於需要查找的32，所以32應該在區間[17,19,32,42]中。

再次查找中點（0+3）//2 = 1 （實際上是第2個元素）。此時中點為19，小於需要查找的32，所以32應該在區間[32,42]中。

再次查找中點（0+1）//2 = 0 （實際上是第1個元素）。此時中點為32，我們找到了需要的元素。

下面是實現二分查找的Python代碼：

import timedef binary_search(a_list,item): starttime = time.clock() first = 0 # 當前指針位置 last = len(a_list)-1 found = False while first <= last and not found: midpoint = (first + last) // 2 if a_list[midpoint] == item: found = True else: if item < a_list[midpoint]: # 如果查找元素小於中點 last = midpoint - 1 # 那麼中點作為新的上界 else: first = midpoint + 1 # 否則作為新的下界 endtime = time.clock() return found,(endtime-starttime)test_list = [0,2,3,8,13,17,19,32,42]print(binary_search(test_list,1))print(binary_search(test_list,32))

3. 哈希表查找

無論順序法還是二分法，都無法事先知道我們需要查找的元素的準確位置，因此查找速度較慢。那麼我們是否可以通過一些計算事先找到元素的位置，直接到該位置獲取元素的值呢？試想一下，如果在列表[1,2,3,4]中，我們事先知道3在第三位，那麼直接到第三個位置取值即可，無須從1，2找起，也無需進行二分。

Python里一種最常用的數據結構字典(dictionary)就使用了這種演算法。字典內有鍵(key)和值(data)，如dict= {『1』:』li』, 『2』:』chen』}，當我們需要找學號為2的同學時，程序直接到儲存』chen』的位置獲取值。

下面我們來看哈希表查找更加具體的原理：

首先我們有一個空的哈希表

現在有一組值item[54,26,93,17,77,31]想要放入哈希表中

我們令h(item) = item % 11,如54%11=10，則放至編號為10的位置，則我們有了一個放入了數值的哈希表

現在我們有了放入數值的哈希表，如果我們需要找學號為54的同學，則只需計算54%11=10，即可直接到編號為10的狹槽(slot)獲取值。無須從77開始找起。

哈希表具有一個嚴重的缺陷：哈希值衝突。例如44%11=0，77%11=0，兩個數值被添加到相同狹槽。影響我們查找的結果。

為了解決哈希值衝突的問題，有一個方法便是尋找一個完美的哈希值計算公式，以及足夠大的哈希表，保證每一個可能的放入哈希表的值(item)，都有一個特別的slot。

實際上這種做法十分地浪費存儲空間。比如一個學號可能長達9位，有一億種可能，需要準備一億個slot。

我們的目標是找到一個哈希計算公式，能夠最小化哈希值衝突，容易計算，且使item均勻分布在哈希表之中。

1）我們使用的方法是線性探測(linear probing)。我們想要將44加入哈希表中

經過計算44%11=0，發現slot [0] 已經有值，那麼我們只需要找到下一個空的slot。即將44放入slot [1] 內。

此時有

我們再往裡面添加55%11=0，此時slot [0] 裡面已經有值，找到下一個空的slot [2]，此時有

繼續往裡面添加20%11=9，找到下一個空的slot [3]，此時有

對於這個新的哈希表，我們該如何查找元素？

比如我們需要查找20，經過計算20%11=9，我們到slot [9] 尋找，未發現，然後按照順序查找的方法依次查找slot [10] slot [0] slot [1] slot [2] slot [3]，找到了20。如果哈希表內沒有20，slot [3] 為空，則此時的查找也可以中止了。

這種方法的缺點在於集簇(clustering)，items容易中心化，比如上個哈希表中，items集中在了slot [9-6]內，而slot [7-8]為空。

可以對這種方法稍作改進：加3法（plus3）

我們想要將44加入哈希表中

經過計算44%11=0，發現編號為sl經過計算44%11=0，發現編號為slot [0] 已經有值，則向後位移三位，有

我們再往裡面添加55%11=0，此時slot [0] 裡面已經有值，向後位移三位到slot [3]，已經有值，向後位移三位到slot [6]，已經有值，向後位移三位到slot [9]，已經有值，向後位移三位到slot [1]，空值，則放進去。

我們繼續往裡面添加20%11=9，此時slot [9] 裡面已經有值，向後位移三位到slot [1]，已經有值，向後位移三位到slot [4]，已經有值，向後位移三位到slot [7]，空值，則放進去。

2）線性探測的一種變形——二次探測(quadratic probing)

直觀上很容易理解，如果我們要查找55，則根據55%44=0找到slot [0] 這一列，然後再按照77-44-55的順序找到55。

3）我們使用python創建一個HashTable類, 實現哈希表查找。這個HashTable類，實際上是簡單的字典數據結構。

import timeclass HashTable: def __init__(self): self.size = 11 self.slots = [None] * self.size # 創建一個空的哈希表（第一行） self.data = [None] * self.size # 創建一個空的哈希表（第二行） def put(self,key,data): hash_value = self.hash_function(key,len(self.slots)) # 獲得應該放入的slot的編號 if self.slots[hash_value] == None: # 如果該slot為空 self.slots[hash_value] = key # 則放入該slot self.data[hash_value] = data else: if self.slots[hash_value] == key: # 如果該slot已有相同的key self.data[hash_value] =data # 則替換其value else: next_slot = self.rehash(hash_value,len(self.slots)) # 如果該slot非空，則移至下一個slot while self.slots[next_slot] != None and self.slots[next_slot] != key: next_slot = self.rehash(next_slot,len(self.slots)) # 知道找到空slot或有相同key的slot if self.slots[next_slot] == None: self.slots[next_slot] = key self.data[next_slot] = data else: self.data[next_slot] = data # 替換 def hash_function(self,key,size): return key % size # 返回slot的編號，如55%11=0 def rehash(self,old_hash,size): return (old_hash + 1) % size # 返回下一個slot的編號 (0+1)%11=1 def get(self,key): start_slot = self.hash_function(key,len(self.slots)) # 55%11=0 data = None stop = False found = False position = start_slot # 直到找到或歷遍哈希表為止 while self.slots[position] != None and not found and not stop: if self.slots[position] == key: found = True data = self.data[position] else: position = self.rehash(position,len(self.slots)) # 移到下一個slot if position == start_slot: # 如果已經歷遍哈希表，則停止 stop = True return data def __getitem__(self,key): return self.get(key) def __setitem__(self,key,data): self.put(key,data)h = HashTable()h[54] = "cat" # 自動調用類中定義的方法__setitem__h[26] = "dog"h[93] = "lion"h[17] = "tiger"h[77] = "bird"h[31] = "cow"h[44] = "goat"h[55] = "pig"h[20] = "chicken"print(h.slots)print(h.data)print(h[20])

4. 三種方法的分析對比

我們使用大O表示法來體現演算法時間複雜度：

O(1)表示該演算法的執行時間（或執行時佔用空間）總是為一個常量，不論輸入的數據集是大是小。

O(N)表示一個演算法的性能會隨著輸入數據的大小變化而線性變化。

……

1）順序查找：

當列表的元素越多，順序查找的次數n越大（線性），演算法複雜度為O(N)。

在一個經過排序的列表中查找時

此時演算法複雜度仍然為O(N)。

2）二分查找

兩分法就是將列表中的元素均分成兩部分，直到剩下1個元素為止。如果列表中有n個元素，令計算次數為i，則n/2^(i)=1。例如列表中有2個元素，則2/2^(1)=1，計算1次，有4個元素，則2/2^(2)=1，計算2次。解得i=log2(n)。此時演算法複雜度為O(log n)。

3）哈希表查找

如果僅僅是簡單的哈希表，演算法複雜度僅僅為O(1)，因為我們可以經過1次計算（或者常數次）即可找到。哈希表的優點在查找快捷，在數據通信領域常常得到運用。缺點在於對儲存空間的消耗。

參考資料：Problem Solving with Algorithms and Data Structures