之前我们讲解了简易版的跳表，我希望你能亲自动手实现一个更完善的跳表，同时也可以尝试实现其他数据结构，例如动态数组或哈希表等。通过实践，我们能够发现自己在哪些方面还有所欠缺。这些方法只有在熟练掌握之后才会真正理解，就像我在编写代码的过程中，难免会忘记一些方法或如何声明属性等等。
我不太愿意写一些业务逻辑，例如典型的购物车逻辑，因为这对个人的成长没有太大帮助，反而可能使我们陷入业务误区。但是，数据结构与算法则不同。好了，言归正传，现在我们来看看如何对之前的简易版跳表进行优化。
关于跳表的解释我就不再赘述了。在上一篇中，我们只定义了一个固定步长为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.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次的查询才能找到结果。
总结
我们实现的跳表有许多优化的方面需要考虑。例如，我们可以避免每次都重新规划索引，因为这是不必要的。另外，我们也可以探索不同的步长绑定方法，不一定要按照我目前的方式进行。今天先说到这里，因为我认为跳表的实现逻辑相当复杂。我们可以在跳表这个领域暂时告一段落。