之前我們講解了簡易版的跳錶，我希望你能親自動手實現一個更完善的跳錶，同時也可以嘗試實現其他數據結構，例如動態數組或哈希表等。通過實踐，我們能夠發現自己在哪些方面還有所欠缺。這些方法只有在熟練掌握之後才會真正理解，就像我在編寫代碼的過程中，難免會忘記一些方法或如何聲明屬性等等。

我不太願意寫一些業務邏輯，例如典型的購物車邏輯，因為這對個人的成長沒有太大幫助，反而可能使我們陷入業務誤區。但是，數據結構與演算法則不同。好了，言歸正傳，現在我們來看看如何對之前的簡易版跳錶進行優化。

關於跳錶的解釋我就不再贅述了。在上一篇中，我們只定義了一個固定步長為2的跳錶，使節點可以進行跳躍查詢，而不是遍歷節點查詢。然而，真正的跳錶有許多跳躍步長的選擇，並不僅限於單一的步長。因此，今天我們將實現多個跳躍步長的功能，先從簡單的開始練習，例如增加一個固定的跳躍步長4。

如果一個節點具有多個跳躍步長，我們就不能直接用單獨的索引節點來表示了，而是需要使用列表來存儲。否則，我們將不得不為每個步長定義一個索引節點。因此，我修改了節點的數據結構如下：

class SkipNode:

    def __init__(self,value,before_node=None,next_node=None,index_node=None):
        self.value = value
        self.before_node = before_node
        self.next_node = next_node
        # 這是一個三元表達式
        self.index_node = index_node if index_node is not None else []

在這個優化過程中，我們使用了一個三元表達式。在Python中，沒有像Java語言中的三元運算符（?:）那樣的寫法。不過，我們可以換一種寫法：[值1] if [條件] else [值2]，這與 [條件] ? [值1] : [值2] 是等價的。

我們不需要對插入數據的邏輯實現進行修改。唯一的區別在於我們將重新建立索引的方法名更改為re_index_pro。為了節省大家查閱歷史文章的時間，我也直接將方法貼在下麵。

def insert_node(node):
    if head.next_node is None:
        head.next_node = node
        node.next_node = tail
        node.before_node = head
        tail.before_node = node
        return
    temp = head.next_node
    # 當遍歷到尾節點時，需要直接插入
    while temp.next_node is not None or temp == tail:
        if temp.value > node.value or temp == tail:
            before = temp.before_node
            before.next_node = node
            temp.before_node = node
            node.before_node = before
            node.next_node = temp
            break
        temp = temp.next_node
    re_index_pro()

為了提高性能，我們需要對索引進行升級和重新規劃。具體操作包括刪除之前已規劃的索引，並新增索引步長為2和4。

def re_index_pro():
    step = 2
    second_step = 4
    # 用來建立步長為2的索引的節點
    index_temp_for_one = head.next_node
    # 用來建立步長為4的索引的節點
    index_temp_for_second = head.next_node
    # 用來遍歷的節點
    temp = head.next_node
    while temp.next_node is not None:
        temp.index_node = []
        if step == 0:
            step = 2
            index_temp_for_one.index_node.append(temp)
            index_temp_for_one = temp
        if second_step == 0:
            second_step = 4
            index_temp_for_second.index_node.append(temp)
            index_temp_for_second = temp
        temp = temp.next_node
        step -= 1
        second_step -= 1

我們需要對查詢方法進行優化，雖然不需要做大的改動，但由於我們的索引節點已更改為列表存儲，因此需要從列表中獲取值，而不僅僅是從節點獲取。在從列表中獲取值的過程中，你會發現列表可能有多個節點，但我們肯定先要獲取最大步長的節點。如果確定步長太大，我們可以縮小步長，如果仍然無法滿足要求，則需要遍歷節點。

