问题标签 [skip-lists]

我安排了一堆活动，我想检查我安排的活动是否有 10 天的间隔，在这 10 天内没有活动发生。是否有良好的数据结构和搜索算法来找到 10 天的间隔？

我想知道如何在 python 中实现一个跳过列表。

我已经制作了一个链接列表，但是在如何创建链接列表的不同级别以及在搜索或将节点插入列表时如何遍历列表的每个级别时遇到了麻烦。

不确定问题应该在这里还是程序员（或其他一些 SE 站点），但我很好奇平衡二叉树和可索引跳过列表之间的相关差异。这个问题是在这个问题的背景下提出的。来自维基百科：

跳过列表是一种概率数据结构，似乎有可能取代平衡树作为许多应用程序选择的实现方法。跳过列表算法具有与平衡树相同的渐近预期时间界限，并且更简单、更快并且使用更少的空间。

跳过列表的空间要求不取决于层次结构的深度吗？并且二叉树不是更容易使用吗，至少对于搜索（在平衡 BST 中授予，插入和删除可能很棘手）？跳过列表还有其他优点/缺点吗？

我已经为整数实现了跳过列表。在测试方法插入时，我在带有计数器 j 的 for 循环中插入从 1 到 1000000 的自然数。我也在使用秒表。附录：在实际程序中，值是双精度值，因为我在 double.NegativeInfinity 中使用了值为 double.PositiveInfinity 的哨兵。（但这不应该是问题）伪代码：

当我制作图形时间/节点数时，它是线性的，但图形步骤/节点是预期的对数。（步骤是方法插入中的循环次数（~操作））。

方法 insert 创建额外的节点并设置一些指针。节点的实现方式如下：

跳过列表由节点组成。

Insert 在类 SkipList 中定义，并以下列方式工作：

我还实现了一个跳过列表版本，其中节点是块并且具有 n = node.depth 右邻居，存储在数组中，但图形时间/数量。节点的数量仍然是线性的（并且节点的步数/数量是对数的）。

我正在开发自己的跳过列表模板类。以下是它的规格：Iterator类保存单个跳过列表的副本。Head 和 Tail 迭代器始终为空，tail 迭代器的 tail 值设置为TRUE。

我的问题出在下面的插入函数中：

它有什么问题？调试了很长时间，我想不通。以下代码给出了内存转储错误！

如果事先知道'n'（要存储的元素数量），我会说正确吗？

跳过列表的 Maxlevel 是(log n + 1)，因为我需要在创建跳过列表之前知道 maxlevel ，这意味着我应该知道要存储的元素数量是多少。

我正在尝试编写一个 ruby​​ 函数来确定跳过列表的平均预期搜索时间。我没有很强的数学背景，我相信我从这个函数得到的结果是不正确的。

n= 列表中的元素数

base=晋升概率的分母。即如果提升 4 个节点中的 1 个，则 base = 4

如何在 Ruby 中表达一个方程，该方程将采用跳过列表和基数中的元素数量并返回平均搜索时间？

我正在基于Java的ConcurrentSkipListMap实现一个并发跳过列表映射，不同之处在于我希望列表允许重复，并且我还希望列表是可索引的（以便查找列表的第 N 个元素需要 O(lg( n)) 时间，而不是标准跳过列表的 O(n) 时间）。这些修改不存在问题。

此外，跳过列表的键是可变的。例如，如果列表元素是整数 {0, 4, 7}，那么中间元素的 key 可以更改为 [0, 7] 中的任何值，而不会提示更改列表结构；如果键更改为 (-inf, -1] 或 [8, +inf)，则删除并重新添加元素以保持列表顺序。我没有将其实现为移除后跟 O(lg(n)) 插入，而是将其实现为移除后跟线性遍历后跟 O(1) 插入（预期运行时间为 O(1) - 99节点将与相邻节点交换的时间百分比）。

很少会插入一个全新的节点（在启动后），并且永远不会删除一个节点（没有立即重新添加它）；几乎所有的操作都是 elementAt(i) 来检索第 i 个索引处的元素，或者是在修改键后交换节点的操作。

我遇到的问题是如何实现密钥修改类。从概念上讲，我想做类似的事情

（insert被调用的子方法run使用 CAS 来处理两个节点尝试同时在同一位置插入的问题（类似于ConcurrentSkipListMap处理冲突插入的方式） - 从概念上讲，这与第一个节点锁定节点相同与插入点相邻，但在没有冲突的情况下会减少开销。）

这样我可以确保列表总是有序的（如果密钥更新有点延迟也没关系，因为我可以确定更新最终会发生；但是，如果列表变得无序，那么事情可能会变得混乱）。问题在于以这种方式实现列表会生成大量线程，每个线程Node（列表中有数千个节点） - 其中大多数会在任何给定时间点阻塞，但我担心有数千个阻塞线程仍然会导致过高的开销。

另一种选择是使update方法同步并Runnable从中删除接口Node，以便两个线程将更新排队Node，然后在其单独的线程上处理这些更新，这两个线程将轮流执行该Node#update方法。问题是这可能会造成瓶颈。如果八个不同的线程都决定一次更新同一个节点，那么队列实现可以很好地扩展，但是同步实现会阻塞八个线程中的七个（然后会阻塞六个线程，然后是五个，等等）。

所以我的问题是，我将如何实现类似于队列实现的东西，除非减少线程数量，否则我将如何实现类似同步实现的东西，除非没有潜在的瓶颈问题。

我最近遇到了一种在排序列表中搜索数字的算法，它是这样的：

给定：一个预言机，它告诉您给定的数字是否大于或小于正在搜索的数字。

从列表中的第一个元素开始。向前跳过 1 个元素并询问预言机您是否已经超过了正在搜索的数字。

如果没有，请跳过 2 个元素并询问神谕您是否走得太远。

如果不跳过前面的 4 个元素，等等......

当您找到导致您忽略正在搜索的号码的第一个跳过时，您可以确定包含正在搜索的号码的子区间。

最后，对子区间进行二分查找。

我想知道这个算法叫什么，以便我可以对它做更多的研究。

谢谢

所以我读了一些关于跳过列表的内容，目前正在实施一个。但是到目前为止，我还没有真正做到一件事。为什么跳过列表是随机的？在所有来源中，我发现跳过列表使用随机数来决定将插入项目的级别。不能计算出最优值吗？或者你不能只说“每四个项目”应该插入到上面的级别吗？