问题标签 [skip-lists]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
68 浏览

.net - .NET 中是否有有序的线程安全映射?

它看起来ConcurrentDictionary大致相当于 .NET 的 Java 的ConcurrentHashMap. 是否有与 Java 等效的 .NET ConcurrentSkipListMap?我找不到一个。

PS 仅就接口而言等效。实现中的等效项(跳过列表)也可以。

0 投票
2 回答
289 浏览

c - 指针数组与跳过列表混淆

我想我对跳过列表的工作原理有了基本的了解,但是除了作为 C 初学者之外,对它们来说是新手让我在一些方面感到困惑,尤其是列表的初始化。这是我要遵循的代码:

我还没有在 C 语言中对指针数组做过任何事情,所以我想我有点了解它们是如何工作的。如果有人愿意帮助我,我有几个问题。

首先,我做sizeof(int)了,得到了 4,sizeof(Node*)得到了 8,所以我希望sizeof(Node)等于 12,但结果是 16,这是为什么呢?SkipList与其内容的大小相比,它的大小也有同样的混淆。我拿出typedef[1]看看是否是其中任何一个原因,但尺寸仍然是 16。

其次,为什么[1]在struct Node *next[1]list->header->next[i]后期需要吗?next[i]高于 1 可以吗?是不是因为每个节点的指针数量是可变的,所以你把它变成一个数组,然后再单独增加它?

三、为什么list->header->next[i] = list->header最初不是NULL?

非常感谢任何建议/意见,谢谢。

0 投票
1 回答
1545 浏览

data-structures - 跳过列表可以有重复的元素吗?

我知道跳过列表是一种排序的数据结构,但它可以有重复的元素吗?还是应该是,如果您尝试插入一个已经存在的元素,它只会返回指向预先存在的元素的指针?

0 投票
2 回答
321 浏览

c - 我的跳过列表是否真的在 N 而不是 log(N) 中搜索?

所以我最终认为我完成了一个工作跳过列表的创建,并认为我应该检查我的工作并研究搜索功能的时间安排。我找到了一个关于如何使用clock()和实现它的教程:

我想通过这样做并绘制 N 与时间的关系,我会得到一个看起来对数的图形,但我的图形看起来是线性的:

在此处输入图像描述

我是否对如何安排我的函数计时以尝试测试时间复杂性有误解,或者我的跳过列表只是没有按应有的方式搜索?这是我的整个跳过列表实现以防万一,但调用了搜索功能findElement()

非常感谢任何建议,谢谢。

0 投票
1 回答
214 浏览

insert - Infinity/-infinity 用于未知类型的跳过列表插入?

我正在实施一个跳过列表,例如:

在我在网上看到的解释中,跳过列表的头部和尾部有无穷大/负无穷大键,但它们都与数字键一起使用。

我可以假设<==运算符可用于键,所以我不必担心string < string

但是,如何找到最小/最大类型的值作为头/尾指针?是否有类似INT_MAXINT_MIN但对于任何类型的东西?

0 投票
2 回答
1548 浏览

java - Java中的Redis实现

我正在尝试在 java中实现一个基本的redis 服务器。但是我不确定我必须使用什么数据结构来实现它的数据库。首先我认为简单HashMap就足够了,因为它可以存储<Object, Object>值,我可以实现GETSET命令。但是当我深入研究时,我可以找到像GETBIT,等这样的命令SETBIT,这些命令ZADD需要更复杂的数据库数据结构。

我想我应该使用带有 ConcurrentSkipListMap 类型的值列的 HashMap。我对吗?请帮忙。

而且,我应该在将 Set 命令的字符串值转换为二进制值后存储它吗?

0 投票
3 回答
140 浏览

algorithm - 删除链表中的第 10000 个节点

我有一个 n 个节点的链表,我想删除第 k 个节点并显示其中的元素。如果 n 的值相对较小并且问题的复杂性不是问题,这很容易。

问题是当我在链表中​​有 n 个节点时 n >=200000 并且我想删除一个也是相对较大值的节点(比如 k=150000)。

这个问题的正常解决方案是遍历整个链表并删除一个节点(解决方案的复杂度为 O(n) ),尽管它是直接且简单的解决方案,但需要更多时间。这个问题的其他解决方案可以是 2 个指针,但这仍然不是最佳解决方案。

我正在寻找一种最佳的解决方案,并在最短的时间内提供结果。

希望我的问题很清楚。需要一些帮助..

0 投票
1 回答
474 浏览

c++ - 在 C++ 中实现 Skiplist 节点

我正在寻找创建一个跳过列表数据结构。这是迄今为止我为 Node.js 编写的代码快照。

我知道如果我在这种情况下使用矢量会更好,因为您可以动态更改其大小。我想知道如果我想使用数组我会去哪里。

我是 C++ 新手,所以我想知道是否可以在以后分配数组的大小。说,我想添加另一个只有大小为 2 的指针数组的节点。

0 投票
1 回答
1436 浏览

algorithm - 算法:在跳过列表中插入

在跳过列表中插入的算法是什么样的?

通常在谷歌上搜索时会弹出类似内容,但奇怪的是,我似乎在我的书或互联网上找不到任何有用的东西。

我唯一能找到的是关于跳过列表如何工作的解释。

0 投票
0 回答
46 浏览

c - 将节点插入跳过列表时出现分段错误

我正在尝试在跳过列表中插入一些元素

其中节点按它们的键排序。但是,当我尝试插入一个比前一个键更大的节点时,我得到一个段错误,我发现它发生在插入函数中

因为

一片空白。我不明白为什么会这样,任何帮助将不胜感激