程序员经验分享-hwhale

跳过列表——用过它们吗？ [关闭]

2024-02-12

我想知道这里是否有人用过跳过列表 http://en.wikipedia.org/wiki/Skip_list。它看起来具有与平衡二叉树大致相同的优点，但实现起来更简单。如果有，您是自己编写的，还是使用预先编写的库（如果是，它的名称是什么）？


我的理解是，它们并不是一个有用的替代品二叉树（例如红黑树）B-trees用于数据库使用，这样您就可以将级别数保持在可行的最小值，并处理基于 K 的日志而不是基于 2 的日志以获得性能特征。概率跳跃列表的算法（恕我直言）比相应的 B 树算法更容易正确。另外还有一些关于无锁跳过列表的文献。几个月前我考虑过使用它们，但后来放弃了发现它们的努力HDF5 http://en.wikipedia.org/wiki/Hierarchical_Data_Format图书馆。

有关该主题的文献：

比尔·皮尤的论文：

  • 跳过列表食谱 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.524
  • 跳过列表：平衡树的概率替代方案 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.9380
  • 跳跃列表的并发维护 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.8201

非学术论文/教程：

  • 永远困惑 http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_skip.aspx（对几种数据结构有一些讨论）
  • “跳过列表” http://www.csee.umbc.edu/courses/undergraduate/341/fall01/Lectures/SkipLists/skip_lists/skip_lists.html作者：托马斯·A·阿纳斯塔西奥
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

datastructures

binarytree

skiplists

