拡張リンクリスト: 必須ガイド

リンクリストはどのように機能しますか?

リンク リストは、各データのフィールドがオフセットではなくポインターによって接続されるデータ構造です。これは、必要なすべてのユーザー フィールド (電話、所有者、会社など) と次のノードへのポインターを含む、最初と最後の要素 (いわゆるノード要素) を格納するメイン要素で構成されます。最後の要素は、リストの終わりを示す NULL フィールドにリンクされます。

リンク リストに新しい要素が追加されると、メイン ノードは「末尾」ポインタを新しいエンド ノードに更新し、以前の NULL ポインタを新しい末尾に更新する必要があります。

このデータ構造により、配列全体のサイズを変更せずに新しいデータを効率的に記録できます。これは書き込み専用データを保存するのに効果的な方法で、要素の数を事前に知る必要がありません。これは単純なデータ構造で、メモリ内では次のようになります。

削除キーのリンクリスト

以前の記事では、各項目の削除後にツリーを離れることなくツリーをスキャンするためのバッファの必要性について説明しました。GC を備えた言語では、これは問題になりません。ただし、アプリケーション コードがメモリを管理する場合は、古い要素を含むリンク リストに基づくバッファが解決策になる場合があります。

リンク リストを使用すると、要素をすばやく追加できます。ただし、リンク リスト内の何かを検索するには順次スキャンが必要なので、キーをすばやく取得するには適していません。したがって、データのログ記録、一時バッファーの作成、ヘッド ノードからの順次読み取りを行うためのデータの整理には、リンク リストは効率的なソリューションです。

プリエンプトする要素を見つけることは、このようなタスクの一例です。プリエンプトは、さまざまなキャッシュ実装でよく使用されます。キャッシュには、より大きなレイテンシで他のメモリ ソースから復元できるデータが含まれます。キャッシュは通常、メイン メモリに保存されます。メイン メモリは限られているため、効率的に使用するために、メイン メモリに保存できるのはデータの小さなスナップショットのみです。

メモリをより賢く使用し、めったに要求されないデータに対するメモリの使用を避け、要求頻度が低すぎる場合はそのようなデータを削除する必要があります。

キャッシュ内のフィールドを削除する効果的な方法は、最近最も使用されていない (LRU) 方式です。以下は LRU 表現です。

この場合、アプリケーションには最近使用したオブジェクトを保存するためのリンク リストが少なくとも 1 つ含まれており、高速検索のためのその他のデータ構造 (ハッシュ テーブルなど) も備えています。ノードは相互接続されています。

ユーザーがハッシュ テーブルからデータを取得すると、リンク リストはデータを末尾に移動して更新します。その結果、数回の操作の後、末尾には最近使用されたデータが含まれ、先頭にはほとんど要求されないデータが保持されます。

メモリ オーバーフローが発生した場合、アプリケーションは最初の N 要素をスキャンして十分なメモリを解放できます。リンク リストは順次スキャンに適応するため、これは簡単な操作です。あまり使用されないデータを含むメモリは解放され、より頻繁に使用される新しいノードはキャッシュに格納されます。

 #include <stdlib.h> #include <stdio.h> typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr; } lnode_t; typedef struct list_t { lnode_t *head; lnode_t *tail; } list_t; lnode_t* lru_insert(list_t *list, char *ptr) { if (!list->head) { list->head = list->tail = calloc(1, sizeof(lnode_t)); list->head->ptr = ptr; return list->head; } lnode_t *saved_tail = list->tail; lnode_t *new = calloc(1, sizeof(sizeof(lnode_t))); new->ptr = ptr; saved_tail->next = new; new->prev = saved_tail; list->tail = new; return new; } void lru_update(list_t *list, lnode_t *lnode) { if (list->tail == lnode) { return; } lnode_t *saved_tail = list->tail; saved_tail->next = lnode; if (!lnode->prev) list->head = lnode->next; lnode->next = NULL; lnode->prev = saved_tail; list->tail = lnode; } void lru_evict(list_t *list, int items, void (*func)(void* arg, void *ptr), void* arg) { lnode_t *lnode = list->head; while(items-- && lnode) { func(arg, lnode->ptr); lnode_t *prev = lnode->prev; lnode_t *next = lnode->next; if (prev) prev->next = next; if (next) next->prev = prev; free(lnode); lnode = next; } if (!lnode) list->head = list->tail = NULL; } void print_deleted_obj(void *arg, void *ptr) { printf("evicted: %p\n", ptr); deleteThisInTheOtherStructure(arg, ptr); } int main() { list_t *list = calloc(1, sizeof(list_t)); lnode_t *test = lru_insert(list, "some data"); lru_insert(list, "another data"); lru_update(list, test); lru_evict(list, 1, print_deleted_obj, otherStructure); }

