历史
自从 William Pugh 写下他的原始论文以来，时代已经发生了一些变化。我们在他的论文中没有提到 CPU 和操作系统的内存层次结构，这已成为当今如此普遍的焦点（现在通常与算法复杂性同等重要）。
他的基准测试输入案例只有区区 2^16 个元素，而当时的硬件通常最多只有 32 位扩展内存寻址可用。这使得指针的大小比我们今天在 64 位机器上使用的大小减少一半或更小。同时，例如，一个字符串字段可能同样大，这使得存储在跳过列表中的元素与跳过节点所需的指针之间的比率可能要小得多，特别是考虑到我们通常需要每个跳过节点的多个指针.
那时，C 编译器在寄存器分配和指令选择等方面的优化并不那么激进。即使是普通的手写汇编通常也可以在性能方面提供显着优势。在那些时候，编译器的提示就像register并且inline实际上做了一件大事。虽然这似乎有点没有意义，因为平衡的 BST 和跳过列表实现在这里都是平等的，但即使是基本循环的优化也是一个更加手动的过程。当优化是一个越来越手动的过程时，更容易实现的东西通常更容易优化。跳过列表通常被认为比平衡树更容易实现。
因此，所有这些因素都可能在当时 Pugh 的结论中发挥了作用。然而时代已经变了：硬件变了，操作系统变了，编译器变了，对这些主题进行了更多的研究，等等。
执行
除此之外，让我们玩得开心并实现一个基本的跳过列表。出于懒惰，我最终调整了这里可用的实现。这是一种普通的实现，与当今大量易于访问的示例性跳过列表实现几乎没有什么不同。
我们将比较我们的实现的性能与std::set几乎总是作为红黑树实现的性能*。
* 有些人可能想知道为什么我使用0而不是nullptr和那种东西。这是一种习惯。在我的工作场所，我们仍然必须编写针对各种编译器的开放库，包括仅支持 C++03 的编译器，所以我仍然习惯于以这种方式编写低/中级实现代码，有时甚至在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 字段的内存及其下一个指针列表是两个独立的块，它们之间的步幅可能很远，如下所示：
[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。尽管如此，我在一次快速分析会议中发现，只有很少一部分时间用于生成随机级别/高度，这不足以将其视为热点。它也只会影响插入时间，除非它提供更均匀的分布，所以我决定跳过这个优化。
内存分配器
在这一点上，我想说我们对跳过列表实现与 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
... 这对于大约 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*. 然而我们没有打败它，我们不得不用内存分配器作弊才能真正接近。
* 请注意，里程可能因机器、供应商实施std::set等而异。
自 1989 年 Pugh 撰写论文以来，时代已经发生了很大变化。
今天，引用局部性的好处占据了主导地位，即使线性复杂度算法也可以胜过线性算法，前提是前者对缓存或页面友好得多。密切关注系统从内存层次结构的上层（例如：二级）抓取内存块的方式，内存较慢但更大，一直到 L1 缓存线和极小的寄存器，这比以往任何时候都更重要，并且如果你问我什么时候好处可以与算法改进相媲美，不再是“微”。
考虑到节点的大小相当大，并且同样重要的是节点的可变大小（这使得它们难以非常有效地分配），跳过列表在这里可能会被削弱。
我们没有看到的一件事是跳过列表在插入时更新的本地化性质。与平衡树通过旋转父节点重新平衡所需的区域相比，这往往会影响更少的区域。因此，跳过列表可以提供潜在的更有效的并发集合或映射实现。
跳过列表的另一个有希望的特性是它只是一个最低级别的链表。结果，它提供了非常简单的线性时间顺序遍历，而不必沿着具有线性复杂度的树的分支下降，因此如果我们想要对包含的所有元素进行大量线性时间迭代，它可能非常好.
但永远记住：
一种技术只有在实施者手中能被应用时才好。