跳过列表——用过它们吗？ [关闭] 的相关文章

  • C# 数组还是字典？

    我想知道 C 数组的访问速度是否恒定 我需要在静态数组中存储 1000 个项目 这些项目将在服务器启动期间初始化 该数组将被只读使用 所以数组不会发生任何变化 我应该使用简单的 C 数组 new MyClass 还是字典 我对 C 非常陌生

  • 在java中的同一个循环中迭代两个hashmap的最佳方法是什么？

    一起迭代下面两个地图的最佳方法是什么 我想比较两个映射值 它们是字符串并且必须获取键和值 HashMap

  • 使用布隆过滤器有什么好处？

    我正在阅读布隆过滤器 它们看起来很愚蠢 使用布隆过滤器可以完成的任何事情 都可以使用单个哈希函数而不是多个哈希函数在更少的空间内更有效地完成 或者看起来就是这样 为什么要使用布隆过滤器以及它有何用处 亚历克斯已经解释得很好了 对于那些还没有

  • 如何正确区分树（即嵌套的字符串列表）？

    我正在使用由嵌套字符串列表组成的数据类型的在线编辑器 请注意 如果每次更改单个值时我都要传输整个结构 那么流量可能会变得难以忍受 所以 为了减少流量 我想到了应用 diff 工具 问题是 如何找到并报告两棵树的差异 例如 ah bh ha

  • 我应该如何存储不同时区事件的数据？

    这是一个概念性问题 因此这里没有代码片段 假设我创建了一个事件数据库 其中一些在纽约 一些在芝加哥 一些在凤凰城 等等 我的服务器的时区设置为纽约 在我看来 为所有这些事件创建 UNIX 时间戳时有两种选择 考虑时区 即 1 月 1 日午夜

  • 理解同构字符串算法

    我理解以下代码来查找字符串是否同构 该代码使用两个哈希值s dict and t dict分别 我假设字符串的长度相同 def isIsomorphic s t s dict t dict for i in range len s if s

  • Delphi是否存在无锁队列“多个生产者-单个消费者”？

    我发现了几个针对单个生产者 单个消费者的实现 但没有找到多个生产者 单个消费者的实现 Delphi是否存在 多个生产者 单个消费者 的无锁队列 无锁队列全线程库 http otl 17slon com支持多个生产者 您可以将它与线程库分开使

  • 使用堆属性按排序顺序打印树 (Cormen)

    我对算法理论 来自 Cormen 感到耳目一新 二进制尝试一章中有一个练习 要求 min heap 属性可以用来打印 n 节点的键吗 树在 O n 时间内排序 展示如何做 或解释为什么不做 我想是的 这是可能的 在最小堆中 节点中的元素小于

  • 将文件保存为 MYSQL 数据库中的 blob 或文件路径

    我知道这些问题是常见问题之一 但我需要您针对具体案例提供帮助 我正在开发一个应用程序 其中一些用户可以添加订单 一些用户可以执行这些订单 这些订单非常具体 因此只有有限数量的用户可以添加它们 然后 为每个订单生成三个文档 每个文档的大小不超

  • 如何定义基于标签的组织结构？

    原标题 有没有办法在基于标签的组织方法上强制建立关系结构 我有一些实体 它们有一系列属性 一些属性影响实体可以具有的其他属性 许多属性被组织成组 并且有时实体被要求具有来自某些组的一定数量的属性 或者可能具有来自某些组的一定范围的属性 有没

  • ConcurrentLinkedDeque 与 LinkedBlockingDeque

    我需要一个线程安全的 LIFO 结构 并发现我可以使用线程安全的实现Deque为了这 Java 7 引入了ConcurrentLinkedDeque http docs oracle com javase 7 docs api java u

  • 为什么 .Net 词典中的条目是按加法顺序排列的？

    我刚刚看到这种行为 我对此感到有点惊讶 如果我向字典中添加 3 或 4 个元素 然后执行 For Each 来获取所有键 它们将以我添加的顺序出现 这让我感到惊讶的原因是字典内部应该是一个哈希表 所以我希望事情能以任何顺序出现 按键的哈希排

  • 二叉堆对于优先级队列的优点？

    看来我错过了一些非常简单的东西 优先级队列的二进制堆与快速排序的值数组相比有什么优势 在这两种情况下 我们将值保存在数组中 插入的时间复杂度为 O logN 删除最大的时间复杂度为 O 1 在这两种情况下 给定元素数组的初始构造都是 O N

  • 如何在 dijkstra 算法中以 O(log n ) 时间更新优先级队列中的键？

    过去一周我一直在研究 dijkstra 算法 我在 java 中有正确的运行代码 它使用数组来计算标准 findMin 函数 该函数为您提供距离最小的顶点 显然它是 O n 现在我希望使用优先级队列 最小堆 来实现它 我的思考过程是 whi

  • 如何从数组表示构建不完全二叉树

    如果输入是一个数组 其中null表示没有节点 input 1 2 3 null 5 null 7 请假设我已经检查过输入 对于每个array i 它的父母array i 2 不会是null 递归地 所以根不能是null 如何构建具有这样的逻

  • 为什么在排序输入上插入到树中比随机输入更快？

    现在我一直听说从随机选择的数据构建二叉搜索树比有序数据更快 这仅仅是因为有序数据需要显式重新平衡以将树高度保持在最低限度 最近我实现了一个不可变的treap http en wikipedia org wiki Treap 一种特殊的二叉搜

  • 从 python 中的缩进文本文件创建树/深度嵌套字典

    基本上 我想迭代一个文件并将每行的内容放入一个深层嵌套的字典中 其结构由每行开头的空格数量定义 本质上 目标是采取这样的事情 a b c d e 并将其变成这样的东西 a b c d e Or this apple colours red

  • 什么时候使用哈希表？

    什么情况下使用哈希表可以提高性能 什么情况下不能 哪些情况不适合使用哈希表 什么情况下使用哈希表可以提高性能 什么情况下不能 如果您有理由关心 请使用哈希表和您正在考虑的其他任何内容来实现 将您的实际数据放入其中 并衡量哪个性能更好 也就是

  • 从日志文件中获取前 100 个 URL

    我的一位朋友在接受采访时被问到以下问题 谁能告诉我如何解决它 我们有一个相当大的日志文件 大约 5GB 日志文件的每一行都包含一个用户在我们网站上访问过的 URL 我们想要找出用户访问最多的 100 个 URL 怎么做 如果我们有超过 10

  • 生成二叉树的所有从根到叶的分支

    抱歉 如果这是一个常见问题 但我还没有找到适合我的特定问题的答案 我正在尝试实施一个walk方法将二叉树从根节点遍历到每个叶节点 每当到达叶节点时都会生成根到叶路径 例如 遍历表示为的二叉树 a b d c 会产生 a b c a d 我的