注意: 使用要素の数の頻度が大幅に異なる場合 (たとえば、リクエストの 95% が 100 万個のうち上位 100 個のキーに分散されている場合)、Splay Tree の方がキャッシュの保存に適している可能性があります。このツリーは、各ノードの使用頻度に基づいてバランスが取られます。

スプレイ ツリーの主な考え方は LRU の逆です。最も使用される要素はルートの近くに配置されるため、このデータ構造はキャッシュのプライマリ構造として理想的です。

追い出しは、メイン構造体と相互接続されたリンク リストを使用するか、スプレイ ツリーをスレッド バイナリ ツリーに変更するという 2 つの方法で解決できます。スプレイ ツリーのノードは、使用頻度によって既に順序付けられています。ツリー リーフのスレッド化を追加すると、CPU 時間をさらに必要とする可能性がありますが、メモリを節約できます。

メモリ内の最近使用されたデータの高速化をよりよく理解するには、このリンクでライブ VM 移行の例を調べてください。

リンクリストのスキャン速度を向上させる

前述のように、リンク リストはデータを書き込むための最速のソリューションを提供します。スキャン速度は優れていますが、配列のスキャン速度よりも遅くなります。

前回の記事では、この問題をデータ局所性として説明しました。しかし、バイナリツリーと同様に、リンクリストには改善の余地があります。リンクリストを展開すると、リストの各ノードにさらに多くのデータを保存できます。そのため、次のポインタノードのメモリが節約され、要素のサイズが CPU キャッシュラインに適合するという条件で、パフォーマンスが向上することがあります。

基本的な考え方は変わりませんが、メモリ内のリストの表現は変更されます。

さまざまな方法で変更されます。以下の 2 つのオプションがあります。

これらの改善により、リンク リストのパフォーマンスは向上しますが、コードが多少複雑になります。リンク リストを使用したディスク操作では、展開されたノードにより多くの要素を含めることができます。その仕組みを理解する簡単な方法は、配列のリンク リストを想像することです。

コードでは、構造体の説明を変更し、今後は構造体の配列内の各要素を読み取ったり書き込んだりする必要があります。

 typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr[3]; } lnode_t;

リストをスキップ

スキップ リストは、リンク リスト内の検索要素の速度特性を向上させる方法です。このタイプのリンク リストには、リンク リストを順序付けるキーが格納され、単純なスキャン操作よりも効率的にノードを見つけるための追加のポインターが含まれます。

追加のノードにより、スキップ リスト内のノード間のトラバース速度が向上します。これはバイナリ検索のように機能します。逆に、新しい要素を追加するには時間がかかります。したがって、スキップ リストにはキーが必要です。アプリケーションは、速度特性を向上させるために任意の数のレベルを作成できます。ほとんどの場合、ツリーの高さと同じかそれより少し少ないレベルにするのが良い選択です。(上の画像をご覧ください)

検索中、アプリケーションは最速のルートである最高レベルから開始します。近いキーを検出すると、目的のノードが見つかるまで下位レベルに下がります。

このプロセスでは、時間の計算量は O(log(n)) になります。たとえば、16 個のノードを持つスキップ リストに 4 レベル、100 万個のノードに 20 レベル、40 億個のノードに 32 レベルを使用すると、RB ツリーと同等の時間計算量になります。

スキップ リストが優れている理由は次のとおりです。

• 実装のシンプルさ。RB ツリーと似た特性を持ちますが、実装と保守がはるかに簡単です。

• スキップ リストの末尾に新しいノードを追加する際の効率が高くなります。

• スキップ リストのスレッドセーフな実装を作成するのはツリーよりも簡単です。

このコンセプトの実装を検討してみましょう。

構造ノード:

 typedef struct skip_node { uint64_t key; uint64_t value; struct skip_node **forward; } skip_node; typedef struct skip_t { uint64_t level; uint8_t max_level; skip_node *header; } skip_t;

ノードを作成する関数:

 skip_node* create_skip_node(uint64_t key, int value, int level) { skip_node *newskip_node = (skip_node*)malloc(sizeof(skip_node)); newskip_node->key = key; newskip_node->value = value; newskip_node->forward = malloc(sizeof(skip_node)*level); for (uint64_t i = 0; i < level; i++) { newskip_node->forward[i] = NULL; } return newskip_node; } skip_t* skip_new(uint8_t max_level) { skip_t *list = (skip_t*)malloc(sizeof(skip_t)); list->level = 0; list->max_level = max_level; skip_node *header = create_skip_node(0, 0, max_level); list->header = header; for (uint64_t i = 0; i < max_level; i++) { header->forward[i] = NULL; } return list; }

