0

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

4

2 回答 2

1

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

首先，展开的链表通常使用非常小的节点大小。正如Wikipedia 文章所说：“足够大，以至于节点可以填充单个缓存行或其中的一个小倍数。” 在现代 Intel 处理器上，高速缓存行是 64 字节。跳过列表节点平均每个节点有两个指针，这意味着前向指针平均每个节点有 16 个字节。加上节点的数据是什么：标量值是 4 或 8 个字节，或者是参考值是 8 个字节（我假设这里是 64 位机器）。

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

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

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

如果你能找到解决这个问题的方法，你仍然不会有太多收获。展开链表的一个重要原因是您在搜索时必须访问每个节点（直到找到的节点）。因此，每次链接遍历可以节省的任何时间都可以节省大量资金。但是使用跳过列表，您可以实现大幅跳跃。例如，在一个组织良好的跳过列表中，您可以在第一次跳转时跳过一半的节点（如果您要查找的节点位于列表的后半部分）。如果展开的跳过列表中的节点仅包含四个元素，那么您获得的唯一节省将是级别 0、1 和 2。在更高级别，您将跳过三个以上的节点，因此您将产生缓存未命中。

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

于 2015-02-16T14:13:02.060 回答
0

链表复杂度为 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 + "来自展开链表的东西，例如 N1/M")

这意味着“新”复杂性不会像人们最初想象的那么好。新的复杂度可能比原来的 O(Log N) 还要糟糕。实现也将更加复杂。所以增益是有问题的，而且相当可疑。

此外，由于单个节点将有大量数据，但只有单个“前向”数组，“树”也不会如此平衡，这将破坏等式的 O(Log N) 部分。

于 2015-02-16T19:45:48.583 回答