问题标签 [skip-lists]

我在内存中有一个已经排序的大小 (N) 集，并且想将其转储到 redis 中，如果先插入头部或尾部，是否可以在 O(N) 中完成？或者没关系，插入会 O(log(N!)) ~ O(N log(N))

有关更多详细信息，redis 排序集是使用哈希图和跳过列表（用于排序）实现的。

编辑：这个问题一直没有答案，或者至少答案对我来说有点模棱两可：Redis：当插入的元素位于开头或结尾时，ZADD 是否比 O(logN) 好？

我在互联网上阅读了跳过列表，我只是了解它如何与不同的数据结构和所有数据一起工作。但我真的想用双向链表实现跳过列表，因为我想在插入时对双向链表进行排序。意味着当元素插入时，它应该仅以排序方式插入。

在这里，我实现了以排序方式在双向链表中插入数据的方法，但是当元素数量非常大时，插入数据并以排序方式制作列表需要很长时间。

请告诉我如何在现有函数中添加跳过列表算法，或者我必须重新重写整个内容？任何有关实施的帮助将不胜感激

这是代码：

为什么 Google/Wikipedia 中没有关于展开的跳过列表的任何信息？例如展开链表和跳过链表的组合。

据我了解，ConcurrentSkipListSet插入、搜索和删除元素的平均复杂度为 O(log n)，最坏的情况为 O(n)。如何访问第一个和最后一个元素？它是否低于对数？我看到它保留了一个指向头部的指针。因此，我猜测第一个元素是 O(1)。

考虑一大组一维的浮点区间，例如

希望找到包含给定点的所有区间。例如给定点 = 1.2，算法应该返回第一个区间，如果给定点 = 2.0，它应该返回上例中的前两个区间。

在我正在处理的问题中，这个操作需要在大量的时间间隔内重复大量的次数。因此，不需要蛮力搜索，性能是一个重要因素。

在搜索它之后，我发现这个问题是在计算几何的上下文中使用间隔跳过列表来解决的。我想知道是否有任何简单、高效的 C++ 实现可用。

编辑：为了更准确地了解问题，有 N 个区间，对于 M 个点，应该确定哪些区间包含每个点。N 和 M 是大数，其中 M 大于 N。

我已经坚持了两个月了，尝试了导师和互联网。我想它已经溃烂了这么久，以至于我学到的一切都从窗户飞到垃圾桶里。

我想声明一个跳过列表节点然后使用它。我不知道如何初始化和访问我的节点数组。我认为节点将我的数组初始化为全NULL，但是为什么我不能将我的节点数组索引[0]设置为指向它前面的节点索引[0]？

这是我的节点：

我没有列表结构，我只是在 main 中组装它

然后我想将 headSentinels 附加到我的第一个节点。

如果我能弄清楚如何使用 main 中的节点，那么我就能弄清楚我的跳过列表的其余部分。有什么东西把我绑起来了，这可能很容易。

我可以编译我的程序，但是当我尝试插入一个数字时，我得到一个分段错误。

我只想先在数组 [0] 上组装一个链表，然后再开始使其成为实际的跳过列表

我试着问我的问题，但我似乎没有正确地问它，我已经被困了 2 个月了。（这是可悲的）

仅供参考：我从节点构建了一个链表：

要在 main 中链接这些，我使用 -> 来分配值

现在我正在尝试制作一个跳过列表，它应该与我的原始节点具有相同的结构，除了 node* next 应该是一个节点类型的指针数组。

我对如何拥有节点指针数组感到困惑。我注意到它们看起来像这样： node **next 然后声明动态分配内存。我只希望我的数组大小为 4。所以 [3]。

我的问题是如何使用 main() 中的节点指针数组创建新节点并将某些内容放在节点数组的第一个插槽中？

这不适用于将事物放入数组中，但它确实适用于放入数字。

请帮我。

我在编写一种在跳过列表中查找元素的方法时遇到了一些困难。

我正在尝试实现它，如果我们正在搜索一个元素并且该元素在列表中不存在，则返回下一个最大值；这将使其成为插入的理想选择。但是，如果找到该元素，则返回该元素。

我将其用于我的remove(T key)方法；如果我们找到该元素，则将其删除。如果它不在列表中，throw new java.util.NoSuchElementException().

虽然我当前的实现可以很好地插入，但我发现它在查找现有元素时不起作用——相反，它将获得下一个值。（从技术上讲，它不应该适用于插入，但确实如此）。

********************** SkipList (size = 3) Level: 2 (null), , , (5) Level: 1 (null), (3), (4), (5) **********************

以上是跳过列表当前的样子。

下面是我正在制作的跳过列表的结构。左手标记是数据为空的节点；我们还有一个幻像节点作为头部；幻像头帮助我们跟踪跳过列表中的当前级别数。结构图

在其当前状态下，如果我们尝试search(4)，返回的节点将是5，即使4它在列表中。

I have this code for a skip list I modified from a source online, the add(x) method somewhat works.

it works when you add a number like 5, then any number smaller than the last number, like 4 but once it get to 7 or any number larger than the previous it gets stuck in a loop, and I cannot see why.

EDIT: I uploaded the entire code I developed, the code is from a Textbook of mine that is in Pseudocode, it needed to be adapted into Java format. I cannot see why its failing.

我正在实施一个跳过列表。它是什么并不重要，但它现在适用于 1000 个节点，但不适用于 10000 个节点。我得到了没有意义的 SegFaults，所以我打印了一些变量。令我惊讶的是，很多不应该改变的东西，变成了垃圾值。例如，我在函数 insertNode 之前和之后打印 inputValue。它有时会重置为零，而应始终递增。我们看代码（跳过读取文件输入，问题发生在while循环）：

我跑了 Valgrind。无效的内存写入/读取发生在变量发生变化之后，至少我相信如此。这就是我添加完整性检查的原因。正如我所想的那样，在尝试访问密钥之前没有无效的内存写入/读取[9999999999999999999999]。但是该行只能运行 int sanitycheck 已更改，而我从来没有这样做过。

最后，这是 insertNode 的代码。我看不到任何可能导致这种情况的东西：

和结构：

我什至没有使用 malloc。有指针操作，但是 valgrind 应该检测我是否做错了什么，对吗？如果我的内存不足，就会出现异常。我创建但从不访问/写入/更改的 int 怎么可能被修改？对不起，很长的帖子，但我不知道问题可能出在哪里。

没有完整性检查的 Valgrind 输出（键 [999...9]）： http: //pastebin.com/hWH3fri2

第 155 行是 while (inputFile >> inputKey)