def search_node(value):
    temp = head.next_node
    # 由於我們有了多個索引節點，所以我們需要知道跨步是否長了，如果長了需要縮短步長，也就是尋找低索引的節點。index_node[1] --> index_node[0]
    step = 0
    while temp.next_node is not None:
        step += 1
        if value == temp.value:
            print(f"該值已找到，經歷了{step}次查詢")
            return
        elif value < temp.value:
            print(f"該值在列表不存在,經歷了{step}次查詢")
            return
                if temp.index_node:
            for index in range(len(temp.index_node) - 1, -1, -1):
                if value > temp.index_node[index].value:
                    temp = temp.index_node[index]
                    break
            else:
                temp = temp.next_node
        else:
            temp = temp.next_node
    print(f"該值在列表不存在,經歷了{step}次查詢")

為了使大家更容易查看數據和索引的情況，我對節點遍歷的方法進行了修改，具體如下所示：

def print_node():
    my_list = []
    temp = head.next_node
    while temp.next_node is not None:
        if temp.index_node:
            my_dict = {"current_value": temp.value, "index_value": [node.value for node in temp.index_node]}
        else:
            my_dict = {"current_value": temp.value, "index_value": temp.index_node}  # 設置一個預設值為None
        my_list.append(my_dict)
        temp = temp.next_node
    for item in my_list:
        print(item)

為了進一步優化查詢結果，我們可以簡單地運行一下，通過圖片來觀察優化的效果。從結果可以看出，我們確實減少了兩次查詢的結果，這是一個很好的進展。然而，實際的跳錶結構肯定比我簡化的要複雜得多。例如，步長可能不是固定的，因此我們需要進一步優化。

由於我們已經將索引節點改為列表存儲，所以我們能夠進行一些較大的修改的地方就是重建索引的方法。

為了實現動態設置步長，我需要獲取當前列表的長度。為此，我在文件中定義了一個名為total_size的變數，並將其初始值設置為0。在插入操作時，我會相應地對total_size進行修改。由於多餘的代碼較多，我不會在此粘貼。

def insert_node(node):
    global total_size
    total_size += 1
    if head.next_node is None:
    # 此處省略重覆代碼。

在這個方法中，我們使用了一個global total_size，這樣定義的原因是因為如果我們想要在函數內部修改全局變數，就必須這樣寫。希望你能記住這個規則，不需要太多的解釋。Python沒有像Java那樣的限定符。

def re_index_fin():
    # 使用字典模式保存住step與前一個索引的關係。
    temp_size = total_size
    dict = {}
    dict_list = []
    # 這裡最主要的是要將字典的key值與節點做綁定，要不然當設置索引值時，每個源節點都不一樣。
    while int((temp_size / 2)) > 1:
        temp_size = int((temp_size / 2))
        key_str = f"step_{temp_size}"
        # 我是通過key_str綁定了temp_size步長，這樣當這個步長被減到0時，步長恢復到舊值時，我能找到之前的元素即可。
        dict[key_str] = head.next_node
        dict_list.append(temp_size)
    # 備份一下，因為在步長減到0時需要恢復到舊值
    backup = list(dict_list)
    # 用來遍歷的節點
    temp = head.next_node
    while temp.next_node is not None:
        temp.index_node = []
        # 直接遍歷有幾個步長
        for i in range(len(dict_list)):
            dict_list[i] -= 1  # 每個元素減一
            if dict_list[i] == 0:
                dict_list[i] = backup[i]  # 恢複舊值
                # 找到之前的源節點，我要進行設置索引節點了
                temp_index = f"step_{backup[i]}"
                temp_index_node = dict[temp_index]
                temp_index_node.index_node.append(temp)
                dict[temp_index] = temp  # 更換要設置的源節點
        temp = temp.next_node

這裡有很多迴圈，其實我想將步長和節點綁定到一起，以優化性能。如果你願意，可以嘗試優化一下，畢竟這隻是跳錶的最初版本。讓我們來演示一下，看看優化的效果如何。最終結果如下，其實還是可以的。我大概試了一下，如果數據分佈不太好的話，很可能需要進行多達6次的查詢才能找到結果。

總結

我們實現的跳錶有許多優化的方面需要考慮。例如，我們可以避免每次都重新規劃索引，因為這是不必要的。另外，我們也可以探索不同的步長綁定方法，不一定要按照我目前的方式進行。今天先說到這裡，因為我認為跳錶的實現邏輯相當複雜。我們可以在跳錶這個領域暫時告一段落。