Python中有哪些常用的查找數(shù)據(jù)結構及算法

Python中有哪些常用的查找數(shù)據(jù)結構及算法？針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

一、基本概念

查找（Searching）就是根據(jù)給定的某個值，在查找表中確定一個其關鍵字等于給定值的數(shù)據(jù)元素（或記錄）。

查找表（Search Table）：由同一類型的數(shù)據(jù)元素（或記錄）構成的集合
關鍵字（Key）：數(shù)據(jù)元素中某個數(shù)據(jù)項的值，又稱為鍵值。
主鍵（Primary Key）：可唯一地標識某個數(shù)據(jù)元素或記錄的關鍵字。

查找表按照操作方式可分為：

靜態(tài)查找表（Static Search Table）：只做查找操作的查找表。它的主要操作是：查詢某個“特定的”數(shù)據(jù)元素是否在表中檢索某個“特定的”數(shù)據(jù)元素和各種屬性動態(tài)查找表（Dynamic Search Table）：在查找中同時進行插入或刪除等操作：查找時插入數(shù)據(jù)查找時刪除數(shù)據(jù)

二、無序表查找

也就是數(shù)據(jù)不排序的線性查找，遍歷數(shù)據(jù)元素。
算法分析：最好情況是在第一個位置就找到了，此為O(1)；最壞情況在最后一個位置才找到，此為O(n)；所以平均查找次數(shù)為(n+1)/2。最終時間復雜度為O(n)

# 最基礎的遍歷無序列表的查找算法# 時間復雜度O(n)
def sequential_search(lis, key):
    length = len(lis)    
    for i in range(length):        
        if lis[i] == key:            
            return i    
    else:        
        return False
if __name__ == '__main__':
    LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
    result = sequential_search(LIST, 123)
    print(result)

三、有序表查找

查找表中的數(shù)據(jù)必須按某個主鍵進行某種排序！

1. 二分查找(Binary Search)

算法核心：在查找表中不斷取中間元素與查找值進行比較，以二分之一的倍率進行表范圍的縮小。

# 針對有序查找表的二分查找算法# 時間復雜度O(log(n))
def binary_search(lis, key):
    low = 0
    high = len(lis) - 1
    time = 0
    while low < high:
        time += 1
        mid = int((low + high) / 2)        if key < lis[mid]:
            high = mid - 1
        elif key > lis[mid]:
            low = mid + 1
        else:            # 打印折半的次數(shù)
            print("times: %s" % time)            return mid
    print("times: %s" % time)    return Falseif __name__ == '__main__':
    LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    result = binary_search(LIST, 99)
    print(result)

2. 插值查找

二分查找法雖然已經很不錯了，但還有可以優(yōu)化的地方。
有的時候，對半過濾還不夠狠，要是每次都排除十分之九的數(shù)據(jù)豈不是更好？選擇這個值就是關鍵問題，插值的意義就是：以更快的速度進行縮減。

插值的核心就是使用公式：
value = (key - list[low])/(list[high] - list[low])

用這個value來代替二分查找中的1/2。
上面的代碼可以直接使用，只需要改一句。

# 插值查找算法# 時間復雜度O(log(n))
def binary_search(lis, key):
    low = 0
    high = len(lis) - 1
    time = 0
    while low < high:
        time += 1
        # 計算mid值是插值算法的核心代碼
        mid = low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))
        print("mid=%s, low=%s, high=%s" % (mid, low, high))        if key < lis[mid]:
            high = mid - 1
        elif key > lis[mid]:
            low = mid + 1
        else:            # 打印查找的次數(shù)
            print("times: %s" % time)            return mid
    print("times: %s" % time)    return Falseif __name__ == '__main__':
    LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    result = binary_search(LIST, 444)
    print(result)

插值算法的總體時間復雜度仍然屬于O(log(n))級別的。其優(yōu)點是，對于表內數(shù)據(jù)量較大，且關鍵字分布比較均勻的查找表，使用插值算法的平均性能比二分查找要好得多。反之，對于分布極端不均勻的數(shù)據(jù)，則不適合使用插值算法。

3. 斐波那契查找

