跳表，它们的表现真的如 Pugh 论文所声称的那样好吗？
Skip lists, are they really performing as good as Pugh paper claim?
我正在尝试使用最小的额外内存开销实现一个与 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 cur_node;
if(cur_node->next_node[lvl] == nullptr || cur_node->next_node[lvl]->value>p_val){
if(lvl==0) return nullptr;
return find_impl(cur_node,p_val,lvl-1);
}
return find_impl(cur_node->next_node[lvl],p_val,lvl);
}
sl_node* find(long p_val)
{
return find_impl(head,p_val,max_level-1);
}
A sl_node - 跳过列表节点 - 看起来像这样：
struct sl_node
{
long value;
short lvl;
sl_node** next_node;
sl_node(int l) : lvl(l)
{
next_node = new sl_node*[l];
for(short i{0};i<l;i++)
next_node[i]=nullptr;
}
~sl_node()
{
delete[] next_node;
}
};
如您所见，与书中的实现相比，此实现没有任何特别或高级之处，我不会分享 Balaced BTS 代码，因为我认为这里不需要，但它是一个非常基本的 BTS，具有当新节点高度大于 16*lg(n) 其中 n 是节点数时，在插入期间触发重新平衡函数。
也就是说，只有当最大高度比最好的理论高度大 16 倍时，我才重新平衡这三个，正如我所说，这个简单的自制 BST 比自制的 Skip List 表现得更好。
但首先，让我们看一些数据，使用 p=.5 和 n=262144，SkipList 中节点的级别具有以下分布：
1:141439, 53.9547%
2:65153, 24.8539%
3:30119, 11.4895%
4:13703, 5.22728%
5:6363, 2.42729%
6:2895, 1.10435%
7:1374, 0.524139%
8:581, 0.221634%
9:283, 0.107956%
10:117, 0.044632%
11:64, 0.0244141%
12:31, 0.0118256%
13:11, 0.00419617%
14:5, 0.00190735%
15:1, 0.00038147%
16:5, 0.00190735%
这几乎完美 - 哦，这是一个很大的！ - 符合文章中的理论，即：50% 级别 1，25% 级别 2 等等。输入数据来自我最好的可用伪随机数生成器，又名 std::random_device，具有 std::default_random_engine 和统一的 int 分布。输入对我来说看起来很随机 :) !
在我的机器上以随机顺序搜索 'all' SkipList 中的 262144 个元素所需的时间是 315 毫秒，而在 naive BTS 上进行相同的搜索操作所需的时间是 134 毫秒，所以BTS 几乎比 SkipList 快两倍。这不是我对 "Skip list algoriths have the same asymptotic expected time bounds as balanced trees and are simple, faster and use less space" PUG89.
的期望
节点 'insertion' 所需的时间对于 SkipList 是 387 毫秒，对于 BTS 是 143 毫秒，再一次，朴素的 BST 表现更好。
如果我不使用输入数字的随机序列而是使用排序序列，事情会变得更有趣，这里我可怜的自制 BST 变慢了，插入 262144 个排序的 int 需要 2866 毫秒，而 SkipList 只需要 168 毫秒.
但是，到了搜索的时候，BST还是更快！对于排序后的输入，我们有 234 毫秒和 77 毫秒，这个 BST 快了 3 倍。
使用不同的 p 因子值，我得到的性能结果略有不同：
最后但并非最不重要的是，内存使用图，如您所料，它确认如果我们增加每个节点的级别数量，我们会显着影响内存指纹。内存使用量计算为存储所有节点的附加指针所需的 space 总和。
毕竟，你们中的任何人都可以就如何实现与 BTS 一样好的 SkipList 提供评论 - 不计算额外的内存开销 - 吗？
我知道 DrDobbs LINK 关于 SkipList 的文章，我浏览了所有论文，搜索和插入操作的代码与原始代码完全匹配PUG89 的实现应该和我的一样好，而且这篇文章没有提供任何性能分析，我没有找到任何其他来源。你能帮帮我吗？
非常感谢任何评论！
谢谢！ :)
历史
自 William Pugh 撰写他的原始论文以来，时代发生了一些变化。我们在他的论文中没有提到 CPU 和操作系统的内存层次结构，这已成为当今如此普遍的焦点（现在通常与算法复杂性同等重要）。
他的基准测试输入案例只有区区 2^16 个元素，而当时的硬件通常最多只有 32 位扩展内存寻址可用。这使得指针的大小只有我们今天在 64 位机器上使用的指针大小的一半或更小。同时，例如，字符串字段可能同样大，使得存储在跳跃列表中的元素与跳跃节点所需的指针之间的比率可能小得多，特别是考虑到我们经常需要每个跳跃节点的指针数量.
C 编译器当时在寄存器分配和指令选择等方面的优化方面并不那么积极。即使是普通的手写汇编也常常可以在性能上提供显着的好处。像 register 和 inline 这样的编译器提示在那个时候实际上起了很大的作用。虽然这可能看起来有点没有实际意义，因为平衡 BST 和跳跃列表实现在这里都是平等的，但即使是基本循环的优化也是一个更加手动的过程。当优化越来越成为一个手动过程时，更容易实施的东西通常更容易优化。跳表通常被认为比平衡树更容易实现。
因此，所有这些因素都可能影响了 Pugh 当时的结论。然而时代变了：硬件变了，操作系统变了，编译器变了，对这些主题进行了更多研究，等等。
实施
除此之外，让我们找点乐子，实现一个基本的跳过列表。出于懒惰，我最终调整了可用的实现 here。这是一种 运行 普通的实现方式，与当今大量易于访问的示例性跳过列表实现方式几乎没有什么不同。
我们会将我们的实现的性能与几乎总是作为红黑树实现的 std::set 进行比较*。
* 有些人可能想知道为什么我使用 0 而不是 nullptr 之类的东西。这是一种习惯。在我的工作场所，我们仍然必须编写针对各种编译器的开放库，包括那些只支持 C++03 的编译器，所以我仍然习惯于以这种方式编写 lower/mid-level 实现代码，有时甚至在C，所以请原谅我写这段代码的旧风格。
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
using namespace std;
static const int max_level = 32;
static const float probability = 0.5;
static double sys_time()
{
return static_cast<double>(clock()) / CLOCKS_PER_SEC;
}
static int random_level()
{
int lvl = 1;
while ((static_cast<float>(rand()) / RAND_MAX) < probability && lvl < max_level)
++lvl;
return lvl;
}
template <class T>
class SkipSet
{
public:
SkipSet(): head(0)
{
head = create_node(max_level, T());
level = 0;
}
~SkipSet()
{
while (head)
{
Node* to_destroy = head;
head = head->next[0];
destroy_node(to_destroy);
}
}
bool contains(const T& value) const
{
const Node* node = head;
for (int i=level; i >= 0; --i)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
}
node = node->next[0];
return node && node->value == value;
}
void insert(const T& value)
{
Node* node = head;
Node* update[max_level + 1];
memset(update, 0, sizeof(Node*)*(max_level + 1));
for (int i = level; i >= 0; i--)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
update[i] = node;
}
node = node->next[0];
if (!node || node->value != value)
{
int lvl = random_level();
assert(lvl >= 0);
if (lvl > level)
{
for (int i = level + 1; i <= lvl; i++) {
update[i] = head;
}
level = lvl;
}
node = create_node(lvl, value);
for (int i = 0; i <= lvl; i++) {
node->next[i] = update[i]->next[i];
update[i]->next[i] = node;
}
}
}
bool erase(const T& value)
{
Node* node = head;
Node* update[max_level + 1];
memset(update, 0, sizeof(Node*)*(max_level + 1));
for (int i = level; i >= 0; i--)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
update[i] = node;
}
node = node->next[0];
if (node->value == value)
{
for (int i = 0; i <= level; i++) {
if (update[i]->next[i] != node)
break;
update[i]->next[i] = node->next[i];
}
destroy_node(node);
while (level > 0 && !head->next[level])
--level;
return true;
}
return false;
}
private:
struct Node
{
T value;
struct Node** next;
};
Node* create_node(int level, const T& new_value)
{
void* node_mem = malloc(sizeof(Node));
Node* new_node = static_cast<Node*>(node_mem);
new (&new_node->value) T(new_value);
void* next_mem = calloc(level+1, sizeof(Node*));
new_node->next = static_cast<Node**>(next_mem);
return new_node;
}
void destroy_node(Node* node)
{
node->value.~T();
free(node->next);
free(node);
}
Node* head;
int level;
};
template <class T>
bool contains(const std::set<T>& cont, const T& val)
{
return cont.find(val) != cont.end();
}
template <class T>
bool contains(const SkipSet<T>& cont, const T& val)
{
return cont.contains(val);
}
template <class Set, class T>
void benchmark(int num, const T* elements, const T* search_elements)
{
const double start_insert = sys_time();
Set element_set;
for (int j=0; j < num; ++j)
element_set.insert(elements[j]);
cout << "-- Inserted " << num << " elements in " << (sys_time() - start_insert) << " secs" << endl;
const double start_search = sys_time();
int num_found = 0;
for (int j=0; j < num; ++j)
{
if (contains(element_set, search_elements[j]))
++num_found;
}
cout << "-- Found " << num_found << " elements in " << (sys_time() - start_search) << " secs" << endl;
const double start_erase = sys_time();
int num_erased = 0;
for (int j=0; j < num; ++j)
{
if (element_set.erase(search_elements[j]))
++num_erased;
}
cout << "-- Erased " << num_found << " elements in " << (sys_time() - start_erase) << " secs" << endl;
}
int main()
{
const int num_elements = 200000;
vector<int> elements(num_elements);
for (int j=0; j < num_elements; ++j)
elements[j] = j;
random_shuffle(elements.begin(), elements.end());
vector<int> search_elements = elements;
random_shuffle(search_elements.begin(), search_elements.end());
typedef std::set<int> Set1;
typedef SkipSet<int> Set2;
for (int j=0; j < 3; ++j)
{
cout << "std::set" << endl;
benchmark<Set1>(num_elements, &elements[0], &search_elements[0]);
cout << endl;
cout << "SkipSet" << endl;
benchmark<Set2>(num_elements, &elements[0], &search_elements[0]);
cout << endl;
}
}
在 GCC 5.2 上，-O2，我得到这个：
std::set
-- Inserted 200000 elements in 0.104869 secs
-- Found 200000 elements in 0.078351 secs
-- Erased 200000 elements in 0.098208 secs
SkipSet
-- Inserted 200000 elements in 0.188765 secs
-- Found 200000 elements in 0.160895 secs
-- Erased 200000 elements in 0.162444 secs
...这太糟糕了。我们的整体速度大约是原来的两倍。
优化
然而，我们可以进行明显的优化。如果我们查看 Node，其当前字段如下所示：
struct Node
{
T value;
struct Node** next;
};
这意味着节点字段的内存及其下一个指针列表是两个独立的块，它们之间的步幅可能很远，如下所示：
[Node fields]-------------------->[next0,next1,...,null]
这对于引用的位置来说效果不佳。如果我们想改进这里的东西，我们应该将这些内存块合并成一个连续的结构，像这样：
[Node fields,next0,next1,...,null]
我们可以通过C中常见的变长struct惯用语来实现。在C++中实现起来有点笨拙，不直接支持它，但我们可以模拟这样的效果：
struct Node
{
T value;
struct Node* next[1];
};
Node* create_node(int level, const T& new_value)
{
void* node_mem = malloc(sizeof(Node) + level * sizeof(Node*));
Node* new_node = static_cast<Node*>(node_mem);
new (&new_node->value) T(new_value);
for (int j=0; j < level+1; ++j)
new_node->next[j] = 0;
return new_node;
}
void destroy_node(Node* node)
{
node->value.~T();
free(node);
}
通过这个适度的调整，我们现在有这些时间：
SkipSet (Before)
-- Inserted 200000 elements in 0.188765 secs
-- Found 200000 elements in 0.160895 secs
-- Erased 200000 elements in 0.162444 secs
SkipSet (After)
-- Inserted 200000 elements in 0.132322 secs
-- Found 200000 elements in 0.127989 secs
-- Erased 200000 elements in 0.130889 secs
... 这让我们更接近 std::set.
的表现
随机数生成器
真正高效的跳跃列表实现通常需要非常快的 RNG。尽管如此，我在快速分析过程中发现，只有非常少的时间用于生成随机 level/height，几乎不足以将其视为热点。它也只会影响插入时间，除非它提供更均匀的分布，所以我决定跳过这个优化。
内存分配器
在这一点上，我想说我们对跳过列表实现与 BST 的期望有一个相当合理的概述：
Insertion
-- std::set: 0.104869 secs
-- SkipList: 0.132322 secs
Search:
-- std::set: 0.078351 secs
-- SkipList: 0.127989 secs
Removal:
-- std::set: 0.098208 secs
-- SkipList: 0.130889 secs
但是，如果我们想更进一步，我们可以使用固定分配器。在这一点上，我们有点作弊，因为 std::set 旨在与任何符合标准分配器接口要求的通用分配器一起使用。但是让我们看看使用固定分配器：
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <cassert>
#include <set>
using namespace std;
static const int max_level = 32;
class FixedAlloc
{
public:
FixedAlloc(): root_block(0), free_element(0), type_size(0), block_size(0), block_num(0)
{
}
FixedAlloc(int itype_size, int iblock_size): root_block(0), free_element(0), type_size(0), block_size(0), block_num(0)
{
init(itype_size, iblock_size);
}
~FixedAlloc()
{
purge();
}
void init(int new_type_size, int new_block_size)
{
purge();
block_size = max(new_block_size, type_size);
type_size = max(new_type_size, static_cast<int>(sizeof(FreeElement)));
block_num = block_size / type_size;
}
void purge()
{
while (root_block)
{
Block* block = root_block;
root_block = root_block->next;
free(block);
}
free_element = 0;
}
void* allocate()
{
assert(type_size > 0);
if (free_element)
{
void* mem = free_element;
free_element = free_element->next_element;
return mem;
}
// Create new block.
void* new_block_mem = malloc(sizeof(Block) - 1 + type_size * block_num);
Block* new_block = static_cast<Block*>(new_block_mem);
new_block->next = root_block;
root_block = new_block;
// Push all but one of the new block's elements to the free pool.
char* mem = new_block->mem;
for (int j=1; j < block_num; ++j)
{
FreeElement* element = reinterpret_cast<FreeElement*>(mem + j * type_size);
element->next_element = free_element;
free_element = element;
}
return mem;
}
void deallocate(void* mem)
{
FreeElement* element = static_cast<FreeElement*>(mem);
element->next_element = free_element;
free_element = element;
}
void swap(FixedAlloc& other)
{
std::swap(free_element, other.free_element);
std::swap(root_block, other.root_block);
std::swap(type_size, other.type_size);
std::swap(block_size, other.block_size);
std::swap(block_num, other.block_num);
}
private:
struct Block
{
Block* next;
char mem[1];
};
struct FreeElement
{
struct FreeElement* next_element;
};
// Disable copying.
FixedAlloc(const FixedAlloc&);
FixedAlloc& operator=(const FixedAlloc&);
struct Block* root_block;
struct FreeElement* free_element;
int type_size;
int block_size;
int block_num;
};
static double sys_time()
{
return static_cast<double>(clock()) / CLOCKS_PER_SEC;
}
static int random_level()
{
int lvl = 1;
while (rand()%2 == 0 && lvl < max_level)
++lvl;
return lvl;
}
template <class T>
class SkipSet
{
public:
SkipSet(): head(0)
{
for (int j=0; j < max_level; ++j)
allocs[j].init(sizeof(Node) + (j+1)*sizeof(Node*), 4096);
head = create_node(max_level, T());
level = 0;
}
~SkipSet()
{
while (head)
{
Node* to_destroy = head;
head = head->next[0];
destroy_node(to_destroy);
}
}
bool contains(const T& value) const
{
const Node* node = head;
for (int i=level; i >= 0; --i)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
}
node = node->next[0];
return node && node->value == value;
}
void insert(const T& value)
{
Node* node = head;
Node* update[max_level + 1] = {0};
for (int i=level; i >= 0; --i)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
update[i] = node;
}
node = node->next[0];
if (!node || node->value != value)
{
const int lvl = random_level();
assert(lvl >= 0);
if (lvl > level)
{
for (int i = level + 1; i <= lvl; ++i)
update[i] = head;
level = lvl;
}
node = create_node(lvl, value);
for (int i = 0; i <= lvl; ++i)
{
node->next[i] = update[i]->next[i];
update[i]->next[i] = node;
}
}
}
bool erase(const T& value)
{
Node* node = head;
Node* update[max_level + 1] = {0};
for (int i=level; i >= 0; --i)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
update[i] = node;
}
node = node->next[0];
if (node->value == value)
{
for (int i=0; i <= level; ++i) {
if (update[i]->next[i] != node)
break;
update[i]->next[i] = node->next[i];
}
destroy_node(node);
while (level > 0 && !head->next[level])
--level;
return true;
}
return false;
}
void swap(SkipSet<T>& other)
{
for (int j=0; j < max_level; ++j)
allocs[j].swap(other.allocs[j]);
std::swap(head, other.head);
std::swap(level, other.level);
}
private:
struct Node
{
T value;
int num;
struct Node* next[1];
};
Node* create_node(int level, const T& new_value)
{
void* node_mem = allocs[level-1].allocate();
Node* new_node = static_cast<Node*>(node_mem);
new (&new_node->value) T(new_value);
new_node->num = level;
for (int j=0; j < level+1; ++j)
new_node->next[j] = 0;
return new_node;
}
void destroy_node(Node* node)
{
node->value.~T();
allocs[node->num-1].deallocate(node);
}
FixedAlloc allocs[max_level];
Node* head;
int level;
};
template <class T>
bool contains(const std::set<T>& cont, const T& val)
{
return cont.find(val) != cont.end();
}
template <class T>
bool contains(const SkipSet<T>& cont, const T& val)
{
return cont.contains(val);
}
template <class Set, class T>
void benchmark(int num, const T* elements, const T* search_elements)
{
const double start_insert = sys_time();
Set element_set;
for (int j=0; j < num; ++j)
element_set.insert(elements[j]);
cout << "-- Inserted " << num << " elements in " << (sys_time() - start_insert) << " secs" << endl;
const double start_search = sys_time();
int num_found = 0;
for (int j=0; j < num; ++j)
{
if (contains(element_set, search_elements[j]))
++num_found;
}
cout << "-- Found " << num_found << " elements in " << (sys_time() - start_search) << " secs" << endl;
const double start_erase = sys_time();
int num_erased = 0;
for (int j=0; j < num; ++j)
{
if (element_set.erase(search_elements[j]))
++num_erased;
}
cout << "-- Erased " << num_found << " elements in " << (sys_time() - start_erase) << " secs" << endl;
}
int main()
{
const int num_elements = 200000;
vector<int> elements(num_elements);
for (int j=0; j < num_elements; ++j)
elements[j] = j;
random_shuffle(elements.begin(), elements.end());
vector<int> search_elements = elements;
random_shuffle(search_elements.begin(), search_elements.end());
typedef std::set<int> Set1;
typedef SkipSet<int> Set2;
cout << fixed << setprecision(3);
for (int j=0; j < 2; ++j)
{
cout << "std::set" << endl;
benchmark<Set1>(num_elements, &elements[0], &search_elements[0]);
cout << endl;
cout << "SkipSet" << endl;
benchmark<Set2>(num_elements, &elements[0], &search_elements[0]);
cout << endl;
}
}
* 我还对 random_level 做了一个小调整，在发现这似乎工作得很好之后让它简单地假设概率为 50%。
通过使用固定分配器，我们可以使用非常简单的恒定时间策略快速分配和释放元素，更重要的是，分配节点的方式使得具有相同高度的节点（最常访问的一起）相对于彼此更连续地分配（尽管不是以理想的顺序排列）。这将时间提高到：
Insertion
-- std::set: 0.104869 secs
-- SkipList: 0.103632 secs
Search:
-- std::set: 0.078351 secs
-- SkipList: 0.089910 secs
Removal:
-- std::set: 0.098208 secs
-- SkipList: 0.089224 secs
... 这对于 std::set 的大约 40 分钟的工作来说还不错，它已经被整个行业的专家戳、戳和调整。我们的删除速度也比 std::set 快（插入时间在我的机器上略有波动，我想说它们大致相当）。
当然我们欺骗了最后一步。使用自定义分配器会使事情向对我们有利的方向倾斜，并且还会以某种方式改变容器的特性，使其内存在被清除、销毁或压缩之前无法释放。它可以将内存标记为未使用并在后续插入时回收它，但它不能使它使用的内存可供跳跃列表之外的人使用。我也懒得注意所有可能类型的正确对齐T，这对于真正概括它是必要的。
排序输入
让我们尝试将其用于已排序的输入。为此，只需注释掉两个 random_shuffle 语句即可。在我这边，我现在得到这些时间：
std::set
-- Inserted 200000 elements in 0.044 secs
-- Found 200000 elements in 0.023 secs
-- Erased 200000 elements in 0.019 secs
SkipSet
-- Inserted 200000 elements in 0.027 secs
-- Found 200000 elements in 0.023 secs
-- Erased 200000 elements in 0.016 secs
... 现在我们的 SkipSet 在所有方面都优于 std::set，尽管只是针对这种特殊情况。
结论
所以我不知道这对跳过列表到底说了什么。几乎没有任何时间和精力，我们已经非常接近竞争对手 std::set*。然而我们没有打败它，我们不得不用内存分配器作弊才能真正接近。
* 请注意，里程可能因机器、std::set 的供应商实施等而异。
自 Pugh 于 1989 年发表论文以来，时代发生了很大变化。
如今，引用局部性的优势占据主导地位，以至于即使是线性复杂度算法也可以胜过线性复杂度算法，前提是前者对缓存或页面更友好。密切关注系统从内存层次结构的较高级别（例如：二级阶段）获取内存块的方式，内存较慢但内存更大，向下到小的 L1 缓存行和极小的寄存器比以往任何时候都更重要，并且如果你问我什么时候好处可以与算法改进相媲美，就不再是“微观”了。
考虑到节点的大小相当大，而且同样重要的是，节点的大小可变（这使得它们难以非常有效地分配），这里的跳过列表可能会被削弱。
我们没有看到的一件事是跳跃列表在插入时更新的本地化性质。这往往会影响比平衡树需要通过旋转父节点重新平衡的区域少得多的区域。因此，跳过列表可以提供一种可能更有效的并发集或映射实现。
跳表的另一个有前途的特性是它只是一个最低级别的链表。因此，它提供了非常简单的线性时间顺序遍历，而不必沿着具有线性对数复杂度的树的分支下降，因此如果我们想对包含的所有元素进行大量线性时间迭代，它可能非常好.
但永远记住：
技术能用在实施者手中，才是好的。
即使在 1989 年，我也怀疑跳跃列表是否是比例如 AVL 树更好的选择。在 1989 年或 1990 年，作为一名学生，我实现了两者：它不是跳跃列表的良好实现，我必须承认，那时候我还是个新手
然而，AVL 树不再难以实现。
相比之下，我在模块 2 中实现的 skip in list 的可变长度前向指针遇到了困难，我 primitivley 解决了这个问题，总是使用最多 16 个 next 指针。
插入操作少的好处，没见过。 AVL 树，如果我没记错的话，平均不超过 2-3 次操作。所以昂贵的再平衡并不经常发生。
我认为这更像是一种炒作。
我正在尝试使用最小的额外内存开销实现一个与 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 cur_node;
if(cur_node->next_node[lvl] == nullptr || cur_node->next_node[lvl]->value>p_val){
if(lvl==0) return nullptr;
return find_impl(cur_node,p_val,lvl-1);
}
return find_impl(cur_node->next_node[lvl],p_val,lvl);
}
sl_node* find(long p_val)
{
return find_impl(head,p_val,max_level-1);
}
A sl_node - 跳过列表节点 - 看起来像这样：
struct sl_node
{
long value;
short lvl;
sl_node** next_node;
sl_node(int l) : lvl(l)
{
next_node = new sl_node*[l];
for(short i{0};i<l;i++)
next_node[i]=nullptr;
}
~sl_node()
{
delete[] next_node;
}
};
如您所见，与书中的实现相比，此实现没有任何特别或高级之处，我不会分享 Balaced BTS 代码，因为我认为这里不需要，但它是一个非常基本的 BTS，具有当新节点高度大于 16*lg(n) 其中 n 是节点数时，在插入期间触发重新平衡函数。
也就是说，只有当最大高度比最好的理论高度大 16 倍时，我才重新平衡这三个，正如我所说，这个简单的自制 BST 比自制的 Skip List 表现得更好。
但首先，让我们看一些数据，使用 p=.5 和 n=262144，SkipList 中节点的级别具有以下分布：
1:141439, 53.9547%
2:65153, 24.8539%
3:30119, 11.4895%
4:13703, 5.22728%
5:6363, 2.42729%
6:2895, 1.10435%
7:1374, 0.524139%
8:581, 0.221634%
9:283, 0.107956%
10:117, 0.044632%
11:64, 0.0244141%
12:31, 0.0118256%
13:11, 0.00419617%
14:5, 0.00190735%
15:1, 0.00038147%
16:5, 0.00190735%
这几乎完美 - 哦，这是一个很大的！ - 符合文章中的理论，即：50% 级别 1，25% 级别 2 等等。输入数据来自我最好的可用伪随机数生成器，又名 std::random_device，具有 std::default_random_engine 和统一的 int 分布。输入对我来说看起来很随机 :) !
在我的机器上以随机顺序搜索 'all' SkipList 中的 262144 个元素所需的时间是 315 毫秒，而在 naive BTS 上进行相同的搜索操作所需的时间是 134 毫秒，所以BTS 几乎比 SkipList 快两倍。这不是我对 "Skip list algoriths have the same asymptotic expected time bounds as balanced trees and are simple, faster and use less space" PUG89.
的期望节点 'insertion' 所需的时间对于 SkipList 是 387 毫秒，对于 BTS 是 143 毫秒，再一次，朴素的 BST 表现更好。
如果我不使用输入数字的随机序列而是使用排序序列，事情会变得更有趣，这里我可怜的自制 BST 变慢了，插入 262144 个排序的 int 需要 2866 毫秒，而 SkipList 只需要 168 毫秒.
但是，到了搜索的时候，BST还是更快！对于排序后的输入，我们有 234 毫秒和 77 毫秒，这个 BST 快了 3 倍。
使用不同的 p 因子值，我得到的性能结果略有不同：
最后但并非最不重要的是，内存使用图，如您所料，它确认如果我们增加每个节点的级别数量，我们会显着影响内存指纹。内存使用量计算为存储所有节点的附加指针所需的 space 总和。
毕竟，你们中的任何人都可以就如何实现与 BTS 一样好的 SkipList 提供评论 - 不计算额外的内存开销 - 吗？
我知道 DrDobbs LINK 关于 SkipList 的文章，我浏览了所有论文，搜索和插入操作的代码与原始代码完全匹配PUG89 的实现应该和我的一样好，而且这篇文章没有提供任何性能分析，我没有找到任何其他来源。你能帮帮我吗？
非常感谢任何评论！
谢谢！ :)
历史
自 William Pugh 撰写他的原始论文以来，时代发生了一些变化。我们在他的论文中没有提到 CPU 和操作系统的内存层次结构，这已成为当今如此普遍的焦点（现在通常与算法复杂性同等重要）。
他的基准测试输入案例只有区区 2^16 个元素，而当时的硬件通常最多只有 32 位扩展内存寻址可用。这使得指针的大小只有我们今天在 64 位机器上使用的指针大小的一半或更小。同时，例如，字符串字段可能同样大，使得存储在跳跃列表中的元素与跳跃节点所需的指针之间的比率可能小得多，特别是考虑到我们经常需要每个跳跃节点的指针数量.
C 编译器当时在寄存器分配和指令选择等方面的优化方面并不那么积极。即使是普通的手写汇编也常常可以在性能上提供显着的好处。像 register 和 inline 这样的编译器提示在那个时候实际上起了很大的作用。虽然这可能看起来有点没有实际意义，因为平衡 BST 和跳跃列表实现在这里都是平等的，但即使是基本循环的优化也是一个更加手动的过程。当优化越来越成为一个手动过程时，更容易实施的东西通常更容易优化。跳表通常被认为比平衡树更容易实现。
因此，所有这些因素都可能影响了 Pugh 当时的结论。然而时代变了：硬件变了，操作系统变了，编译器变了，对这些主题进行了更多研究，等等。
实施
除此之外，让我们找点乐子，实现一个基本的跳过列表。出于懒惰，我最终调整了可用的实现 here。这是一种 运行 普通的实现方式，与当今大量易于访问的示例性跳过列表实现方式几乎没有什么不同。
我们会将我们的实现的性能与几乎总是作为红黑树实现的 std::set 进行比较*。
* 有些人可能想知道为什么我使用 0 而不是 nullptr 之类的东西。这是一种习惯。在我的工作场所，我们仍然必须编写针对各种编译器的开放库，包括那些只支持 C++03 的编译器，所以我仍然习惯于以这种方式编写 lower/mid-level 实现代码，有时甚至在C，所以请原谅我写这段代码的旧风格。
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
using namespace std;
static const int max_level = 32;
static const float probability = 0.5;
static double sys_time()
{
return static_cast<double>(clock()) / CLOCKS_PER_SEC;
}
static int random_level()
{
int lvl = 1;
while ((static_cast<float>(rand()) / RAND_MAX) < probability && lvl < max_level)
++lvl;
return lvl;
}
template <class T>
class SkipSet
{
public:
SkipSet(): head(0)
{
head = create_node(max_level, T());
level = 0;
}
~SkipSet()
{
while (head)
{
Node* to_destroy = head;
head = head->next[0];
destroy_node(to_destroy);
}
}
bool contains(const T& value) const
{
const Node* node = head;
for (int i=level; i >= 0; --i)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
}
node = node->next[0];
return node && node->value == value;
}
void insert(const T& value)
{
Node* node = head;
Node* update[max_level + 1];
memset(update, 0, sizeof(Node*)*(max_level + 1));
for (int i = level; i >= 0; i--)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
update[i] = node;
}
node = node->next[0];
if (!node || node->value != value)
{
int lvl = random_level();
assert(lvl >= 0);
if (lvl > level)
{
for (int i = level + 1; i <= lvl; i++) {
update[i] = head;
}
level = lvl;
}
node = create_node(lvl, value);
for (int i = 0; i <= lvl; i++) {
node->next[i] = update[i]->next[i];
update[i]->next[i] = node;
}
}
}
bool erase(const T& value)
{
Node* node = head;
Node* update[max_level + 1];
memset(update, 0, sizeof(Node*)*(max_level + 1));
for (int i = level; i >= 0; i--)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
update[i] = node;
}
node = node->next[0];
if (node->value == value)
{
for (int i = 0; i <= level; i++) {
if (update[i]->next[i] != node)
break;
update[i]->next[i] = node->next[i];
}
destroy_node(node);
while (level > 0 && !head->next[level])
--level;
return true;
}
return false;
}
private:
struct Node
{
T value;
struct Node** next;
};
Node* create_node(int level, const T& new_value)
{
void* node_mem = malloc(sizeof(Node));
Node* new_node = static_cast<Node*>(node_mem);
new (&new_node->value) T(new_value);
void* next_mem = calloc(level+1, sizeof(Node*));
new_node->next = static_cast<Node**>(next_mem);
return new_node;
}
void destroy_node(Node* node)
{
node->value.~T();
free(node->next);
free(node);
}
Node* head;
int level;
};
template <class T>
bool contains(const std::set<T>& cont, const T& val)
{
return cont.find(val) != cont.end();
}
template <class T>
bool contains(const SkipSet<T>& cont, const T& val)
{
return cont.contains(val);
}
template <class Set, class T>
void benchmark(int num, const T* elements, const T* search_elements)
{
const double start_insert = sys_time();
Set element_set;
for (int j=0; j < num; ++j)
element_set.insert(elements[j]);
cout << "-- Inserted " << num << " elements in " << (sys_time() - start_insert) << " secs" << endl;
const double start_search = sys_time();
int num_found = 0;
for (int j=0; j < num; ++j)
{
if (contains(element_set, search_elements[j]))
++num_found;
}
cout << "-- Found " << num_found << " elements in " << (sys_time() - start_search) << " secs" << endl;
const double start_erase = sys_time();
int num_erased = 0;
for (int j=0; j < num; ++j)
{
if (element_set.erase(search_elements[j]))
++num_erased;
}
cout << "-- Erased " << num_found << " elements in " << (sys_time() - start_erase) << " secs" << endl;
}
int main()
{
const int num_elements = 200000;
vector<int> elements(num_elements);
for (int j=0; j < num_elements; ++j)
elements[j] = j;
random_shuffle(elements.begin(), elements.end());
vector<int> search_elements = elements;
random_shuffle(search_elements.begin(), search_elements.end());
typedef std::set<int> Set1;
typedef SkipSet<int> Set2;
for (int j=0; j < 3; ++j)
{
cout << "std::set" << endl;
benchmark<Set1>(num_elements, &elements[0], &search_elements[0]);
cout << endl;
cout << "SkipSet" << endl;
benchmark<Set2>(num_elements, &elements[0], &search_elements[0]);
cout << endl;
}
}
在 GCC 5.2 上，-O2，我得到这个：
std::set
-- Inserted 200000 elements in 0.104869 secs
-- Found 200000 elements in 0.078351 secs
-- Erased 200000 elements in 0.098208 secs
SkipSet
-- Inserted 200000 elements in 0.188765 secs
-- Found 200000 elements in 0.160895 secs
-- Erased 200000 elements in 0.162444 secs
...这太糟糕了。我们的整体速度大约是原来的两倍。
优化
然而，我们可以进行明显的优化。如果我们查看 Node，其当前字段如下所示：
struct Node
{
T value;
struct Node** next;
};
这意味着节点字段的内存及其下一个指针列表是两个独立的块，它们之间的步幅可能很远，如下所示：
[Node fields]-------------------->[next0,next1,...,null]
这对于引用的位置来说效果不佳。如果我们想改进这里的东西，我们应该将这些内存块合并成一个连续的结构，像这样：
[Node fields,next0,next1,...,null]
我们可以通过C中常见的变长struct惯用语来实现。在C++中实现起来有点笨拙，不直接支持它，但我们可以模拟这样的效果：
struct Node
{
T value;
struct Node* next[1];
};
Node* create_node(int level, const T& new_value)
{
void* node_mem = malloc(sizeof(Node) + level * sizeof(Node*));
Node* new_node = static_cast<Node*>(node_mem);
new (&new_node->value) T(new_value);
for (int j=0; j < level+1; ++j)
new_node->next[j] = 0;
return new_node;
}
void destroy_node(Node* node)
{
node->value.~T();
free(node);
}
通过这个适度的调整，我们现在有这些时间：
SkipSet (Before)
-- Inserted 200000 elements in 0.188765 secs
-- Found 200000 elements in 0.160895 secs
-- Erased 200000 elements in 0.162444 secs
SkipSet (After)
-- Inserted 200000 elements in 0.132322 secs
-- Found 200000 elements in 0.127989 secs
-- Erased 200000 elements in 0.130889 secs
... 这让我们更接近 std::set.
随机数生成器
真正高效的跳跃列表实现通常需要非常快的 RNG。尽管如此，我在快速分析过程中发现，只有非常少的时间用于生成随机 level/height，几乎不足以将其视为热点。它也只会影响插入时间，除非它提供更均匀的分布，所以我决定跳过这个优化。
内存分配器
在这一点上，我想说我们对跳过列表实现与 BST 的期望有一个相当合理的概述：
Insertion
-- std::set: 0.104869 secs
-- SkipList: 0.132322 secs
Search:
-- std::set: 0.078351 secs
-- SkipList: 0.127989 secs
Removal:
-- std::set: 0.098208 secs
-- SkipList: 0.130889 secs
但是，如果我们想更进一步，我们可以使用固定分配器。在这一点上，我们有点作弊，因为 std::set 旨在与任何符合标准分配器接口要求的通用分配器一起使用。但是让我们看看使用固定分配器：
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <cassert>
#include <set>
using namespace std;
static const int max_level = 32;
class FixedAlloc
{
public:
FixedAlloc(): root_block(0), free_element(0), type_size(0), block_size(0), block_num(0)
{
}
FixedAlloc(int itype_size, int iblock_size): root_block(0), free_element(0), type_size(0), block_size(0), block_num(0)
{
init(itype_size, iblock_size);
}
~FixedAlloc()
{
purge();
}
void init(int new_type_size, int new_block_size)
{
purge();
block_size = max(new_block_size, type_size);
type_size = max(new_type_size, static_cast<int>(sizeof(FreeElement)));
block_num = block_size / type_size;
}
void purge()
{
while (root_block)
{
Block* block = root_block;
root_block = root_block->next;
free(block);
}
free_element = 0;
}
void* allocate()
{
assert(type_size > 0);
if (free_element)
{
void* mem = free_element;
free_element = free_element->next_element;
return mem;
}
// Create new block.
void* new_block_mem = malloc(sizeof(Block) - 1 + type_size * block_num);
Block* new_block = static_cast<Block*>(new_block_mem);
new_block->next = root_block;
root_block = new_block;
// Push all but one of the new block's elements to the free pool.
char* mem = new_block->mem;
for (int j=1; j < block_num; ++j)
{
FreeElement* element = reinterpret_cast<FreeElement*>(mem + j * type_size);
element->next_element = free_element;
free_element = element;
}
return mem;
}
void deallocate(void* mem)
{
FreeElement* element = static_cast<FreeElement*>(mem);
element->next_element = free_element;
free_element = element;
}
void swap(FixedAlloc& other)
{
std::swap(free_element, other.free_element);
std::swap(root_block, other.root_block);
std::swap(type_size, other.type_size);
std::swap(block_size, other.block_size);
std::swap(block_num, other.block_num);
}
private:
struct Block
{
Block* next;
char mem[1];
};
struct FreeElement
{
struct FreeElement* next_element;
};
// Disable copying.
FixedAlloc(const FixedAlloc&);
FixedAlloc& operator=(const FixedAlloc&);
struct Block* root_block;
struct FreeElement* free_element;
int type_size;
int block_size;
int block_num;
};
static double sys_time()
{
return static_cast<double>(clock()) / CLOCKS_PER_SEC;
}
static int random_level()
{
int lvl = 1;
while (rand()%2 == 0 && lvl < max_level)
++lvl;
return lvl;
}
template <class T>
class SkipSet
{
public:
SkipSet(): head(0)
{
for (int j=0; j < max_level; ++j)
allocs[j].init(sizeof(Node) + (j+1)*sizeof(Node*), 4096);
head = create_node(max_level, T());
level = 0;
}
~SkipSet()
{
while (head)
{
Node* to_destroy = head;
head = head->next[0];
destroy_node(to_destroy);
}
}
bool contains(const T& value) const
{
const Node* node = head;
for (int i=level; i >= 0; --i)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
}
node = node->next[0];
return node && node->value == value;
}
void insert(const T& value)
{
Node* node = head;
Node* update[max_level + 1] = {0};
for (int i=level; i >= 0; --i)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
update[i] = node;
}
node = node->next[0];
if (!node || node->value != value)
{
const int lvl = random_level();
assert(lvl >= 0);
if (lvl > level)
{
for (int i = level + 1; i <= lvl; ++i)
update[i] = head;
level = lvl;
}
node = create_node(lvl, value);
for (int i = 0; i <= lvl; ++i)
{
node->next[i] = update[i]->next[i];
update[i]->next[i] = node;
}
}
}
bool erase(const T& value)
{
Node* node = head;
Node* update[max_level + 1] = {0};
for (int i=level; i >= 0; --i)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
update[i] = node;
}
node = node->next[0];
if (node->value == value)
{
for (int i=0; i <= level; ++i) {
if (update[i]->next[i] != node)
break;
update[i]->next[i] = node->next[i];
}
destroy_node(node);
while (level > 0 && !head->next[level])
--level;
return true;
}
return false;
}
void swap(SkipSet<T>& other)
{
for (int j=0; j < max_level; ++j)
allocs[j].swap(other.allocs[j]);
std::swap(head, other.head);
std::swap(level, other.level);
}
private:
struct Node
{
T value;
int num;
struct Node* next[1];
};
Node* create_node(int level, const T& new_value)
{
void* node_mem = allocs[level-1].allocate();
Node* new_node = static_cast<Node*>(node_mem);
new (&new_node->value) T(new_value);
new_node->num = level;
for (int j=0; j < level+1; ++j)
new_node->next[j] = 0;
return new_node;
}
void destroy_node(Node* node)
{
node->value.~T();
allocs[node->num-1].deallocate(node);
}
FixedAlloc allocs[max_level];
Node* head;
int level;
};
template <class T>
bool contains(const std::set<T>& cont, const T& val)
{
return cont.find(val) != cont.end();
}
template <class T>
bool contains(const SkipSet<T>& cont, const T& val)
{
return cont.contains(val);
}
template <class Set, class T>
void benchmark(int num, const T* elements, const T* search_elements)
{
const double start_insert = sys_time();
Set element_set;
for (int j=0; j < num; ++j)
element_set.insert(elements[j]);
cout << "-- Inserted " << num << " elements in " << (sys_time() - start_insert) << " secs" << endl;
const double start_search = sys_time();
int num_found = 0;
for (int j=0; j < num; ++j)
{
if (contains(element_set, search_elements[j]))
++num_found;
}
cout << "-- Found " << num_found << " elements in " << (sys_time() - start_search) << " secs" << endl;
const double start_erase = sys_time();
int num_erased = 0;
for (int j=0; j < num; ++j)
{
if (element_set.erase(search_elements[j]))
++num_erased;
}
cout << "-- Erased " << num_found << " elements in " << (sys_time() - start_erase) << " secs" << endl;
}
int main()
{
const int num_elements = 200000;
vector<int> elements(num_elements);
for (int j=0; j < num_elements; ++j)
elements[j] = j;
random_shuffle(elements.begin(), elements.end());
vector<int> search_elements = elements;
random_shuffle(search_elements.begin(), search_elements.end());
typedef std::set<int> Set1;
typedef SkipSet<int> Set2;
cout << fixed << setprecision(3);
for (int j=0; j < 2; ++j)
{
cout << "std::set" << endl;
benchmark<Set1>(num_elements, &elements[0], &search_elements[0]);
cout << endl;
cout << "SkipSet" << endl;
benchmark<Set2>(num_elements, &elements[0], &search_elements[0]);
cout << endl;
}
}
* 我还对 random_level 做了一个小调整，在发现这似乎工作得很好之后让它简单地假设概率为 50%。
通过使用固定分配器，我们可以使用非常简单的恒定时间策略快速分配和释放元素，更重要的是，分配节点的方式使得具有相同高度的节点（最常访问的一起）相对于彼此更连续地分配（尽管不是以理想的顺序排列）。这将时间提高到：
Insertion
-- std::set: 0.104869 secs
-- SkipList: 0.103632 secs
Search:
-- std::set: 0.078351 secs
-- SkipList: 0.089910 secs
Removal:
-- std::set: 0.098208 secs
-- SkipList: 0.089224 secs
... 这对于 std::set 的大约 40 分钟的工作来说还不错，它已经被整个行业的专家戳、戳和调整。我们的删除速度也比 std::set 快（插入时间在我的机器上略有波动，我想说它们大致相当）。
当然我们欺骗了最后一步。使用自定义分配器会使事情向对我们有利的方向倾斜，并且还会以某种方式改变容器的特性，使其内存在被清除、销毁或压缩之前无法释放。它可以将内存标记为未使用并在后续插入时回收它，但它不能使它使用的内存可供跳跃列表之外的人使用。我也懒得注意所有可能类型的正确对齐T，这对于真正概括它是必要的。
排序输入
让我们尝试将其用于已排序的输入。为此，只需注释掉两个 random_shuffle 语句即可。在我这边，我现在得到这些时间：
std::set
-- Inserted 200000 elements in 0.044 secs
-- Found 200000 elements in 0.023 secs
-- Erased 200000 elements in 0.019 secs
SkipSet
-- Inserted 200000 elements in 0.027 secs
-- Found 200000 elements in 0.023 secs
-- Erased 200000 elements in 0.016 secs
... 现在我们的 SkipSet 在所有方面都优于 std::set，尽管只是针对这种特殊情况。
结论
所以我不知道这对跳过列表到底说了什么。几乎没有任何时间和精力，我们已经非常接近竞争对手 std::set*。然而我们没有打败它，我们不得不用内存分配器作弊才能真正接近。
* 请注意，里程可能因机器、std::set 的供应商实施等而异。
自 Pugh 于 1989 年发表论文以来，时代发生了很大变化。
如今，引用局部性的优势占据主导地位，以至于即使是线性复杂度算法也可以胜过线性复杂度算法，前提是前者对缓存或页面更友好。密切关注系统从内存层次结构的较高级别（例如：二级阶段）获取内存块的方式，内存较慢但内存更大，向下到小的 L1 缓存行和极小的寄存器比以往任何时候都更重要，并且如果你问我什么时候好处可以与算法改进相媲美，就不再是“微观”了。
考虑到节点的大小相当大，而且同样重要的是，节点的大小可变（这使得它们难以非常有效地分配），这里的跳过列表可能会被削弱。
我们没有看到的一件事是跳跃列表在插入时更新的本地化性质。这往往会影响比平衡树需要通过旋转父节点重新平衡的区域少得多的区域。因此，跳过列表可以提供一种可能更有效的并发集或映射实现。
跳表的另一个有前途的特性是它只是一个最低级别的链表。因此，它提供了非常简单的线性时间顺序遍历，而不必沿着具有线性对数复杂度的树的分支下降，因此如果我们想对包含的所有元素进行大量线性时间迭代，它可能非常好.
但永远记住：
技术能用在实施者手中，才是好的。
即使在 1989 年，我也怀疑跳跃列表是否是比例如 AVL 树更好的选择。在 1989 年或 1990 年，作为一名学生，我实现了两者：它不是跳跃列表的良好实现，我必须承认，那时候我还是个新手
然而，AVL 树不再难以实现。 相比之下，我在模块 2 中实现的 skip in list 的可变长度前向指针遇到了困难，我 primitivley 解决了这个问题，总是使用最多 16 个 next 指针。
插入操作少的好处，没见过。 AVL 树，如果我没记错的话，平均不超过 2-3 次操作。所以昂贵的再平衡并不经常发生。
我认为这更像是一种炒作。