展开的跳跃列表的实际使用

Question

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

Answer 1

可能是因为它通常不会给您带来很大的性能改进（如果有的话），并且它会在一定程度上涉及正确编码。

首先，展开的 linked 列表通常使用非常小的节点大小。正如 Wikipedia article 所说：“刚好足以让节点填充单个缓存行或其中的一小部分。”在现代 Intel 处理器上，缓存行是 64 字节。跳跃列表节点平均每个节点有两个指针，这意味着前向指针每个节点平均有 16 个字节。加上节点的任何数据：4 或 8 个字节用于标量值，或 8 个字节用于引用（我假设这里是 64 位机器）。

因此 "element." 总计 24 个字节，除了元素不是固定大小。他们有不同数量的前向指针。因此，您需要通过为每个元素的最大数量的前向指针分配一个数组来使每个元素具有固定大小（对于具有 32 级的跳跃列表需要 256 个字节），或者使用大小正确的动态分配数组.所以你的元素本质上变成了：

struct UnrolledSkipListElement
{
    void* data; // 64-bit pointer to data item
    UnrolledSkipListElement* forward_pointers; // dynamically allocated
}

这会将您的元素大小减少到仅 16 个字节。但是你会失去很多从展开中获得的缓存友好行为。要找出下一步要去哪里，您必须取消引用 forward_pointers 数组，这将导致缓存未命中，因此消除了通过展开获得的节省。此外，动态分配的指针数组不是免费的：分配该内存涉及一些（小的）开销。

即使您能找到解决该问题的方法，您仍然不会有太大收获。展开 linked 列表的一个重要原因是您在搜索时必须访问每个节点（直到找到的节点）。因此，每次 link 遍历可以节省的任何时间加起来都是非常大的节省。但是有了跳过列表，你就可以大跃进了。例如，在一个组织完美的跳过列表中，您可以在第一次跳转时跳过一半的节点（如果您要查找的节点位于列表的后半部分）。如果展开的跳过列表中的节点仅包含四个元素，那么您获得的唯一节省将是级别 0、1 和 2。在更高级别，您将跳过前面三个以上的节点，因此您将招致缓存未命中。

所以跳过列表没有展开，因为它会在一定程度上涉及实施并且它不会给你带来很大的性能提升，如果有的话。这很可能会导致列表变慢。

Answer 2

链表复杂度为O(N)

跳表复杂度为 O(Log N)

展开链表的复杂度可以计算如下：

O (N / (M / 2) + Log M) = O (2N/M + Log M)

其中 M 是单个节点中的元素数。

因为Log M不显着，

展开链表复杂度为O(N/M)

如果我们假设将 Skip list 与 Unrolled 链表结合起来，新的复杂度将是

O(Log N + "something from unrolled linked list such N1/M")

这意味着 "new" 复杂性不会像最初有人想象的那样好。新的复杂性可能比原来的 O(Log N) 更糟。实施也将更加复杂。所以增益是值得怀疑的，相当可疑。

此外，由于单个节点将有很多数据，但只有单个 "forward" 数组，因此 "tree" 也不会如此平衡，这将破坏 O(Log N) 部分等式。

展开的跳跃列表的实际使用

Realistic usage of unrolled skip lists

linked-list

skip-lists

data-structures