浅谈“跳跃表”的相关操作及其应用

《浅谈“跳跃表”的相关操作及其应用》由会员分享，可在线阅读，更多相关《浅谈“跳跃表”的相关操作及其应用（15页珍藏版）》请在装配图网上搜索。

1、让 算 法 的 效 率 “ 跳 起 来” ！ 浅 谈 “ 跳 跃 表 ” 的 相 关 操 作 及 其 应 用 “跳 跃 表 ” 新 生 的 宠 儿 跳 跃 表 （ Skip List） 是 1987年 才 诞 生 的 一 种 崭新 的 数 据 结 构 ， 它 在 进 行 查 找 、 插 入 、 删 除等 操 作 时 的 时 间 复 杂 度 均 为 O(logn),有 着 近乎 替 代 平 衡 树 的 本 领 。 而 且 最 重 要 的 一 点 ，就 是 它 的 编 程 复 杂 度 较 同 类 的 AVL树 ， 红 黑树 等 要 低 得 多 ， 这 使 得 其 无 论 是 在 理 解 还 是在

2、推 广 性 上 ， 都 有 着 十 分 明 显 的 优 势 。 “跳 跃 表 ” 的 结 构 跳 跃 表 由 多 条 链 构 成 （ S0， S1， S2 ， Sh） ， 且 满 足 如 下 三 个 条 件 ： 每 条 链 必 须 包 含 两 个 特 殊 元 素 ： + 和 - S0包 含 所 有 的 元 素 ， 并 且 所 有 链 中 的 元 素 按 照 升 序 排 列 。 每 条 链 中 的 元 素 集 合 必 须 包 含 于 序 数 较 小 的 链 的 元 素 集 合 ， 即 ：hSSSS .210hSSSS .210 53 53 53 45 45 37 30 30 30 29 15 1

3、1 11 11 11 - - - - + + + + S0 S1 S2 S3 跳跃表的实例 “跳 跃 表 ” 的 时 空 效 率 空 间 复 杂 度 ： O(n) （ 期 望 ） 跳 跃 表 高 度 ： O(logn) （ 期 望 ）相 关 操 作 的 时 间 复 杂 度 ： 查 找 ： O(logn) （ 期 望 ） 插 入 ： O(logn) （ 期 望 ） 删 除 ： O(logn) （ 期 望 ） 基 本 操 作 一 查 找目 的 ： 在 跳 跃 表 中 查 找 一 个 元 素 x在 跳 跃 表 中 查 找 一 个 元 素 x， 按 照 如 下 几 个 步 骤 进 行 ： 从 最 上

4、层 的 链 （ Sh） 的 开 头 开 始 假 设 当 前 位 置 为 p， 它 向 右 指 向 的 节 点 为 q（ p与 q不 一 定 相 邻 ） ， 且q的 值 为 y。 将 y与 x作 比 较l x=y 输 出 查 询 成 功 ， 输 出 相 关 信 息l xy 从 p向 右 移 动 到 q的 位 置l xy 从 p向 下 移 动 一 格I. 如 果 当 前 位 置 在 最 底 层 的 链 中 （ S 0） ， 且 还 要 往 下 移 动 的 话 ， 则 输出 查 询 失 败 53 53 53 45 45 37 30 30 30 29 15 11 11 11 11 - - - - +

5、+ + + 查询元素53的全过程S0 S1 S2 S3 查 找 成 功 ！ 基 本 操 作 二 插 入目 的 ： 在 跳 跃 表 中 插 入 一 个 元 素 x 插 入 操 作 由 两 部 分 组 成 ：查 找 插 入 的 位 置 和 插 入 对 应 元 素 。为 了 确 定 插 入 的 “ 列 高 ” ， 我 们 引 入 一 个 随 机 决 策 模 块 ： 产 生 一 个 0到 1的 随 机 数 r r random() 如 果 r小 于 一 个 概 率 因 子 P， 则 执 行 方 案 A， if rp then do A 否 则 ， 执 行 方 案 B else do B列 的 初 始

