如何在Python中实现一个支持范围查询的跳跃表?

风明大大_6759

风明大大_6759

2026-11-21

556人浏览

原创

跳表适用于动态高频增删且需O(log n)范围查询的场景,因bisect+list插入删除为O(n),而跳表平均O(log n)且天然支持正向范围遍历;其节点需为每层维护独立前向指针,底层覆盖全量数据,范围查询从最高层定位left前驱后沿level 0遍历收集。

如何在python中实现一个支持范围查询的跳跃表?

为什么不用 bisect 而要手写跳跃表?

当你需要在动态插入/删除频繁、同时又要求 O(log n) 范围查询(比如 [left, right] 内所有元素)的场景下,bisect + list 就不适用了——每次插入删除都是 O(n)。跳跃表能兼顾平均 O(log n) 的增删查,且天然支持正向遍历范围结果,比平衡树(如 sortedcontainers)更易理解、无第三方依赖。

跳跃表节点怎么设计才支持范围遍历?

关键不是只存 next 指针,而要为每一层维护独立的前向指针链,并让底层(level 0)完整覆盖所有数据节点。每个节点必须带值和层数,且 level 数组长度即为其高度。范围查询时,从最高层快速定位 left 的前驱,再沿 level 0 向右收集直到超过 right。

容易踩的坑:

  • find_predecessor(left) 必须返回严格 left 的最大节点,不能返回等于 left 的节点——否则可能漏掉左边界
  • 层级随机生成要用 random.random() ,别用 randint(1, max_level),否则概率分布不满足指数衰减,退化成链表
  • 所有 level 的指针更新必须原子完成:先建好新节点所有层指针,再用 CAS 或全局锁串行化(单线程可忽略,但逻辑要预留)

范围查询函数 range_query(left, right) 怎么写?

核心是复用查找逻辑:先跳到 left 的前驱,然后从它的 level 0 next 开始,一路 next 直到节点值 > right。注意边界包含性——[left, right] 要检查当前节点值是否 ≥ left 且 ≤ right。

示例片段(简化版):

def range_query(self, left, right):
    res = []
    # 找到最接近 left 且 = left:
            res.append(curr.value)
        curr = curr.forward[0]
    return res

性能提示:不要在循环里反复调用 _find_predecessor;也不要把所有节点先取出再过滤——那会破坏 O(k + log n) 的复杂度(k 是结果数量)。

使用 Claude Agent SDK 将绑定的 Claude 代码会话嵌入到 Python 自动化中
使用 Claude Agent SDK 将绑定的 Claude 代码会话嵌入到 Python 自动化中

当现有的脚本或服务需要将作用域化的仓库工作委托给 Claude Code 并以编程方式消费结构化响应时,请使用 Claude Agent SDK for Python。

下载

Python 实现里哪些细节会让范围查询变慢或出错?

最容易被忽略的是内存模型和比较稳定性。Python 中如果节点值是自定义对象,__lt__ 必须严格全序,否则 while curr.value 可能无限循环或跳过节点。另外,None 哨兵节点的比较要显式处理,比如:

if curr is None or curr.value > right: 比 curr.value > right 更安全

还有两个硬伤点:

  • Python 的 GIL 让多线程并发更新跳跃表几乎没收益,真要高并发请直接上 redis.ZRANGEBYSCORE
  • 没有垃圾回收感知——大量删除后,高层指针残留空洞,虽不影响正确性,但会轻微拖慢查找;定期 rebuild 或加惰性标记可缓解

真正用起来,你会发现:写对 _find_predecessor 和管住 None 边界,就解决了 90% 的 bug。

Python免费学习笔记(深入):立即使用
在学习笔记中,你将探索 Python 的核心概念和高级技巧!

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

python

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
python打包成可执行文件
python打包成可执行文件

本专题为大家带来python打包成可执行文件相关的文章,大家可以免费的下载体验。

2023.07.20

1971

4

python能做什么
python能做什么

python能做的有:可用于开发基于控制台的应用程序、多媒体部分开发、用于开发基于Web的应用程序、使用python处理数据、系统编程等等。本专题为大家提供python相关的各种文章、以及下载和课程。

2023.07.25

5624

7

format在python中的用法
format在python中的用法

Python中的format是一种字符串格式化方法,用于将变量或值插入到字符串中的占位符位置。通过format方法,我们可以动态地构建字符串,使其包含不同值。php中文网给大家带来了相关的教程以及文章,欢迎大家前来阅读学习。

2023.07.31

1909

3

python教程
python教程

Python已成为一门网红语言,即使是在非编程开发者当中,也掀起了一股学习的热潮。本专题为大家带来python教程的相关文章,大家可以免费体验学习。

2023.08.03

34537

23

python环境变量的配置
python环境变量的配置

Python是一种流行的编程语言,被广泛用于软件开发、数据分析和科学计算等领域。在安装Python之后,我们需要配置环境变量,以便在任何位置都能够访问Python的可执行文件。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

2023.08.04

4027

5

python eval
python eval

eval函数是Python中一个非常强大的函数,它可以将字符串作为Python代码进行执行,实现动态编程的效果。然而,由于其潜在的安全风险和性能问题,需要谨慎使用。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

2023.08.04

4027

5

scratch和python区别
scratch和python区别

scratch和python的区别:1、scratch是一种专为初学者设计的图形化编程语言,python是一种文本编程语言;2、scratch使用的是基于积木的编程语法,python采用更加传统的文本编程语法等等。本专题为大家提供scratch和python相关的文章、下载、课程内容,供大家免费下载体验。

2023.08.11

1303

5

python合并两个列表
python合并两个列表

Python是一种强大的编程语言,具有许多方便的功能和工具。在Python中,有多种方法可以合并两个列表。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

2023.08.10

636

4

python是前端还是后端
python是前端还是后端

Python属于前端也属于后端,其灵活性和丰富的生态系统使得开发人员能够在不同的领域中灵活运用。本专题为大家提供python相关的文章、下载、课程内容,供大家免费下载体验。

2023.08.11

3143

5

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程