翼度科技»论坛 编程开发 python 查看内容

Java开发者的Python快速进修指南:实战之跳表pro版本

11

主题

11

帖子

33

积分

新手上路

Rank: 1

积分
33
之前我们讲解了简易版的跳表,我希望你能亲自动手实现一个更完善的跳表,同时也可以尝试实现其他数据结构,例如动态数组或哈希表等。通过实践,我们能够发现自己在哪些方面还有所欠缺。这些方法只有在熟练掌握之后才会真正理解,就像我在编写代码的过程中,难免会忘记一些方法或如何声明属性等等。
我不太愿意写一些业务逻辑,例如典型的购物车逻辑,因为这对个人的成长没有太大帮助,反而可能使我们陷入业务误区。但是,数据结构与算法则不同。好了,言归正传,现在我们来看看如何对之前的简易版跳表进行优化。
关于跳表的解释我就不再赘述了。在上一篇中,我们只定义了一个固定步长为2的跳表,使节点可以进行跳跃查询,而不是遍历节点查询。然而,真正的跳表有许多跳跃步长的选择,并不仅限于单一的步长。因此,今天我们将实现多个跳跃步长的功能,先从简单的开始练习,例如增加一个固定的跳跃步长4。
如果一个节点具有多个跳跃步长,我们就不能直接用单独的索引节点来表示了,而是需要使用列表来存储。否则,我们将不得不为每个步长定义一个索引节点。因此,我修改了节点的数据结构如下:
  1. class SkipNode:
  2.     def __init__(self,value,before_node=None,next_node=None,index_node=None):
  3.         self.value = value
  4.         self.before_node = before_node
  5.         self.next_node = next_node
  6.         # 这是一个三元表达式
  7.         self.index_node = index_node if index_node is not None else []
复制代码
在这个优化过程中,我们使用了一个三元表达式。在Python中,没有像Java语言中的三元运算符(?:)那样的写法。不过,我们可以换一种写法:[值1] if [条件] else [值2],这与 [条件] ? [值1] : [值2] 是等价的。
我们不需要对插入数据的逻辑实现进行修改。唯一的区别在于我们将重新建立索引的方法名更改为re_index_pro。为了节省大家查阅历史文章的时间,我也直接将方法贴在下面。
  1. def insert_node(node):
  2.     if head.next_node is None:
  3.         head.next_node = node
  4.         node.next_node = tail
  5.         node.before_node = head
  6.         tail.before_node = node
  7.         return
  8.     temp = head.next_node
  9.     # 当遍历到尾节点时,需要直接插入
  10.     while temp.next_node is not None or temp == tail:
  11.         if temp.value > node.value or temp == tail:
  12.             before = temp.before_node
  13.             before.next_node = node
  14.             temp.before_node = node
  15.             node.before_node = before
  16.             node.next_node = temp
  17.             break
  18.         temp = temp.next_node
  19.     re_index_pro()
复制代码
为了提高性能,我们需要对索引进行升级和重新规划。具体操作包括删除之前已规划的索引,并新增索引步长为2和4。
  1. def re_index_pro():
  2.     step = 2
  3.     second_step = 4
  4.     # 用来建立步长为2的索引的节点
  5.     index_temp_for_one = head.next_node
  6.     # 用来建立步长为4的索引的节点
  7.     index_temp_for_second = head.next_node
  8.     # 用来遍历的节点
  9.     temp = head.next_node
  10.     while temp.next_node is not None:
  11.         temp.index_node = []
  12.         if step == 0:
  13.             step = 2
  14.             index_temp_for_one.index_node.append(temp)
  15.             index_temp_for_one = temp
  16.         if second_step == 0:
  17.             second_step = 4
  18.             index_temp_for_second.index_node.append(temp)
  19.             index_temp_for_second = temp
  20.         temp = temp.next_node
  21.         step -= 1
  22.         second_step -= 1
复制代码
我们需要对查询方法进行优化,虽然不需要做大的改动,但由于我们的索引节点已更改为列表存储,因此需要从列表中获取值,而不仅仅是从节点获取。在从列表中获取值的过程中,你会发现列表可能有多个节点,但我们肯定先要获取最大步长的节点。如果确定步长太大,我们可以缩小步长,如果仍然无法满足要求,则需要遍历节点。
  1. def search_node(value):
  2.     temp = head.next_node
  3.     # 由于我们有了多个索引节点,所以我们需要知道跨步是否长了,如果长了需要缩短步长,也就是寻找低索引的节点。index_node[1] --> index_node[0]
  4.     step = 0
  5.     while temp.next_node is not None:
  6.         step += 1
  7.         if value == temp.value:
  8.             print(f"该值已找到,经历了{step}次查询")
  9.             return
  10.         elif value < temp.value:
  11.             print(f"该值在列表不存在,经历了{step}次查询")
  12.             return
  13.                 if temp.index_node:
  14.             for index in range(len(temp.index_node) - 1, -1, -1):
  15.                 if value > temp.index_node[index].value:
  16.                     temp = temp.index_node[index]
  17.                     break
  18.             else:
  19.                 temp = temp.next_node
  20.         else:
  21.             temp = temp.next_node
  22.     print(f"该值在列表不存在,经历了{step}次查询")
