歴史
William Pugh が最初の論文を書いてから、時代は少し変わりました。彼の論文では、今日広く注目されている CPU とオペレーティング システムのメモリ階層については言及されていません (現在では、アルゴリズムの複雑さと同じくらい重要な場合が多い)。
ベンチマーク用の彼の入力ケースにはわずか 2^16 の要素があり、当時のハードウェアでは通常、最大で 32 ビットの拡張メモリ アドレッシングが利用可能でした。これにより、ポインターのサイズは、現在の 64 ビット マシンで使用されているサイズの半分以下になりました。一方、文字列フィールドは、たとえば、スキップ リストに格納されている要素とスキップ ノードに必要なポインタとの比率を同じくらい大きくすることができます。特に、スキップ ノードごとに多数のポインタが必要になることが多いことを考えると、 .
当時の C コンパイラは、レジスタの割り当てや命令の選択などに関して、それほど積極的な最適化を行っていませんでした。平均的な手書きのアセンブリでも、多くの場合、パフォーマンスが大幅に向上します。コンパイラーは、当時のようregisterに、inline実際に大したことを示唆しています。バランスの取れた BST とスキップ リストの実装はどちらも対等な立場にあるため、これはちょっと意味がないように思えるかもしれませんが、基本的なループの最適化でさえ、より手作業のプロセスでした。最適化がますます手作業のプロセスになると、実装が容易なものは最適化も容易になることがよくあります。多くの場合、スキップ リストはバランシング ツリーよりも実装がはるかに簡単であると考えられています。
したがって、これらすべての要因が、当時のピューの結論に関与していた可能性があります。しかし、時代は変わりました。ハードウェアが変わり、オペレーティング システムが変わり、コンパイラが変わり、これらのトピックについてより多くの研究が行われるようになったなどです。
実装
それはさておき、楽しみながら基本的なスキップ リストを実装しましょう。私は怠惰からここで利用可能な実装を適応させることになりました。これはありきたりの実装であり、今日出回っている、簡単にアクセスできる模範的なスキップ リスト実装の過多とほとんど変わりません。
私たちの実装のパフォーマンスを、std::setほぼ常に赤黒ツリーとして実装されているものと比較します*。
* なぜ私が0代わりにnullptrand を使うのか不思議に思う人もいるかもしれません。それは習慣です。私の職場では、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
...これはかなりひどいです。全体的に約 2 倍遅くなります。
最適化
しかし、私たちができる明白な最適化があります。を見るとNode、現在のフィールドは次のようになります。
struct Node
{
T value;
struct Node** next;
};
これは、Node フィールドのメモリとその次のポインターのリストが 2 つの別個のブロックであり、次のように非常に離れている可能性があることを意味します。
[Node fields]-------------------->[next0,next1,...,null]
これは、参照の局所性には不十分です。ここを改善したい場合は、次のように、これらのメモリ ブロックを 1 つの連続した構造にマージする必要があります。
[Node fields,next0,next1,...,null]
これは、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;
}
}
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これを行うには、2 つのステートメントをコメントアウトするだけです。私の側では、次の時間が得られます。
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
...そして今では、この 1 種類の例外的なケースだけではありますが、すべての分野でSkipSet優れています。std::set
結論
したがって、これがスキップリストについて何を言っているのか正確にはわかりません。ほとんど時間と労力をかけずに、ライバルにかなり近づきましたstd::set*。それでも、私たちはそれを打ち負かすことはできませんでした。実際に近づけるために、メモリ アロケーターをいじる必要がありました。
* 走行距離は、マシン、ベンダーの実装std::setなどによって異なる場合があることに注意してください。
ピューが 1989 年に書いた論文から、時代はかなり変わりました。
今日では、参照の局所性の利点が優勢であり、線形複雑性アルゴリズムでさえも線形アルゴリズムよりも優れたパフォーマンスを発揮することができます。システムがメモリ階層の上位レベル (例: セカンダリ ステージ) からメモリのチャンクを取得する方法に細心の注意を払うことは、低速ではあるがより大きなメモリを使用して、小さな L1 キャッシュ ラインと小さなレジスタに至るまで、これまで以上に重要なことです。利点がいつアルゴリズムの改善に匹敵するかを私に尋ねた場合、もはや「マイクロ」ではありません。
ここでは、ノードのサイズがかなり大きく、ノードの可変サイズ (非常に効率的に割り当てることが難しくなっています) を考えると、スキップ リストが機能しなくなる可能性があります。
私たちが見ていないことの 1 つは、挿入時にスキップ リストが更新されるローカライズされた性質です。これは、バランシング ツリーが親ノードをローテーションして再調整する必要がある場合よりも、はるかに少ない領域に影響を与える傾向があります。その結果、スキップ リストは、並行セットまたはマップの潜在的により効率的な実装を提供できます。
スキップ リストのもう 1 つの有望な特徴は、最下位レベルの単純なリンク リストであることです。その結果、線形の複雑さでツリーの枝を下る必要なく、非常に単純な線形時系列トラバーサルを提供するため、含まれるすべての要素に対して多くの線形時間反復を実行したい場合に非常に優れている可能性があります。 .
しかし、常に覚えておいてください：
技術は、実装者の手で適用できるほど優れています。