6、高 度 为 1。 插 入 元 素 时 ， 不 停 地 执 行随 机 决 策 模 块 。 如 果 要 求 执 行 的 是 A操 作 ， 则 将 列的 高 度 加 1， 并 且 继 续 反 复 执 行 随 机 决 策 模 块 。 直 到 第 i次 ， 模 块 要 求 执 行 的 是 B操 作 ， 我 们 结 束 决 策 ，并 向 跳 跃 表 中 插 入 一 个 高 度 为 i的 列 。 基 本 操 作 二 插 入 假 设 我 们 现 在 要 插 入 一 个 元 素 40到 已 有 的跳 跃 表 中 。 37 30 30 30 29 15 - - - - S0 S1 S2 S3 插入的位置53 53

7、 53 45 45 + + + + 40 40 4040 高 度 +1随 机 化 模 块 运 行 状 况 ： 高 度 =4高 度 +1 高 度 +1 结 束53 - - - - S0 S1 S2 S3 基 本 操 作 三 删 除目 的 ： 从 跳 跃 表 中 删 除 一 个 元 素 x 删 除 操 作 分 为 以 下 三 个 步 骤 ： 在 跳 跃 表 中 查 找 到 这 个 元 素 的 位 置 ， 如 果 未 找 到 ， 则 退 出 将 该 元 素 所 在 整 列 从 表 中 删 除1. 将 多 余 的 “ 空 链 ” 删 除 11 11 11 11 53 53 53 45 45 37 30

8、 30 30 29 15 + + + + 53 53 53 45 45 37 30 30 30 29 15 - - - + + + S0 S1 S2 概 率 因 子 P 对 跳 跃 表 的 影 响 在 插 入 操 作 中 ， 我 们 引 入 了 一 个 概 率 因 子 P， 它 决 定 了 跳 跃 表 的 高 度 ，并 影 响 到 了 整 个 数 据 结 构 的 效 率 。 让 我 们 来 看 看 在 实 际 评 测 过 程 中 ， 不 同 的 P在 时 空 效 率 上 的 差 异 。P 平 均 操 作 时 间 平 均 列 高 总 结 点 数 每 次 查 找 跳 跃次 数 （ 平 均 值 ）

9、每 次 插 入 跳 跃次 数 （ 平 均 值 ） 每 次 删 除 跳 跃次 数 （ 平 均 值 ） 2/3 0.0024690 ms 3.004 91233 39.878 41.604 41.5661/2 0.0020180 ms 1.995 60683 27.807 29.947 29.0721/e 0.0019870 ms 1.584 47570 27.332 28.238 28.4521/4 0.0021720 ms 1.330 40478 28.726 29.472 29.6641/8 0.0026880 ms 1.144 34420 35.147 35.821 36.007 跳 跃

10、表 的 应 用 高 效 率 的 相 关 操 作 和 较 低 的 编 程 复 杂 度 使 得 跳 跃 表 在 实 际应 用 中 的 范 围 十 分 广 泛 。 尤 其 在 那 些 编 程 时 间 特 别 紧 张 的情 况 下 ， 高 性 价 比 的 跳 跃 表 很 可 能 会 成 为 你 的 得 力 助 手 。您 正 为 找 不 到 合 适 的 数 据 结 构 而 感 到 烦 恼 吗 ？您 正 为 自 己 编 写 程 序 的 效 率 高 低 而 感 到 担 忧 吗 ？您 正 为 陷 入 R-B tree的 深 渊 又 无 法 自 拔 而 感 到 苦 闷 吗 ？朋 友 ！试 试 跳 跃 表 吧 ！

11、它 将 给 您 的 编 程 带 来 超 高 的 效 率 与 无 尽 的 快 乐 ！ 机 不 可 失 ， 时 不 再 来 ！详 情 请 致 电 ： 1381xxxxxxx 跳 跃 表 的 应 用 NOI2004 Day1 郁 闷 的 出 纳 员 （ Cashier） 抽 象 题 意 ：要 求 维 护 这 样 一 个 数 据 结 构 ， 使 得 它 支 持 以 下 四 种 操 作 ： I(x) 插 入 一 个 值 为 x 元 素 A(x) 现 有 全 体 元 素 加 上 一 个 值 x S(x) 现 有 全 体 元 素 减 去 一 个 值 x F(i) 查 找 现 有 元 素 中 第 i 大 的

