C データ構造に関する本を読んでいるときに、「メモリ効率の良い双方向リンク リスト」という用語に出くわしました。メモリ効率の良い双方向リンク リストは、通常の双方向リンク リストよりも少ないメモリを使用するが、同じ仕事をするという 1 行がありました。それ以上の説明はなく、例も示されませんでした。これはジャーナルから取られたものであり、括弧内の「シンハ」であることが与えられました.
Googleで検索した後、私が最も近いのはこれでした。しかし、私は何も理解できませんでした。
誰かがCのメモリ効率の良い双方向リンクリストとは何か説明できますか? 通常の双方向リンクリストとどう違うのですか?
編集：さて、私は重大な間違いを犯しました。私が上に投稿したリンクを参照してください。記事の 2 ページ目でした。最初のページがあることに気付かず、指定されたリンクが最初のページだと思いました。記事の最初のページには実際に説明がありますが、完璧ではないと思います。メモリ効率の良いリンク リストまたは XOR リンク リストの基本概念についてのみ説明します。
これは、メモリを節約できる古いプログラミングのトリックです。メモリは昔ほどリソースを必要としないため、あまり使用されていないと思います。
基本的な考え方は次のとおりです: 従来の双方向リンク リストでは、隣接するリスト要素への 2 つのポインターがあります。次の要素を指す "next" ポインターと、前の要素を指す "prev" ポインターです。したがって、適切なポインターを使用して、リストを順方向または逆方向にトラバースできます。
メモリ削減の実装では、"next" と "prev" を、"next" と "prev" のビットごとの排他的 OR (ビットごとの XOR) である単一の値に置き換えます。したがって、隣接する要素ポインターのストレージを半分に減らします。
この手法を使用すると、リストをどちらの方向にもたどることができますが、そのためには前の (または次の) 要素のアドレスを知る必要があります。たとえば、順方向にリストをトラバースしていて、"prev" のアドレスを持っている場合、"prev" と現在の結合されたポインター値のビットごとの XOR を取ることで "next" を取得できます。 「前」XOR「次」。結果は "prev" XOR "prev" XOR "next" であり、これは単に "next" です。反対方向でも同じことができます。
欠点は、結合されたポインターをデコードするためのコンテキストがないため、「前」または「次」要素のアドレスを知らずに、その要素へのポインターが与えられた場合、要素を削除するなどのことを実行できないことです。価値。
もう 1 つの欠点は、この種のポインタ トリックが、コンパイラが期待する通常のデータ型チェック メカニズムを回避することです。
これは巧妙なトリックですが、正直なところ、最近ではこれを使用する理由はほとんどありません。
この質問に対する私の2 番目の回答を見ることをお勧めします。しかし、私はこの答えが間違っていると言っているわけではありません。これも正しいです。
メモリ効率の良いリンク リストは、 XOR リンク リストとも呼ばれます。
XOR (^) リンク リストは、ポインタnextとbackポインタを格納する代わりに、 1 つのnextポインタを使用してポインタとポインタの両方の仕事を行うリンクリストbackです。まず、XOR 論理ゲートのプロパティを見てみましょう。
|-------------|------------|------------|
| Name | Formula | Result |
|-------------|------------|------------|
| Commutative | A ^ B | B ^ A |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1) | A ^ 0 | A |
|-------------|------------|------------|
| None (2) | A ^ A | 0 |
|-------------|------------|------------|
| None (3) | (A ^ B) ^ A| B |
|-------------|------------|------------|
例を挙げてみましょう。A、B、C、D の4 つのノードを持つ双方向リンク リストがあります。外観は次のとおりです。
ご覧のとおり、各ノードには 2 つのポインターと、データを格納するための 1 つの変数があります。したがって、3 つの変数を使用しています。
多数のノードを持つ双方向リンク リストがある場合、使用するメモリが多すぎます。より効率的にするには、Memory-Efficient Doublely Linked Listを使用します。
メモリ効率の高い双方向リンク リストは、XOR とそのプロパティを使用して前後に移動するために 1 つのポインターのみを使用するリンク リストです。
ここに絵の表現があります：
どのように前後に移動しますか？
一時変数があります (ノードにはなく、1 つだけです)。ノードを左から右にトラバースしているとしましょう。したがって、ノード A から開始します。ノード A のポインターには、ノード B のアドレスを格納します。次に、ノード B に移動します。ノード B に移動する間、一時変数にノード A のアドレスを格納します。
ノード B のリンク (ポインター) 変数のアドレスはA ^ Cです。前のノードのアドレス (A) を取得し、それを現在のリンク フィールドと XOR すると、C のアドレスが得られます。論理的には、次のようになります。
A ^ (A ^ C)
式を単純化してみましょう。次のような連想プロパティにより、括弧を削除して書き直すことができます。
A ^ A ^ C
これをさらに単純化することができます
0 ^ C
2 番目の (表に記載されている「なし (2)」) プロパティのためです。
最初の (表に記載されている「なし (1)」) プロパティのため、これは基本的に
C
これらすべてを理解できない場合は、単に 3 番目のプロパティ (表に記載されている「なし (3)」) を参照してください。
これで、ノード C のアドレスを取得しました。これは、戻る場合と同じプロセスになります。
ノード C からノード B に移動するとします。ノード C のアドレスを一時変数に格納し、上記のプロセスをもう一度実行します。
注:A、B、などはすべてCアドレスです。明確にするように言ってくれたBathshebaに感謝します。
XOR リンク リストの短所
Lundin が述べたように、すべての変換は from/to で行う必要がありますuintptr_t。
Sami Kuhmonen が述べたように、ランダムなノードだけでなく、明確に定義された開始点から開始する必要があります。
ノードをジャンプすることはできません。あなたは順番に行かなければなりません。
また、ほとんどの場合、XOR 連結リストは二重連結リストよりも優れているわけではないことに注意してください。
参考文献
OK, so you've seen the XOR linked list, which saves you one pointer per item... but that is an ugly, ugly data structure, and far from the best you can do.
If you're worried about memory, it's almost always better to use a doubly-linked list with more than 1 element per node, like a linked list of arrays.
For example, while an XOR linked list costs 1 pointer per item, plus the item itself, A doubly-linked list with 16 items per node costs 3 pointers for each 16 items, or 3/16 pointers per item. (the extra pointer is the cost of the integer that records how many items are in the node) That is less than 1.
In addition to the memory savings, you get advantages in locality because all 16 items in the node are next to each other in memory. Algorithms that iterate through the list will be faster.
Note that an XOR-linked list also requires you to allocate or free memory each time you add or delete a node, and that is an expensive operation. With the array-linked list, you can do better than this by allowing nodes to be less than completely full. If you allow 5 empty item slots, for example, then you only have allocate or free memory on every 3rd insert or delete at worst.
There are many possible strategies for determining how and when to allocate or free nodes.
XOR 連結リストについてはすでにかなり詳しく説明しましたが、メモリの最適化についてさらにいくつかのアイデアを紹介します。
ポインターは通常、64 ビット マシンでは 8 バイトを使用します。32 ビット ポインターでアドレス可能な 4GB を超える RAM 内の任意のポイントをアドレス指定する必要があります。
メモリ マネージャーは通常、バイトではなく、固定サイズのブロックを扱います。たとえば、C の malloc は通常、16 バイトの粒度で割り当てます。
これら 2 つのことは、データが 1 バイトの場合、対応する二重連結リスト要素が 32 バイト (8+8+1、最も近い 16 の倍数に切り上げ) になることを意味します。XOR トリックを使用すると、16 まで下げることができます。
ただし、さらに最適化するには、独自のメモリ マネージャーを使用することを検討できます。(a) 1 バイトなどのより低い粒度でブロックを処理したり、場合によってはビット単位になったりします。(b) 全体のサイズの制限がより厳しくなります。たとえば、リストが常に 100 MB の連続ブロック内に収まることがわかっている場合、そのブロック内の任意のバイトをアドレス指定するのに 27 ビットしか必要ありません。32 ビットまたは 64 ビットではありません。
ジェネリック リスト クラスを開発していないが、アプリケーションの特定の使用パターンを知っている場合、多くの場合、そのようなメモリ マネージャーを実装するのは簡単な作業です。たとえば、1000 を超える要素を割り当てることがなく、各要素が 5 バイトかかることがわかっている場合、メモリ マネージャーを 5000 バイトの配列として実装し、最初の空きバイトのインデックスを保持する変数を使用して、余分な要素を割り当てると、そのインデックスを取得して、割り当てられたサイズだけ前方に移動します。この場合、ポインターは実際のポインター (int* など) ではなく、その 5000 バイト配列内の単なるインデックスになります。