随机推荐

  • Android Lollipop 问题 - 无法将图像从相机加载到 ImageView

    在 android lollipop 之前的任何版本上 下面的代码都可以正常工作 由于某种原因 从 Android 的某个版本 大约 5 0 开始 每当从相机捕获图像时 屏幕都会向右和向后旋转 90 度 不仅我的设备上的自动旋转关闭 我的活

  • Eclipse 插件：将 Launch 命令组添加到 Custom Perspective

    我在网上查找了很多教程 但很难找到与 Launches 相关的任何内容 我正在实现一个 IDE 插件 该插件实现了自定义透视图 但除了 运行最后一个工具 按钮之外 我看不到任何 运行 或 调试 工具栏按钮 每次启动透视图时 我都需要进入 自

  • 在 MEF 中组合零件后自动调用方法

    有没有办法指定在组成部分后自动调用方法 该方法可以在组合部分或进行组合的类中调用 是的 如果你的类实现了IPartImports满意通知 http msdn microsoft com en us library system compon

  • 有没有适用于 Android 的照片库？ [关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 由于Android中的内置照片库小部件不够好 很容易崩溃 我正在寻找第3方照片库库 如果您有好的选择请

  • 使用下拉菜单填充表单 - Access

    我正在尝试在访问中创建一个表单 该表单在顶部有一个下拉菜单 并将使用与所选内容相对应的记录填充表单的其余部分 我在网上查看了 2 个不同的指南 但都指向旧版本的 Access 我认为我遗漏了一些东西 所以 我做所有事情的顺序 我走到桌边拿表

  • Web Api 属性路由中的可选参数

    我想处理以下 API 调用的 POST v1 location deviceid appid 附加参数来自 Post Body 这一切对我来说都很好 现在我想通过允许 设备 id 和 或 应用程序 id 和 或正文数据为空来扩展我的代码 v

  • 需要获取文本文件中匹配字符串的行号

    我需要使用 PHP 获取文本文件的行号 我需要的线路是 想要这条线路 我尝试使用 file 将文件行放入数组中并使用 array search 进行搜索 但它不会返回行号 在此示例中 我需要返回 3 作为行号 file file file

  • PrimeFaces commandButton actionListener 未触发

    我无法获取我的actionListener in a

  • 如何从本地存储获取文件（pdf、jpg、docs）并创建文件[重复]

    这个问题在这里已经有答案了 我尝试使用意图数据 uri 创建文件 要创建文件 我开始这样的意图 val intent Intent Intent ACTION GET CONTENT apply addCategory Intent CAT

  • 使用程序检查已安装的软件

    我们需要创建一个程序 实际上我们被要求创建一个软件许可合规工具 我们如何检查机器内安装的软件 是通过注册表吗 在搜索时我看到一篇文章说我们需要研究 HKLM 的 卸载 子项 另外 我们是否还可以获得有关软件是否是免费软件 共享软件 从注册表

  • js中如何将数据更新到文件中的特定位置

    我有一个包含数据的文件如下 Test txt

  • 在 UWP 和 ASPNETCORE 应用程序上使用哪些类库作为参考

    我想创建一个可在我的 aspnetcore 应用程序和 uwp 应用程序上使用的类库 如果我错了 请纠正我 按照我理解下图 第一张图 的方式 我可以创建一个 net core 类库并让它引用 uwp 和 aspnetcore 我所做的是我创

  • 如何在 Intellij IDEA 参数中使用通配符

    我使用尝试在运行配置中添加参数 I add master sequential pg txt 但当我开始跑步时 错误就出来了 usr local go bin go run home asus dev 6 824 src main wc g

  • 在 git 中将文件夹部署到分支的最简单方法是什么？

    我的文件夹里有一个master分支命名public 将其内容复制到不同分支的根目录的最简单方法是什么 例如gh pages 一个非常好的技巧如图所示在子模块中生成 GitHub 页面 http blog blindgaenger net g

  • 仅电子邮件应用程序可解析 Intent

    我有一个问题 我只想通过电子邮件活动来解决意图 ACTION SEND 但除了电子邮件之外 我还得到其他应用程序 例如 TubeMate 即使我已将 mime 类型设置为 message rfc822 知道如何我可以获取电子邮件应用程序来解

  • JobControl 和 JofConf.setMapperClass() 错误

    我正在尝试使用JobControl将多个Mappers和Reducers连接在一起但调用时遇到以下错误JobConf setMapperClass setMapperClass java lang Class

  • 指向成员函数的指针错误[关闭]

    Closed 这个问题需要调试细节 help minimal reproducible example 目前不接受答案 当我编译以下代码时 出现以下错误 谁能帮我解决这个问题 谢谢 错误 ISO C 禁止使用绑定成员函数的地址来形成指向成员

  • 如何在 Java 或其他平台中创建 logrotate 友好的文件编写器？

    在 Java 中实现与以下兼容的文件编写器 记录器的最佳实践是什么对数旋转 http linux die net man 8 logrotate 目标是允许 logrotate 用于所有日志管理 而不是使用日志记录 API Log4J 等

  • 如何限制JComboBox中的可编辑文本？

    我的 jcombobox 中已经有这个 myjcombobox getEditor getEditorComponent addKeyListener new KeyAdapter Override public void keyTyped

  • 跳过列表——用过它们吗？ [关闭]

    Closed 这个问题是基于意见的 help closed questions 目前不接受答案 我想知道这里是否有人用过跳过列表 http en wikipedia org wiki Skip list 它看起来具有与平衡二叉树大致相同的优

热门标签