History
自从威廉·皮尤（William Pugh）写出他的原始论文以来，时代已经发生了一些变化。我们在他的论文中没有提到 CPU 和操作系统的内存层次结构，这已成为当今普遍关注的焦点（现在通常与算法复杂性同等重要）。
他的基准测试输入案例只有区区 2^16 个元素，而当时的硬件通常最多只能提供 32 位扩展内存寻址。这使得指针的大小比我们今天在 64 位机器上使用的指针大小减半或更小。同时，例如，字符串字段可能一样大，使得存储在跳跃列表中的元素与跳跃节点所需的指针之间的比率可能小很多，特别是考虑到我们通常每个跳跃节点需要多个指针。
当时，C 编译器在寄存器分配和指令选择等方面的优化并不那么积极。即使是普通的手写程序集通常也可以提供显着的性能优势。编译器提示如下register and inline在那段时间实际上做了一件大事。虽然这看起来有点没有实际意义，因为平衡 BST 和跳跃列表实现在这里是平等的，但即使是基本循环的优化也是一个更加手动的过程。当优化越来越成为一个手动过程时，更容易实施的事情通常也更容易优化。跳跃列表通常被认为比平衡树更容易实现。
因此，所有这些因素可能都影响了皮尤当时的结论。然而时代已经变了：硬件变了，操作系统变了，编译器变了，对这些主题进行了更多的研究，等等。
执行
除此之外，让我们享受一些乐趣并实现一个基本的跳过列表。我最终调整了可用的实现here http://en.literateprograms.org/Skip_list_%28C_Plus_Plus%29出于懒惰。这是一种普通的实现方式，与当今大量易于访问的示例性跳过列表实现方式几乎没有什么不同。
我们将比较我们的实现的性能std::set它几乎总是被实现为红黑树*。
* Some might wonder why I use 0 instead of nullptr and things of that sort. It's a habit. At my workplace, we still have to write open libraries that target a wide range of compilers including those that only support C++03, so I'm still used to writing lower/mid-level implementation code that way, and sometimes even in C, so please forgive the old style in which I wrote this code.
#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 字段的内存及其下一个指针列表是两个单独的块，它们之间可能有非常远的步幅，如下所示：
[Node fields]-------------------->[next0,next1,...,null]
这对于参考位置来说效果很差。如果我们想改进这里的东西，我们应该将这些内存块合并成一个连续的结构，如下所示：
[Node fields,next0,next1,...,null]
我们可以通过 C 中常见的变长结构体习惯来实现这一点。在 C++ 中实现有点尴尬，因为 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。尽管如此，我在快速分析会话中发现，只有极少的时间用于生成随机级别/高度，几乎不足以将其视为热点。它也只会影响插入时间，除非它提供更均匀的分布，所以我决定跳过此优化。
内存分配器
至此，我想说我们对跳跃列表实现与 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;
}
}
* I also made a minor tweak to random_level to make it simply assume a probability of 50% after discovering that this seems to work quite well.
通过使用固定分配器，我们可以使用非常简单的常量时间策略快速分配和释放元素，更重要的是，以某种方式分配节点，使得具有相同高度的节点（最常一起访问的节点）被更连续地分配相互尊重（尽管不是按照理想的顺序）。这将时间缩短为：
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
...这对于大约 40 分钟的对抗来说还不错std::set整个行业的专家都对这个问题进行了探讨和调整。我们的清除速度也比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*。然而我们并没有击败它，我们必须使用内存分配器来作弊才能真正接近它。
* Note that mileage may vary across machines, vendor implementations of std::set, etc.
自 Pugh 1989 年发表论文以来，时代已经发生了很大变化。
如今，引用局部性的好处在很大程度上占据了主导地位，即使是线性复杂度算法也可以胜过线性算法，前提是前者对缓存或页面友好得多。密切关注系统从内存层次结构的上层（例如：二级阶段）获取内存块的方式，内存速度较慢但更大，一直到小型 L1 高速缓存线和小型寄存器，这比以往任何时候都更重要，并且如果你问我什么时候带来的好处可以与算法改进相媲美，那么不再是“微观”。
考虑到节点的大小相当大，而且同样重要的是，节点的大小可变（这使得它们很难非常有效地分配），因此跳跃列表可能会被削弱。
我们没有考虑的一件事是跳跃列表在插入时更新的本地化性质。这往往会影响比平衡树通过旋转父节点重新平衡所需的区域少得多的区域。因此，跳跃列表可以提供并发集或映射的潜在更有效的实现。
跳跃列表的另一个有前途的特性是它只是一个最低级别的链接列表。因此，它提供了非常简单的线性时间顺序遍历，而不必以线性复杂度沿着树的分支下降，因此如果我们想要对包含的所有元素进行大量线性时间迭代，那么它可能非常好。
但永远记住：
一项技术只有能够应用到实施者手中才算好。
