问题标签 [skip-lists]

我正在寻找一种方法来在跳过列表中找到给定的元素 x，它是列表中的第 k 个（在它之前有 k-1 个元素）。算法的预期时间应该是 O(log K)

我找到了采用 O(log n) 的已知算法，但这里是 O(log K)。

提前谢谢你

我如何证明这一点，节点的跳过列表变体通过投掷六面来决定它们的高度（如果骰子取值 2 到 6 中的任何一个，则节点将自身提升到下一个级别。节点最终确定其级别当掷骰子为 1 时。），如果有 n 个节点，则列表的数量至少为 O ( 1 − 1/nlog c*lognn )c>= 1 - 1/n

我正在尝试使用泛型实现 SkipList，但遇到了问题。我似乎无法实例化节点。

节点类：

列表类：

错误出现在p1 = new SkipNode<E>(SkipNode.negInf, null);我尝试删除该<E>行并将其更改为 this: p1 = new SkipNode(SkipNode<E>.negInf, null);，这没有多大意义，但我想我会尝试一下。我也尝试在参数中执行“-oo”，但它希望我将节点构造函数参数更改为字符串和整数。

我究竟做错了什么？

I am trying to make a SkipList and I have a method that takes a generic data type:

Which takes you here:

The problem is on the compareTo() method. It says the compareTo() method is undefined for type E. In Eclipse it wants me to add two typecasts like this:

((String) p.getRight().getKey().compareTo((String) key) <= 0 )

Why does it want String? The data type could be anything. I tried doing typecast of E instead but Eclipse wants to change it back to String. Any help would be appreciated.

当我运行上述代码时，插入的第一个元素（在本例 3 中）始终是列表中的最后一个元素。其他所有元素都以正确的顺序插入。上述程序显示 2-39-50-500-2000-3。我可以再插入 100 个值，它们都会插入正确的位置，除了插入的第一个元素总是最后一个，无论我是否放置更大的值。

我不能完全把手指放在它上面，但显然它在放置插入时忽略了列表的最后一个元素。感谢是否有人可以对此有所了解。谢谢！

我正在尝试使用最小的额外内存开销来实现一个性能与 BST 一样好的跳过列表，目前即使不考虑任何内存限制，我的 SkipList 实现的性能甚至与非常幼稚的平衡 BST 实现相距甚远 -可以这么说，手工制作的 BTS :) -

作为参考，我使用了 William Pugh PUG89的原始论文和我在 Sedgewick -13.5- 的 C 算法中找到的实现。我的代码是递归实现，下面是插入和查找操作的线索：

这是查找操作的代码：

sl_node -skip list node- 看起来像这样：

正如你所看到的，与本书的实现相比，这个实现没有什么特别或先进的，我不会分享平衡的 BTS 代码，因为我认为这里不需要，但它是一个非常基本的 BTS，在当新节点高度大于 16*lg(n) 时插入，其中 n 是节点数。

可以这么说，只有当最大高度比最佳理论高度高 16 倍时，我才重新平衡这三个，正如我所说，这个简单的自制 BST 比自制的跳过列表要好得多。

但首先，让我们看一些数据，使用 p=.5 和 n=262144 时，SkipList 中节点的级别具有以下分布：

这几乎完美 - 哦，这是一个大问题！ - 符合文章中的理论，即：50% 级别 1，25% 级别 2 等等。输入数据来自我最好的可用伪随机数生成器，即 std::random_device 和 std::default_random_engine 和统一的 int 分布。输入对我来说看起来很随机:)！

在我的机器上搜索“所有”SkipList 中的“所有”262144 个元素所需的时间（以随机顺序）为 315 毫秒，而对于幼稚 BTS 上的相同搜索操作，所需时间为 134 毫秒，因此 BTS 几乎比跳过列表。这并不是我对“跳过列表算法与平衡树具有相同的渐近预期时间界限并且简单、快速且使用更少空间” PUG89 所期望的。

SkipList 节点“插入”所需的时间为 387 毫秒，BTS 为 143 毫秒，同样，简单的 BST 性能更好。

如果不是使用输入数字的随机序列，而是使用排序序列，事情会变得更有趣，这里我可怜的自制 BST 变得很慢，并且插入 262144 个排序的 int 需要 2866 毫秒，而 SkipList 只需要 168 毫秒。

但是，到了搜索时间，BST 还是更快！对于排序后的输入，我们有 234 毫秒和 77 毫秒，这个 BST 快 3 倍。

使用不同的 p 因子值，我得到的性能结果略有不同：

最后但并非最不重要的一点是内存使用图，正如您所料，它确认如果我们增加每个节点的级别数量，我们会显着影响内存指纹。内存使用量计算为存储所有节点的附加指针所需空间的总和。

毕竟，你们中的任何人都可以向我提供关于如何实现与 BTS 一样好的 SkipList 的评论 - 不计算额外的内存开销 - 吗？

我知道 DrDobbs LINK关于 SkipList 的文章，我浏览了所有论文，搜索和插入操作的代码与PUG89的原始实现完全匹配，所以应该和我的一样好，并且文章没有提供任何性能无论如何分析，我没有找到任何其他来源。你能帮助我吗？

任何评论都非常感谢！

谢谢！:)

有人可以解释一下skipListSearch()andskipListInsert()方法吗？代码来自 Adam Drozdek 的著作Data Structures and Algorithms in C++。在这个skiplist中，插入不需要列表重组，并且生成节点，从而保持不同级别的节点分布足够。

maxLevel = 4. 对于 15 个元素，所需的一指针节点数为 8，二指针节点数为 4，三指针节点数为 2，四指针节点数为 1。每插入一个节点，就会产生一个介于 1 到 15 之间的随机数 r。如果 r < 9，则插入一级节点。如果 r < 13，则插入第二级节点。如果 r < 15，则为三级节点。如果 r = 15，则生成并插入四级节点。

我已经实现了一个惰性锁定跳过列表，就像在“多处理器编程的艺术”一书中一样。但我想增加跳过列表以通过索引访问其元素。这样做我已经编写了这个类（它可以立即运行，只需复制/粘贴）但我的索引访问在多线程模式下仍然失败。

编辑1：

实际上这是一个正在运行的版本！但我必须锁定所有级别直到MAX_LEVEL，而不是当前节点toplevel。所以如果我能摆脱和之间的锁，我会很toplevel高兴MAX_LEVEL。

我正在尝试在 graphviz 中显示一个跳过列表数据结构。如何使图形的所有节点从相同的水平高度而不是随机节点位置开始？

我正在与一位同事进行激烈的讨论，因为他不想承认使用 Java 包中的现有类比编写自己的类更好。

我们希望以线程安全的方式访问集合，以便迭代器也可以工作。

我找到了这个类ConcurrentSkipListSet，但它需要我实现Comparable我们不需要的接口。他认为这比编写整个同步的东西更糟糕。我拒绝。

有没有比 ConcurrentSkipListSet 更好的 Java 类不能让我实现Comparable？