由插值算法帶來的啟發(fā)，發(fā)明了斐波那契算法。其核心也是如何優(yōu)化那個縮減速率，使得查找次數(shù)盡量降低。
使用這種算法，前提是已經有一個包含斐波那契數(shù)據(jù)的列表
F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...]

# 斐波那契查找算法# 時間復雜度O(log(n))def fibonacci_search(lis, key):
    # 需要一個現(xiàn)成的斐波那契列表。其最大元素的值必須超過查找表中元素個數(shù)的數(shù)值。
    F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,         233, 377, 610, 987, 1597, 2584, 4181, 6765,         10946, 17711, 28657, 46368]
    low = 0
    high = len(lis) - 1
    
    # 為了使得查找表滿足斐波那契特性，在表的最后添加幾個同樣的值
    # 這個值是原查找表的最后那個元素的值
    # 添加的個數(shù)由F[k]-1-high決定
    k = 0
    while high > F[k]-1:
        k += 1
    print(k)
    i = high    while F[k]-1 > i:
        lis.append(lis[high])
        i += 1
    print(lis)    
    # 算法主邏輯。time用于展示循環(huán)的次數(shù)。
    time = 0
    while low <= high:
        time += 1
        # 為了防止F列表下標溢出，設置if和else
        if k < 2:
            mid = low        else:
            mid = low + F[k-1]-1
        
        print("low=%s, mid=%s, high=%s" % (low, mid, high))        if key < lis[mid]:
            high = mid - 1
            k -= 1
        elif key > lis[mid]:
            low = mid + 1
            k -= 2
        else:            if mid <= high:                # 打印查找的次數(shù)
                print("times: %s" % time)                return mid            else:
                print("times: %s" % time)                return high
    print("times: %s" % time)    return Falseif __name__ == '__main__':
    LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    result = fibonacci_search(LIST, 444)
    print(result)

算法分析：斐波那契查找的整體時間復雜度也為O(log(n))。但就平均性能，要優(yōu)于二分查找。但是在最壞情況下，比如這里如果key為1，則始終處于左側半區(qū)查找，此時其效率要低于二分查找。

總結：二分查找的mid運算是加法與除法，插值查找則是復雜的四則運算，而斐波那契查找只是最簡單的加減運算。在海量數(shù)據(jù)的查找中，這種細微的差別可能會影響最終的查找效率。因此，三種有序表的查找方法本質上是分割點的選擇不同，各有優(yōu)劣，應根據(jù)實際情況進行選擇。

四、線性索引查找

對于海量的無序數(shù)據(jù)，為了提高查找速度，一般會為其構造索引表。
索引就是把一個關鍵字與它相對應的記錄進行關聯(lián)的過程。
一個索引由若干個索引項構成，每個索引項至少包含關鍵字和其對應的記錄在存儲器中的位置等信息。
索引按照結構可以分為：線性索引、樹形索引和多級索引。
線性索引：將索引項的集合通過線性結構來組織，也叫索引表。
線性索引可分為：稠密索引、分塊索引和倒排索引

稠密索引

稠密索引指的是在線性索引中，為數(shù)據(jù)集合中的每個記錄都建立一個索引項。

這其實就相當于給無序的集合，建立了一張有序的線性表。其索引項一定是按照關鍵碼進行有序的排列。
這也相當于把查找過程中需要的排序工作給提前做了。

分塊索引

給大量的無序數(shù)據(jù)集合進行分塊處理，使得塊內無序，塊與塊之間有序。
這其實是有序查找和無序查找的一種中間狀態(tài)或者說妥協(xié)狀態(tài)。因為數(shù)據(jù)量過大，建立完整的稠密索引耗時耗力，占用資源過多；但如果不做任何排序或者索引，那么遍歷的查找也無法接受，只能折中，做一定程度的排序或索引。

分塊索引的效率比遍歷查找的O(n)要高一些，但與二分查找的O(logn)還是要差不少。

倒排索引

不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，這種被稱為倒排索引。其中記錄號表存儲具有相同次關鍵字的所有記錄的地址或引用（可以是指向記錄的指針或該記錄的主關鍵字）。

倒排索引是最基礎的搜索引擎索引技術。

關于Python中有哪些常用的查找數(shù)據(jù)結構及算法問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業(yè)資訊頻道了解更多相關知識。