标签: skip-lists

我最近遇到了称为跳过列表的数据结构.它似乎与二叉搜索树具有非常相似的行为.

为什么你想在二叉搜索树上使用跳过列表？

我正在尝试使用最小的额外内存开销实现一个与BST一样好的跳过列表,目前即使不考虑任何内存限制,我的SkipList实现的性能也远远不是一个非常天真的平衡BST实现 - 所以说,手工制作的BTS :) -

作为参考,我使用了William Pugh PUG89的原始论文以及我在Sedgewick -13.5-的C中算法中发现的实现.我的代码是一个递归实现,这是插入和查找操作的线索:

sl_node* create_node()
{
    short lvl {1};
    while((dist2(en)<p)&&(lvl<max_level))
        ++lvl;
    return new sl_node(lvl);
}

void insert_impl(sl_node* cur_node,
        sl_node* new_node,
        short lvl)
{
    if(cur_node->next_node[lvl]==nullptr || cur_node->next_node[lvl]->value > new_node->value){
        if(lvl<new_node->lvl){
            new_node->next_node[lvl] = cur_node->next_node[lvl];
            cur_node->next_node[lvl] = new_node;
        }
        if(lvl==0) return;
        insert_impl(cur_node,new_node,lvl-1);
        return;
    }
    insert_impl(cur_node->next_node[lvl],new_node,lvl);
}
sl_node* insert(long p_val)
{
    sl_node* new_node = create_node();
    new_node->value = p_val;
    insert_impl(head, new_node,max_level-1);
    return new_node;
}

这是查找操作的代码:

sl_node* find_impl(sl_node* cur_node,
        long p_val,
        int lvl)
{
    if(cur_node==nullptr) return nullptr;
    if(cur_node->value==p_val) return …

我听说过一种新的平衡 BST 数据结构，称为zip 树。什么是zip树？它是如何工作的？

我想知道这里是否有人使用跳过列表.它看起来与平衡二叉树具有大致相同的优点,但实现起来更简单.如果你有,你是自己编写的,还是使用预先编写的库(如果有的话,它的名字是什么)？

我需要实现一个无锁的跳过列表.我试图找文件.不幸的是,我发现的是无锁单链表(多种口味).但是如何实现无锁跳过列表？

我想在两个对象之间实现一个简单的比较器，它的唯一要求是

1. 它是一个有效的比较器（即定义所有对象的线性顺序）和
2. .compare当且仅当对象相同时才返回 0 。

会Comparator.comparing(System::identityHashCode)工作吗？还有其他方法吗？

动机： 我想构建一个集合，允许我将时间戳消息存储在线程安全集合中，该集合将支持诸如“获取时间戳位于 [a,b) 中的所有消息”之类的查询。

似乎番石榴TreeMultimap使用全局锁（编辑：如果用synchronizedSortedSetMultimap包装器包装），并且ConcurrentSkipListMap似乎每次只支持一个条目（它是一张地图，而不是多张地图）。所以我想只使用一组对：

ConcurrentSkipListSet<ImmutablePair<Float,Message>> db,

其中对按词法排序，首先按时间（使用Float.compareTo），然后按类似Comparator.nullsFirst(Comparator.comparing(System::identityHashCode)).

• 的nullsFirst是有只是让db.subSet(ImmutablePair.of(a,null), ImmutablePair.of(b,null))查询半开时间区间[a，b）中。

• 你明白为什么我关心比较器保持相同性：如果消息比较器对不相同的消息返回零，消息可能会被删除。

• 你也明白了为什么我不需要比较器的其他东西：它就在那里，所以我可以使用ConcurrentSkipListSet. 我当然不想强加于用户（好吧，只是我 :-) 为Message.

• 另一种可能的解决方案是使用 a ConcurrentSkipListMap<Float, Set<Message>>（带有线程安全的 Set<> 实例），但在内存方面似乎有点浪费，一旦消息被删除，我需要自己删除 emptySet 以节省内存。

编辑：正如一些人所指出的，identityHashCode 可能会产生冲突，实际上我现在已经确认在我的设置中存在这种冲突（大致相当于上面的 4K 集合，每个集合每个时间段填充 4K 消息）。这很可能是我看到一些消息丢失的原因。所以我现在比以往任何时候都更有兴趣找到某种方法来拥有一个真正尊重相同性的“不可知”比较运算符。实际上，64 位哈希值（而不是 identityHashCode 提供的 32 位值）可能就足够了。

我ConcurrentSkipListSet在Java Collection Framework中找到了,它使用跳过列表进行备份.但Java中是否有跳过列表？一个集合在我的用例中不起作用.我需要一个支持重复的可索引列表.

我正在阅读跳过列表和MemSQL,并想知道为什么跳过列表在数据库中没有被更广泛地使用？使用跳过列表是否有任何重大缺陷？

我有兴趣实现一个优先级队列,以实现一个相对简单的高效Astar实现(我的意思是优先级队列很简单).

似乎因为Skip List提供了一个简单的O(1)extract-Min操作和一个O(Log N)的插入操作,它可能与更难实现的具有O(log N)提取的Fibonacci Heap竞争 - 最小和O(1)插入.我认为Skip-List对于具有稀疏节点的图更好,而Fibonacci堆对于具有更密集连接的节点的环境更好.

这可能会使Fibonacci Heap通常更好,但我认为Big-Oh明智的这些是相似的吗？

我觉得为什么QMap实现了跳过列表数据结构而不是rb-tree？有关并发数据结构和跳过列表优势的非常有趣的SO线程比rb-tree,优点和缺点.它确实是非常有用的链接,但QMap不是线程安全的,它不会进行任何互斥锁定,以便开箱即用同步访问.它需要包装或子类化.

对我来说,编写"手工制作"的滑雪列表而不是rb-tree并不简单,所以这也不是很明显.

在非线程安全的Qt容器的上下文中是否有任何kill-feature？

Tnx提前.