12、元 素 值（ x为 10 5级 别 ）同 时 还 要 保 持 这 样 一 个 性 质 ：现 有 的 元 素 必 须 都 大 于 一 个 特 定 的 值 min， 小 于 min的 要 删 去 。 我 们 利 用 一 个 虚 拟 的 “ 零 线 ” 来 表 示 0在 数 据 结 构 中 的 相 对 位 置 。 这 样 在进 行 A和 S操 作 的 时 候 ， 只 要 对 “ 零 线 ” 进 行 调 整 即 可 ， 并 不 需 要 对 所 有 元素 的 值 做 全 面 的 修 改 。 而 在 做 S操 作 时 ， 为 了 维 持 题 意 中 的 性 质 ， 要 注 意 将值 低 于 （ “ 零 线

13、 ” +min） 的 元 素 删 除 。 支 持 这 些 操 作 的 数 据 结 构 有 很 多 ， 比 如 说 线 段 树 ， 伸 展 树 ， 跳 跃 表 等 。 跳 跃 表 的 应 用 NOI2004 Day1 郁 闷 的 出 纳 员 （ Cashier）评 测 结 果 ： （ 单 位 ： 秒 ） Test1 Test2 Test3 Test4 Test5 Test6 Test7 Test8 Test9 Test10线 段 树 0.000 0.000 0.000 0.031 0.062 0.094 0.109 0.203 0.265 0.250伸 展 树 0.000 0.000 0.016

14、 0.062 0.047 0.125 0.141 0.360 0.453 0.422跳 跃 表 0.000 0.000 0.000 0.047 0.062 0.109 0.156 0.368 0.438 0.375I命 令 时 间复 杂 度 A命 令 时 间复 杂 度 S命 令 时 间复 杂 度 F命 令 时 间复 杂 度 线 段 树 O(logR) O(1) O(logR) O(logR) 伸 展 树 O(logN) O(1) O(logN) O(logN) 跳 跃 表 O(logN) O(1) O(logN) O(logN) 空 间 复 杂 度 O（ n） 摆 脱 实 数 的 约 束 极

15、小 的 编 程 复 杂 度 能 够 使 你 很 短 的 内 解 决 此 题 ！跳 跃 表 的 应 用 HNOI2004 Day1 宠 物 收 养 所 （ Pet） 抽 象 题 意 ： 维 护 一 个 数 据 结 构 ， 使 得 它 支 持 以 下 两 种 操 作 ： 插 入 一 个 元 素 x (0 x231) 给 定 一 个 元 素 y， 删 除 现 有 与 y差 值 最 小 的 元 素 x （ |x-y|为 最 小 ） 所 有 操 作 次 数 不 超 过 80000思 考 . 线 段 树 ? 如 果 采 取 边 做 边 开 空 间 的 策 略 ， 勉 强 可 以 缓 解 内 存 的 压力

16、。 但 此 题 对 内 存 的 要 求 很 苛 刻 ， 元 素 相 对 范 围 来 说 也 比较 少 ， 如 果 插 入 的 元 素 稍 微 分 散 一 些 ， 就 很 有 可 能 使 得 空间 复 杂 度 接 近 O（ nlogR） ！何 况 如 果 拓 展 一 下 ， 插 入 的 元 素 不 是 整 数 而 是 实 数 呢 ？跳 跃 表 ！ 好 ! 总 结 跳 跃 表 作 为 一 种 新 兴 的 数 据 结 构 ， 以 相 当 高的 效 率 和 较 低 的 复 杂 度 散 发 着 其 独 特 的 光 芒。 和 同 样 以 编 程 复 杂 度 低 而 闻 名 的 “ 伸 展 树” 相 比 ， 跳 跃 表 的 效 率 不 但 不 会 比 它 差 ， 甚至 优 于 前 者 。“跳 跃 表 ” 这 个 名 字 有 着 其 深 远 的 意 义 ！ 谢 谢 大 家Thank you