问题标签 [skip-lists]

在redis.h中，skipnode 定义如下：

varspan是什么意思？这个 var 存储什么？

插入 n 个元素后，跳过列表使用的预期空间是多少？

我预计在最坏的情况下，空间消耗可能会无限增长。

维基百科说“空间 O(n)”。

如何以一种或另一种方式证明这一点？

我想将（简单链接）列表转换为从链接列表派生的跳过列表。在将（链接）列表作为参数的转换 ctor 内部，我在 *. 我只是从 main 调用那个 ctor 一次。新的 SkipList 怎么可能被循环调用？

我对从跳过列表中插入或删除元素所需的时间有点困惑。

假设有一个高度为 H 的跳过列表，每个级别包含 n/2^i 个条目。
n = 键值对总数
i = 跳过列表的级别 i<= H

现在，根据理论，插入操作将执行以下操作
1. 找到一个键 <= 正在插入的键。
2. 插入此键
3. 在基础级别以上的级别中随机创建此条目。

让我们假设 Skip 列表基于链表。
第 1 步：应该取 O(n)。
第 2 步：应该是 O(1)。
第 3 步：应该是 O(log n) 时间。我仍然对这个逻辑感到困惑，它将成为下面问题的一部分

问题

1. 基于上述事实，插入时间不应该是 O(n) + O(1) + O(log n) 吗？忽略低阶项，它应该是 O(n) + O(log n)？

2. 第 3 步再次应该花费 O(n) 时间来搜索要插入的密钥 <= 密钥，然后需要 o(1) 时间来插入。导致非常复杂的插入运行时间？

书上说插入跳过列表需要 O(log n) 时间。我一定错过了一些重要的信息，请你帮我很好地理解这个概念。

我很清楚为什么 QMap 是通过 skiplist 数据结构而不是 rb-tree 实现的？有一个非常有趣的SO 线程，关于并发数据结构和跳过列表对 rb-tree 的好处，优点和缺点。它确实是非常有趣的对话，带有有用的链接，但 QMap 不是线程安全的，它不做任何互斥锁来同步访问开箱即用。它需要包装器或子类化。

对我来说，编写“手工制作的”跳过列表而不是 rb-tree 并不简单，所以这也不明显。

在非线程安全的 Qt 容器的上下文中是否有任何终止功能？

提前Tnx。

我可以知道为什么平均情况下插入跳过列表的时间复杂度是 O(log n)，为什么具有 n 个元素的跳过列表的高度很可能是 O(log n)。以及为什么每一层的平均搜索时间是 O(1)。

最近我遇到了ConcurrentSkipListMap，它skip list是ConcurrentNavigableMap. 现在我想知道，为什么它被实现为skip list.

并发导航地图skip list的“标准”实现吗？什么使它特别好？skip list

我对使用跳过列表作为 A* 的开放列表很感兴趣。然而，让我感到困扰的是它的概率性质。开放列表可以从非常小的节点集到大量节点，并且需要保持每个节点的性能。

据我了解，跳过列表对于小数据集随机给出错误结果的可能性更高。我认为这可能会在生成大量短路径时出现问题。

我正在考虑解决这个问题，为什么不在一定程度上监视随机数。保持每个级别的节点数量的运行总数，并且为了保持每个级别之间的理想节点分布，有时会干预并强制节点成为特定级别。

我不确定这在我给定的应用程序中的效果如何，如果我应该专注于我的开放列表的另一个数据结构。

我在跳过列表上阅读的所有文章都没有提到这种优化。由于我对整个性能分析游戏相当陌生，因此我不愿尝试改进已记录的数据结构。

在一些博客和 lucene 网站中，我知道 lucene 在倒排索引中使用数据结构“跳过列表”。但我对此有些疑惑。

1：一般情况下，skip list可能用在内存中，倒排索引存储在磁盘中。那么 lucene 在索引上搜索时是如何使用它的呢？只是在磁盘上扫描或将其加载到内存中？

2：skip list的insert操作符经常使用random(0,1)来决定是否插入到下一级，但是在luncene的介绍中，似乎每一项都是固定的区间，那么lucene如何创建不同的“skip list”呢？

如果我错了，请纠正我。

到目前为止，我发现的所有跳过列表实现都使用键并将它们与值相关联。但是我需要的是一个跳过列表，我可以在其中在索引位置 i 处插入一个值，以便可以使用索引递增 1 来查询该索引 i 之后的所有值。

这里有一个澄清的小例子：

现在value应该是 6，因为在索引 3 处插入了 5，所以值 6 向上移动了一个索引。

可以使用跳过列表构建这样的数据结构，请参阅此处的可索引跳过列表： http ://en.wikipedia.org/wiki/Skip_list

但我找不到实现。拥有这样的数据结构将非常有用，例如在大列表上有许多随机插入和访问的情况下。