挿入時のタスクには、ノードを格納する正しい場所の検出と、このノードに接続するレベルの数の決定が含まれます。レベルを決定するためのランダム関数の使用は、各新しいノードのプロセスを簡素化するのに役立ちます。平均して、この関数は 50% のケースで 2 番目のレベルを割り当て、25% のケースで 3 番目のレベルを割り当てます。この方法により、要素のバランスを再調整するためのメモリへのアクセス時間が最小限に抑えられます。

 uint64_t random_level(uint8_t max_level) { uint64_t level = 1; while (rand() < RAND_MAX / 2 && level < max_level) { level++; } return level; } void skip_insert(skip_t *list, uint64_t key, int value) { skip_node *update[list->max_level]; skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } update[i] = current; } current = current->forward[0]; if (current == NULL || current->key != key) { uint64_t newLevel = random_level(list->max_level); if (newLevel > list->level) { for (uint64_t i = list->level; i < newLevel; i++) { update[i] = list->header; } list->level = newLevel; } skip_node *newskip_node = create_skip_node(key, value, newLevel); for (uint64_t i = 0; i < newLevel; i++) { newskip_node->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newskip_node; } } }

ノードを検索する機能:

 skip_node* skip_search(skip_t *list, uint64_t key) { skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } } current = current->forward[0]; ++nodes_scan; if (current != NULL && current->key == key) return current; else return NULL; }

リンク リスト、スキップ リスト、RB ツリーのパフォーマンスをテストするためのベンチマーク関数。キーとして使用される値は、2 の累乗として設定されます。テスト目的の値は重要ではありません。

 skip_t *skipList = skip_new(atoi(argv[1])); list_t *llist = list_new(); tree_t *tree = calloc(1, sizeof(*tree)); size_t to_index = 50000000; struct timespec s_icalc; struct timespec e_icalc; struct timespec s_scalc; struct timespec e_scalc; clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) tree_insert(tree, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; nodes_scan = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { node_t *node = tree_get(tree, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) skip_insert(skipList, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { skip_node* ret = skip_search(skipList, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) list_add(llist, NULL, NULL); clock_gettime(CLOCK_REALTIME, &e_icalc);

順次増加するキーでこのデータ構造をテストした結果:

これは挿入するのに最適なタイミングであり (単純なリンク リストを考慮しない場合)、要素を検索する非常に高速な方法です。

順次減少するキーでこのデータ構造をテストした結果:

これは簡単に理解できます。このスキップ リストの実装には、最初の要素へのヘッド ポインターしかありません。末尾にノードを追加するのはより複雑です。このアプローチを変更するには、2 番目のポインター (末尾へのポインター) または逆スキップ リスト (ヘッドが大きな値を指す) を追加します。つまり、スキップ リストは、Kafka ストリームなどのログ データに効果的なデータ構造です。その場合、RB ツリーの少なくとも 2 倍の速度で実行でき、実装も簡単になります。

スキップ リストはリンク リストの挿入速度を低下させますが、シーケンシャル データの場合、特にキーが順次増加する間、要素へのアクセス時間が対数である他のデータ構造よりも高速です。ただし、キーが順次増加すると、ツリーのバランスを維持するために多くの回転が発生するため、ツリーへの挿入が複雑になります。

これは、シーケンス全体で値が増加 (または減少) している場合にのみ効果的に機能します。たとえば、キーをランダム化すると、結果は異なります。

ご覧のとおり、値の分布は RB ツリーの速度特性に大きな影響を与えませんが、スキップ リストのパフォーマンスには顕著に影響します。

結論

現在、アプリケーションはメモリやディスク内のデータをさまざまな方法で整理することがあります。マップとリストは、さまざまな目的に合わせてデータをさまざまな順序で整理する上で重要な役割を果たします。これらの構造により、十分なパフォーマンス、リソース効率、および機能が確保されます。

場合によっては、それだけではニーズに十分ではなく、アプリケーションの重要な部分を変更して、より最適化する必要があります。不正確な一致やメモリの節約のためのツリーなど、より適切なデータ構造を使用するとメリットが得られる場合があります。その他のケースでは、非同期メソッドを使用して個々のスレッドのパフォーマンスを向上させるなど、アルゴリズムの改善がメリットとなります。

他のすべてのオプションが尽きると、残るアプローチはデータ構造を適応させ、使用方法を調整することです。データ構造を実際に特定のタスクにより適したものにするために、データ構造を変更する例がいくつかあります。

リンク リストは主に書き込み専用でシーケンス スキャンを行うデータ構造ですが、RB ツリーよりも最適化でき、書き込み専用の場合でも効率を維持できます。ただし、特定の特性を高めると、他の特性にも影響が出る可能性があります。したがって、重要なものを優先し、重要でないものを破棄するのが最善の方法です。