之前我們講解了簡易版的跳表，我希望你能親自動手實現(xiàn)一個更完善的跳表，同時也可以嘗試實現(xiàn)其他數(shù)據(jù)結(jié)構(gòu)，例如動態(tài)數(shù)組或哈希表等。通過實踐，我們能夠發(fā)現(xiàn)自己在哪些方面還有所欠缺。這些方法只有在熟練掌握之后才會真正理解，就像我在編寫代碼的過程中，難免會忘記一些方法或如何聲明屬性等等。
我不太愿意寫一些業(yè)務(wù)邏輯，例如典型的購物車邏輯，因為這對個人的成長沒有太大幫助，反而可能使我們陷入業(yè)務(wù)誤區(qū)。但是，數(shù)據(jù)結(jié)構(gòu)與算法則不同。好了，言歸正傳，現(xiàn)在我們來看看如何對之前的簡易版跳表進行優(yōu)化。
關(guān)于跳表的解釋我就不再贅述了。在上一篇中，我們只定義了一個固定步長為2的跳表，使節(jié)點可以進行跳躍查詢，而不是遍歷節(jié)點查詢。然而，真正的跳表有許多跳躍步長的選擇，并不僅限于單一的步長。因此，今天我們將實現(xiàn)多個跳躍步長的功能，先從簡單的開始練習(xí)，例如增加一個固定的跳躍步長4。
如果一個節(jié)點具有多個跳躍步長，我們就不能直接用單獨的索引節(jié)點來表示了，而是需要使用列表來存儲。否則，我們將不得不為每個步長定義一個索引節(jié)點。因此，我修改了節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：
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 []
在這個優(yōu)化過程中，我們使用了一個三元表達式。在Python中，沒有像Java語言中的三元運算符（?:）那樣的寫法。不過，我們可以換一種寫法：[值1] if [條件] else [值2]，這與 [條件] ? [值1] : [值2] 是等價的。
我們不需要對插入數(shù)據(jù)的邏輯實現(xiàn)進行修改。唯一的區(qū)別在于我們將重新建立索引的方法名更改為re_index_pro。為了節(jié)省大家查閱歷史文章的時間，我也直接將方法貼在下面。
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
# 當遍歷到尾節(jié)點時，需要直接插入
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()
為了提高性能，我們需要對索引進行升級和重新規(guī)劃。具體操作包括刪除之前已規(guī)劃的索引，并新增索引步長為2和4。
def re_index_pro():
step = 2
second_step = 4
# 用來建立步長為2的索引的節(jié)點
index_temp_for_one = head.next_node
# 用來建立步長為4的索引的節(jié)點
index_temp_for_second = head.next_node
# 用來遍歷的節(jié)點
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
我們需要對查詢方法進行優(yōu)化，雖然不需要做大的改動，但由于我們的索引節(jié)點已更改為列表存儲，因此需要從列表中獲取值，而不僅僅是從節(jié)點獲取。在從列表中獲取值的過程中，你會發(fā)現(xiàn)列表可能有多個節(jié)點，但我們肯定先要獲取最大步長的節(jié)點。如果確定步長太大，我們可以縮小步長，如果仍然無法滿足要求，則需要遍歷節(jié)點。
def search_node(value):
temp = head.next_node
# 由于我們有了多個索引節(jié)點，所以我們需要知道跨步是否長了，如果長了需要縮短步長，也就是尋找低索引的節(jié)點。index_node[1] --> index_node[0]
step = 0
while temp.next_node is not None:
step += 1
if value == temp.value:
print(f"該值已找到，經(jīng)歷了{step}次查詢")
return
elif value < temp.value:
print(f"該值在列表不存在,經(jīng)歷了{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"該值在列表不存在,經(jīng)歷了{step}次查詢")
為了使大家更容易查看數(shù)據(jù)和索引的情況，我對節(jié)點遍歷的方法進行了修改，具體如下所示：
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} # 設(shè)置一個默認值為None
my_list.append(my_dict)
temp = temp.next_node
for item in my_list:
print(item)
為了進一步優(yōu)化查詢結(jié)果，我們可以簡單地運行一下，通過圖片來觀察優(yōu)化的效果。從結(jié)果可以看出，我們確實減少了兩次查詢的結(jié)果，這是一個很好的進展。然而，實際的跳表結(jié)構(gòu)肯定比我簡化的要復(fù)雜得多。例如，步長可能不是固定的，因此我們需要進一步優(yōu)化。
由于我們已經(jīng)將索引節(jié)點改為列表存儲，所以我們能夠進行一些較大的修改的地方就是重建索引的方法。
為了實現(xiàn)動態(tài)設(shè)置步長，我需要獲取當前列表的長度。為此，我在文件中定義了一個名為total_size的變量，并將其初始值設(shè)置為0。在插入操作時，我會相應(yīng)地對total_size進行修改。由于多余的代碼較多，我不會在此粘貼。
def insert_node(node):
global total_size
total_size += 1
if head.next_node is None:
# 此處省略重復(fù)代碼。
在這個方法中，我們使用了一個global total_size，這樣定義的原因是因為如果我們想要在函數(shù)內(nèi)部修改全局變量，就必須這樣寫。希望你能記住這個規(guī)則，不需要太多的解釋。Python沒有像Java那樣的限定符。
def re_index_fin():
# 使用字典模式保存住step與前一個索引的關(guān)系。
temp_size = total_size
dict = {}
dict_list = []
# 這里最主要的是要將字典的key值與節(jié)點做綁定，要不然當設(shè)置索引值時，每個源節(jié)點都不一樣。
while int((temp_size / 2)) > 1:
temp_size = int((temp_size / 2))
key_str = f"step_{temp_size}"
# 我是通過key_str綁定了temp_size步長，這樣當這個步長被減到0時，步長恢復(fù)到舊值時，我能找到之前的元素即可。
dict[key_str] = head.next_node
dict_list.append(temp_size)
# 備份一下，因為在步長減到0時需要恢復(fù)到舊值
backup = list(dict_list)
# 用來遍歷的節(jié)點
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] # 恢復(fù)舊值
# 找到之前的源節(jié)點，我要進行設(shè)置索引節(jié)點了
temp_index = f"step_{backup[i]}"
temp_index_node = dict[temp_index]
temp_index_node.index_node.append(temp)
dict[temp_index] = temp # 更換要設(shè)置的源節(jié)點
temp = temp.next_node
這里有很多循環(huán)，其實我想將步長和節(jié)點綁定到一起，以優(yōu)化性能。如果你愿意，可以嘗試優(yōu)化一下，畢竟這只是跳表的最初版本。讓我們來演示一下，看看優(yōu)化的效果如何。最終結(jié)果如下，其實還是可以的。我大概試了一下，如果數(shù)據(jù)分布不太好的話，很可能需要進行多達6次的查詢才能找到結(jié)果。
文章來源：http://www.zghlxwxcb.cn/news/detail-749534.html
總結(jié)
我們實現(xiàn)的跳表有許多優(yōu)化的方面需要考慮。例如，我們可以避免每次都重新規(guī)劃索引，因為這是不必要的。另外，我們也可以探索不同的步長綁定方法，不一定要按照我目前的方式進行。今天先說到這里，因為我認為跳表的實現(xiàn)邏輯相當復(fù)雜。我們可以在跳表這個領(lǐng)域暫時告一段落。文章來源地址http://www.zghlxwxcb.cn/news/detail-749534.html
到了這里，關(guān)于Java開發(fā)者的Python快速進修指南：實戰(zhàn)之跳表pro版本的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