复制代码
为了使大家更容易查看数据和索引的情况,我对节点遍历的方法进行了修改,具体如下所示:
  1. def print_node():
  2.     my_list = []
  3.     temp = head.next_node
  4.     while temp.next_node is not None:
  5.         if temp.index_node:
  6.             my_dict = {"current_value": temp.value, "index_value": [node.value for node in temp.index_node]}
  7.         else:
  8.             my_dict = {"current_value": temp.value, "index_value": temp.index_node}  # 设置一个默认值为None
  9.         my_list.append(my_dict)
  10.         temp = temp.next_node
  11.     for item in my_list:
  12.         print(item)
复制代码
为了进一步优化查询结果,我们可以简单地运行一下,通过图片来观察优化的效果。从结果可以看出,我们确实减少了两次查询的结果,这是一个很好的进展。然而,实际的跳表结构肯定比我简化的要复杂得多。例如,步长可能不是固定的,因此我们需要进一步优化。
由于我们已经将索引节点改为列表存储,所以我们能够进行一些较大的修改的地方就是重建索引的方法。

为了实现动态设置步长,我需要获取当前列表的长度。为此,我在文件中定义了一个名为total_size的变量,并将其初始值设置为0。在插入操作时,我会相应地对total_size进行修改。由于多余的代码较多,我不会在此粘贴。
  1. def insert_node(node):
  2.     global total_size
  3.     total_size += 1
  4.     if head.next_node is None:
  5.     # 此处省略重复代码。
复制代码
在这个方法中,我们使用了一个global total_size,这样定义的原因是因为如果我们想要在函数内部修改全局变量,就必须这样写。希望你能记住这个规则,不需要太多的解释。Python没有像Java那样的限定符。
  1. def re_index_fin():
  2.     # 使用字典模式保存住step与前一个索引的关系。
  3.     temp_size = total_size
  4.     dict = {}
  5.     dict_list = []
  6.     # 这里最主要的是要将字典的key值与节点做绑定,要不然当设置索引值时,每个源节点都不一样。
  7.     while int((temp_size / 2)) > 1:
  8.         temp_size = int((temp_size / 2))
  9.         key_str = f"step_{temp_size}"
  10.         # 我是通过key_str绑定了temp_size步长,这样当这个步长被减到0时,步长恢复到旧值时,我能找到之前的元素即可。
  11.         dict[key_str] = head.next_node
  12.         dict_list.append(temp_size)
  13.     # 备份一下,因为在步长减到0时需要恢复到旧值
  14.     backup = list(dict_list)
  15.     # 用来遍历的节点
  16.     temp = head.next_node
  17.     while temp.next_node is not None:
  18.         temp.index_node = []
  19.         # 直接遍历有几个步长
  20.         for i in range(len(dict_list)):
  21.             dict_list[i] -= 1  # 每个元素减一
  22.             if dict_list[i] == 0:
  23.                 dict_list[i] = backup[i]  # 恢复旧值
  24.                 # 找到之前的源节点,我要进行设置索引节点了
  25.                 temp_index = f"step_{backup[i]}"
  26.                 temp_index_node = dict[temp_index]
  27.                 temp_index_node.index_node.append(temp)
  28.                 dict[temp_index] = temp  # 更换要设置的源节点
  29.         temp = temp.next_node
复制代码
这里有很多循环,其实我想将步长和节点绑定到一起,以优化性能。如果你愿意,可以尝试优化一下,毕竟这只是跳表的最初版本。让我们来演示一下,看看优化的效果如何。最终结果如下,其实还是可以的。我大概试了一下,如果数据分布不太好的话,很可能需要进行多达6次的查询才能找到结果。

总结

我们实现的跳表有许多优化的方面需要考虑。例如,我们可以避免每次都重新规划索引,因为这是不必要的。另外,我们也可以探索不同的步长绑定方法,不一定要按照我目前的方式进行。今天先说到这里,因为我认为跳表的实现逻辑相当复杂。我们可以在跳表这个领域暂时告一段落。

来源:https://www.cnblogs.com/guoxiaoyu/p/17860575.html
免责声明:由于采集信息均来自互联网,如果侵犯了您的权益,请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x

举报 回复 使用道具