XORリンクリスト

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

XORリンクリストは、コンピュータープログラミングで使用されるデータ構造一種ですビット単位のXOR演算を利用して、二重にリンクされたリストのストレージ要件を減らします

説明

通常の二重リンクリストは、各リストノードに前のリストアイテムと次のリストアイテムのアドレスを格納し、2つのアドレスフィールドを必要とします。

...ABCDE..。
          –>次–>次–>次–>
          <– prev <– prev <– prev <–

XORリンクリストは、前のアドレスとのアドレスのビット単位のXOR(ここでは⊕で示されます)を1つのフィールドに格納することにより、同じ情報を1つのアドレスフィールドに圧縮します。

...ABCDE..。
          ⇌A⊕C⇌B⊕D⇌C⊕E⇌

より正式には:

  link(B)= addr(A)⊕addr(C)、link(C)= addr(B)⊕addr(D)、..。

リストを左から右にトラバースする場合:カーソルがCにあるとすると、前の項目Bは、リンクフィールド(B⊕D)の値とXORされる可能性があります。次に、Dのアドレスが取得され、リストトラバーサルが再開されます。同じパターンが他の方向にも当てはまります。

すなわち addr(D) = link(C) ⊕ addr(B) どこで

      link(C)= addr(B)⊕addr(D)

それで

      addr(D)= addr(B)⊕addr(D)⊕addr(B)           
  
      addr(D)= addr(B)⊕addr(B)⊕addr(D)

以来

       X⊕X=0                 
       => addr(D)=0⊕addr(D)

以来

       X⊕0=X
       => addr(D)= addr(D)

addr(B)XOR演算は、方程式に2回現れることをキャンセルし、残っているのは。だけaddr(D)です。

ある時点からいずれかの方向にリストのトラバースを開始するには、2つの連続するアイテムのアドレスが必要です。2つの連続するアイテムのアドレスが逆になると、リストトラバーサルは反対方向に発生します。[1]

動作理論

キーは最初の操作であり、XORのプロパティは次のとおりです。

  • X⊕X=0
  • X⊕0=X
  • X⊕Y=Y⊕X
  • (X⊕Y)⊕Z=X⊕(Y⊕Z)

R2レジスタには、現在のアイテムCのアドレスと先行アイテムPのアドレスのXORが常に含まれています:C⊕P。レコードのリンクフィールドには、L⊕Rなどの左右の後続アドレスのXORが含まれています。R2(C⊕P)と現在のリンクフィールド(L⊕R)のXORは、C⊕P⊕L⊕Rを生成します。

  • 前任者がLの場合、P(= L)とLはキャンセルされ 、C⊕Rが残ります。
  • 前任者がRだった場合、P(= R)とRはキャンセルされ、C⊕Lが残ります。

いずれの場合も、結果は現在のアドレスと次のアドレスのXORです。これをR1の現在のアドレスとXORすると、次のアドレスが残ります。R2には、(現在の)現在のアドレスと先行アドレスの必要なXORペアが残されています。

機能

  • あるアイテムから次のアイテムへのトラバーサルを実行するには、2つのXOR演算で十分です。どちらの場合も、同じ命令で十分です。アイテムを含み、 {…B C D…}R1とR2がそれぞれ現在の(たとえばC)リストアイテムのアドレスを含むレジスタであり、現在のアドレスと前のアドレス(たとえばC⊕D)のXORを含むワークレジスタであるリストを考えてみます。System / 360命令としてキャスト:
X R2、Link R2 <-C⊕D⊕B⊕D(つまり、B⊕C、「リンク」はリンクフィールドです
                                  現在のレコードで、B⊕Dを含む)
XR R1、R2 R1 <-C⊕B⊕C(つまり、B、voilà:次のレコード)
  • リストの終わりは、のように、エンドポイントに隣接して配置されたアドレス0のリストアイテムを想像することによって示されます{0 A B C…}Aのリンクフィールドは0⊕Bになります。現在のアイテムのアドレスを開発する際にゼロの結果を検出するために、2つのXOR演算の後に、上記のシーケンスで追加の命令が必要です。
  • リンクポインタをゼロにすることで、リストのエンドポイントを反映させることができます。ゼロポインタはミラーです。(左右の隣接アドレスのXORは同じであるため、ゼロです。)

欠点

  • 汎用デバッグツールはXORチェーンをたどることができないため、デバッグがより困難になります。[2]
  • メモリ使用量の減少の代償は、コードの複雑さの増加であり、メンテナンスがより高価になります。
  • ほとんどのガベージコレクションスキームは、リテラルポインタを含まないデータ構造では機能しません
  • すべての言語がポインターと整数の間の型変換をサポートしているわけではありません。ポインターのXORは、一部のコンテキストでは定義されていません。
  • リストをトラバースしている間、次のノードのアドレスを計算するには、以前にアクセスしたノードのアドレスが必要です。リストをトラバースしていない場合、たとえば、リストアイテムへのポインタが別のデータ構造に含まれている場合、ポインタは読み取れません。 ;
  • XORリンクリストは、アドレスのみを知っているリストからノードを削除する機能や、アドレスのみを知っているときに既存のノードの前後に新しいノードを挿入する機能など、二重リンクリストの重要な利点の一部を提供しません。既存のノードの。

コンピュータシステムはますます安価で豊富なメモリを備えているため、ストレージのオーバーヘッドは一般に、特殊な組み込みシステム以外では最優先の問題ではありません。リンクリストのオーバーヘッドを削減することが依然として望ましい場合、展開はより実用的なアプローチを提供します(また、キャッシュパフォーマンスの向上やランダムアクセスの高速化などの他の利点もあります)。

バリエーション

XORリンクリストの基本原則は、任意の可逆二項演算に適用できます。XORを加算または減算で置き換えると、わずかに異なるがほぼ同等の定式化が得られます。

追加リンクリスト

...ABCDE..。
          ⇌A+C⇌B+D⇌C+E⇌

この種類のリストには、ゼロリンクフィールドが「ミラー」ではないことを除いて、XORリンクリストとまったく同じプロパティがあります。リスト内の次のノードのアドレスは、現在のノードのリンクフィールドから前のノードのアドレスを引くことによって与えられます。

減算リンクリスト

...ABCDE..。
          ⇌CA⇌DB⇌EC⇌

この種のリストは、リストを順方向にトラバースするために必要な命令シーケンスがリストを逆方向にトラバースするために必要なシーケンスとは異なるという点で、標準の「従来の」XORリンクリストとは異なります。次のノードのアドレスは、前のノードのアドレスにリンクフィールドを追加することで指定されます。前のノードのアドレスは、次のノードのアドレスからリンクフィールドを 引くことによって与えられます。

リスト内の各アドレスに一定のオフセットを追加してもリンクフィールドに格納されている値を変更する必要がないため、減算リンクリストは、ポインタ値のパッチを適用せずにリスト全体をメモリに再配置できるという点でも特別です。シリアル化も参照してください。)これは、XORリンクリストと従来のリンクリストの両方に勝る利点です。

二分探索木

XORリンクリストの概念は、XOR二分探索木に一般化できます。[3]

も参照してください

参考文献

  1. ^ 「XORリンクリスト-メモリ効率の高い二重リンクリスト|セット1-GeeksforGeeks」GeeksforGeeks2011-05-23 2018年10月29日取得
  2. ^ Gadbois、David; etal。「GC[ガベージコレクション]FAQ–ドラフト」2018年12月5日取得
  3. ^ 「XORスケープゴートツリーに基づくc++連想コンテナ」2021年11月5日取得

外部リンク