永続的なデータ構造

コンピューティングにおいて、永続的データ構造または非一時的データ構造は、変更されたときに常に以前のバージョンを保持するデータ構造です。このようなデータ構造は、操作によって構造が（目に見えて）その場で更新されるのではなく、常に新しい更新された構造が生成されるため、事実上不変です。この用語は、Driscoll、Sarnak、Sleator、およびTarjanの1986年の論文で導入されました。^[1]

すべてのバージョンにアクセスできるが、最新バージョンのみを変更できる場合、データ構造は部分的に永続的です。すべてのバージョンにアクセスして変更できる場合、データ構造は完全に永続的です。2つの以前のバージョンから新しいバージョンを作成できる結合操作もある場合、データ構造は合流的に永続的と呼ばれます。永続的ではない構造は、一時的と呼ばれます。^[2]

こうしたタイプのデータ構造は、論理プログラミングや関数型プログラミングで特に一般的です。^[2]これらのパラダイムの言語では、可変データの使用が推奨されていない（または完全に禁止されている）ためです。

部分的永続性モデルでは、プログラマはデータ構造の以前のバージョンを照会できますが、更新できるのは最新バージョンのみです。これは、データ構造の各バージョン間の線形順序付けを意味します。 ^[3]完全永続性モデルでは、データ構造のどのバージョンでも更新と照会の両方が許可されます。ロープデータ構造の場合のように、データ構造の古いバージョンの照会または更新のパフォーマンス特性が低下することが許容される場合もあります。^[4]さらに、データ構造が完全に永続的であることに加えて、同じデータ構造の 2 つのバージョンを組み合わせて、完全に永続的な新しいバージョンを形成できる場合、そのデータ構造は合流的に永続的であると言えます。^[5]

ユーザーが構造の任意のバージョンを照会できるが、更新できるのは最新バージョンのみであるデータ構造のタイプ。

いくつかのテクニックを使用することで、一時的なデータ構造を部分的に永続的なデータ構造に変換できます。

テクニックの 1 つは、動的完全ハッシュを使用して作成された Van Emde Boas Tree のランダム化バージョンを使用することです。このデータ構造は次のように作成されます。

• m 個の要素を持つ階層化ツリーは、動的完全ハッシュを使用して実装されます。
• ツリーは、m 個の要素をサイズ log(log n) のバケットに分割することによって剪定され、バケット 1 の要素はバケット 2 の要素よりも小さくなります。
• 各バケットの最大要素は階層化ツリーに格納され、各バケットは順序なしのリンク リストとして構造に格納されます。

このデータ構造のサイズは、構造に格納される要素の数、つまり O(m) によって制限されます。新しい最大要素の挿入は、一定の O(1) の期待時間および償却時間で行われます。最後に、この構造で要素を見つけるためのクエリは、最悪の場合 O(log(log n)) 時間で実行できます。^[6]

永続的なデータ構造を作成する方法の 1 つは、プラットフォームが提供する一時的なデータ構造 (配列など) を使用してデータ構造にデータを保存し、データ構造の更新時にコピーオンライト セマンティクスを使用してそのデータ構造全体をコピーすることです。これは、書き込みごとにバックアップ データ構造全体をコピーする必要があるため、サイズ n の配列を m 回変更した場合の最悪のケースで O(n·m) のパフォーマンス特性につながるため、非効率的な手法です。^{[引用が必要]}

ファット ノード方式では、フィールドの古い値は消去せずに、ノード フィールドに加えられたすべての変更をノード自体に記録します。このためには、ノードが任意に「ファット」になることが許可される必要があります。言い換えると、各ファット ノードには、エフェメラル ノードと同じ情報とポインターフィールドに加えて、任意の数の追加フィールド値のためのスペースが含まれます。各追加フィールド値には、関連付けられたフィールド名とバージョン スタンプがあり、これは、名前付きフィールドが指定された値に変更されたバージョンを示します。さらに、各ファット ノードには、ノードが作成されたバージョンを示す独自のバージョン スタンプがあります。ノードにバージョン スタンプがある唯一の目的は、各ノードに、バージョンごとにフィールド名ごとに 1 つの値のみが含まれるようにすることです。構造内を移動できるように、ノード内の元のフィールド値にはそれぞれバージョン スタンプ 0 があります。

ファットノード方式を使用すると、変更ごとに O(1) のスペースが必要になります。新しいデータを保存するだけです。変更ごとに、変更履歴の最後に変更を保存するために O(1) の追加時間がかかります。これは、変更履歴が拡張可能な配列に保存されていると仮定した場合の、償却時間制限です。アクセス時に、構造をトラバースするときに各ノードの正しいバージョンを見つける必要があります。「m」の変更が行われる場合、配列内の最も近い変更を見つけるコストにより、各アクセス操作で O(log m) の速度低下が発生します。

パス コピー メソッドでは、変更されるノードへのパス上のすべてのノードのコピーが作成されます。これらの変更は、データ構造を通じてカスケード バックされる必要があります。つまり、古いノードを指していたすべてのノードを、新しいノードを指すように変更する必要があります。これらの変更によって、さらにカスケード変更が発生し、ルート ノードに到達するまでこれが続きます。

m 回の変更では、追加検索時間は O(log m) かかります。変更時間とスペースは、データ構造内の最長パスのサイズと、一時データ構造の更新コストによって制限されます。親ポインタのないバランス型バイナリ検索ツリーでは、最悪の場合の変更時間の複雑さは O(log n + 更新コスト) です。ただし、リンク リストでは、最悪の場合の変更時間の複雑さは O(n + 更新コスト) です。

Driscoll、Sarnak、Sleator、Tarjanは、ファットノードとパスコピーの技術を組み合わせて、O(1)のアクセス速度低下とO(1)の変更空間と時間の計算量を実現する方法を^考案しました[1]。

各ノードには、1 つの変更ボックスが格納されます。このボックスには、ノードに対する 1 つの変更 (ポインターの 1 つ、ノードのキー、またはノード固有のデータの他の部分に対する変更) と、その変更が適用されたときのタイムスタンプが保持されます。最初は、すべてのノードの変更ボックスは空です。

ノードがアクセスされるたびに、変更ボックスがチェックされ、そのタイムスタンプがアクセス時間と比較されます。(アクセス時間は、考慮されるデータ構造のバージョンを指定します。) 変更ボックスが空の場合、またはアクセス時間が変更時間より前の場合、変更ボックスは無視され、ノードの通常部分のみが考慮されます。一方、アクセス時間が変更時間より後の場合、変更ボックスの値が使用され、ノードのその値が上書きされます。

ノードの変更は次のように行われます。(各変更は 1 つのポインターまたは同様のフィールドに触れるものと想定されます。) ノードの変更ボックスが空の場合、変更内容がそこに入力されます。それ以外の場合、変更ボックスはいっぱいです。ノードのコピーが作成されますが、最新の値のみが使用されます。変更は、変更ボックスを使用せずに、新しいノードで直接実行されます。(新しいノードのフィールドの 1 つが上書きされ、その変更ボックスは空のままになります。) 最後に、この変更は、パスのコピーと同様に、ノードの親にカスケードされます。(これには、親の変更ボックスの入力、または親のコピーの再帰的作成が含まれる場合があります。ノードに親がない場合 (ルート)、新しいルートがルートのソートされた配列に追加されます。)

このアルゴリズムでは、任意の時刻 t に対して、時刻 t のデータ構造内に最大 1 つの変更ボックスが存在します。したがって、時刻 t での変更により、ツリーは 3 つの部分に分割されます。1 つの部分には時刻 t より前のデータが含まれ、1 つの部分には時刻 t より後のデータが含まれ、1 つの部分は変更の影響を受けません。

変更の時間とスペースには、償却分析が必要です。変更には、 O(1) の償却スペースと O(1) の償却時間がかかります。理由を確認するには、ポテンシャル関数ϕ を使用します。ここで、 ϕ(T) は、 T 内の完全なライブ ノードの数です。 T のライブ ノードは、現在の時刻 (つまり、最後の変更後) に現在のルートから到達可能なノードです。完全なライブ ノードは、変更ボックスがいっぱいになっているライブ ノードです。

各変更には、たとえば k 個のコピーと、それに続く変更ボックスへの 1 つの変更が含まれます。k 個のコピーのそれぞれについて考えてみましょう。それぞれに O(1) のスペースと時間がかかりますが、潜在的関数が 1 つ減少します。(まず、コピーされるノードは完全かつライブでなければならないため、潜在的関数に寄与します。ただし、潜在的関数が削除されるのは、新しいツリーで古いノードに到達できない場合のみです。ただし、新しいツリーで古いノードに到達できないことはわかっています。アルゴリズムの次のステップでは、ノードの親を変更してコピーを指すようにします。最後に、コピーの変更ボックスが空であることがわかっています。したがって、完全にライブだったノードが空のライブ ノードに置き換えられ、ϕ が 1 つ減少します。) 最後のステップでは、変更ボックスが満たされ、O(1) の時間がかかり、ϕ が 1 つ増加します。

まとめると、ϕの変化はΔϕ =1− kです。したがって、アルゴリズムはO(k +Δϕ)= O(1)のスペースとO(k +Δϕ +1) = O(1)の時間を必要とします。

パスのコピーは、バイナリ検索木などの特定のデータ構造で永続性を実現するための簡単な方法の 1 つです。任意のデータ構造で機能する永続性を実装するための一般的な戦略があると便利です。これを実現するために、有向グラフGについて考えます。Gの各頂点vには、ポインターによって表される定数cの出力エッジがあると仮定します。各頂点には、データを表すラベルがあります。頂点には、inedges( v ) として定義される、頂点につながる制限された数 d のエッジがあるとします。Gでは、次のさまざまな操作を許可します。

• CREATE-NODE(): 入ってくるエッジも出ていくエッジもない新しい頂点を作成します。
• CHANGE-EDGE( v , i , u ): vのi^{番目の辺を}uを指すように変更します。
• CHANGE-LABEL( v , x ): vに格納されているデータの値をxに変更します。

上記の操作はいずれも特定の時間に実行され、永続的なグラフ表現の目的は、いつでもGの任意のバージョンにアクセスできるようにすることです。この目的のために、 Gの各頂点vのテーブルを定義します。テーブルにはc列と行が含まれます。各行には、出力エッジへのポインタに加えて、頂点のデータを表すラベルと、操作が実行された時間t が含まれます。さらに、vへのすべての入力エッジを追跡する配列 inedges( v ) があります。テーブルがいっぱいになると、行を含む新しいテーブルを作成できます。古いテーブルは非アクティブになり、新しいテーブルがアクティブ テーブルになります。 ${\displaystyle d+1}$${\displaystyle d+1}$

CREATE-NODEを呼び出すと新しいテーブルが作成され、すべての参照がnullに設定されます。

CHANGE-EDGE( v , i , u ) が呼び出されると仮定すると、考慮すべきケースが 2 つあります。

• 頂点vのテーブルには空の行があります。この場合、テーブルの最後の行をコピーし、頂点vのi番目の辺を新しい頂点uを指すように変更します。
• 頂点vのテーブルがいっぱいです。この場合、新しいテーブルを作成する必要があります。古いテーブルの最後の行を新しいテーブルにコピーします。配列 inedges( v ) をループして、配列内の各頂点が新しく作成されたテーブルを指すようにする必要があります。さらに、グラフG にエッジ v,w が存在するように、すべての頂点wについて inedges(w) のエントリv を変更する必要があります。

^{これは、頂点の}i番目のエッジを変更する代わりに、i^番目のラベルを変更する点を除いて、CHANGE-EDGE とまったく同じように機能します。

上記で提案したスキームの効率性を調べるために、クレジット スキームとして定義された引数を使用します。クレジットは通貨を表します。たとえば、クレジットはテーブルの支払いに使用できます。引数は次のように述べています。

• 1つのテーブルの作成には1クレジットが必要です
• CREATE-NODEの呼び出しごとに2クレジットが付与されます
• CHANGE-EDGEへの通話ごとに1クレジットが付与されます

クレジット スキームは、常に次の不変条件を満たす必要があります。各アクティブ テーブルの各行には 1 つのクレジットが格納され、テーブルには行数と同じ数のクレジットがあります。この不変条件が 3 つの操作 CREATE-NODE、CHANGE-EDGE、および CHANGE-LABEL すべてに適用されることを確認しましょう。

• CREATE-NODE: 2 つのクレジットを取得します。1 つはテーブルの作成に使用され、もう 1 つはテーブルに追加される 1 つの行に割り当てられます。したがって、不変性が維持されます。
• CHANGE-EDGE: 考慮すべきケースが 2 つあります。最初のケースは、テーブルにまだ少なくとも 1 つの空の行がある場合です。この場合、1 つのクレジットが新しく挿入された行に使用されます。2 番目のケースは、テーブルがいっぱいの場合です。この場合、古いテーブルは非アクティブになり、CHANGE-EDGE の呼び出しから取得された 1 つのクレジットに加えて、クレジットが新しいテーブルに変換されます。したがって、合計でクレジットがあります。1 つのクレジットは、新しいテーブルの作成に使用されます。別のクレジットは、テーブルに追加される新しい行に使用され、残りのdクレジットは、新しいテーブルを指す必要がある他の頂点のテーブルの更新に使用されます。不変条件は維持されていると結論付けられます。${\displaystyle d+1}$${\displaystyle d+2}$
• CHANGE-LABEL: CHANGE-EDGE とまったく同じように機能します。

まとめると、CREATE_NODE の呼び出しとCHANGE_EDGE の呼び出しを行うと、テーブルが作成されるという結論になります。各テーブルのサイズは再帰呼び出しを考慮に入れなくても であるため、テーブルに入力するには が必要になります。ここで、追加の d 係数は、他のノードの入辺を更新することで発生します。したがって、一連の操作を完了するために必要な作業量は、作成されるテーブルの数に を掛けた値で制限されます。各アクセス操作は で実行でき、辺とラベルの操作があるため、 が必要です。結論として、で CREATE-NODE、CHANGE-EDGE、および CHANGE-LABEL の任意のシーケンスを完了できるデータ構造が存在することになります。 ${\displaystyle n_{1}}$${\displaystyle n_{2}}$${\displaystyle 2\cdot n_{1}+n_{2}}$${\displaystyle O(d)}$${\displaystyle O(d^{2})}$${\displaystyle O(d^{2})}$${\displaystyle O(Log(d))}$${\displaystyle m}$${\displaystyle m\cdot O(Log(d))}$${\displaystyle n}$${\displaystyle O(n\cdot d^{2})+m\cdot O(Log(d))}$

永続性を使用して効率的に解決できる便利なアプリケーションの 1 つに、次の要素の検索があります。X軸に平行で、互いに交差しない非交差線分があると仮定します。ポイントを照会して、その上の線分(ある場合) を返すことができるデータ構造を構築します。まず、単純な方法を使用して次の要素の検索を解決し、次に永続的なデータ構造方法を使用して解決する方法を示します。 ${\displaystyle n}$${\displaystyle p}$${\displaystyle p}$

まず、無限遠から始まる垂直線分から始めて、線分を左から右にスイープします。これらの線分の終点に遭遇するたびに一時停止します。垂直線は平面を垂直ストリップに分割します。線分がある場合は、各線分に終点があるため、垂直ストリップを取得できます。ストリップ内で開始および終了する線分はありません。すべての線分はストリップに触れないか、完全に交差します。線分は、上から下に向かって何らかの順序でソートされたいくつかのオブジェクトと考えることができます。重要なのは、見ている点がこの順序のどこに当てはまるかです。線分の終点を座標でソートします。各ストリップについて、交差するサブセット線分を辞書に格納します。垂直線が線分をスイープするとき、線分の左の終点を通過するたびに、それを辞書に追加します。線分の右の終点を通過すると、辞書から削除します。すべての終点で、辞書のコピーを保存し、すべてのコピーを座標でソートして格納します。このようにして、あらゆるクエリに回答できるデータ構造が得られます。点 の上のセグメントを見つけるには、の座標を調べて、それがどのコピーまたはストリップに属しているかを確認します。次に、 の座標を調べて、その上のセグメントを見つけることができます。したがって、2 つのバイナリ検索が必要になります。1 つはストリップまたはコピーを見つけるための座標の検索で、もう 1 つはその上のセグメントを見つけるための座標の検索です。したがって、クエリ時間は かかります。このデータ構造では、スペースが問題になります。なぜなら、すべてのセグメントが他のセグメントの終わりよりも前に始まるようにセグメントが構造化されていると仮定すると、単純な方法を使用して構造を構築するために必要なスペースは になるからです。では、同じクエリ時間で、より適切なスペースを持つ別の永続データ構造を構築する方法を見てみましょう。 ${\displaystyle n}$${\displaystyle 2\cdot n+1}$${\displaystyle 2}$${\displaystyle x}$${\displaystyle s_{i}}$${\displaystyle s_{i}}$${\displaystyle x}$${\displaystyle p}$${\displaystyle x}$${\displaystyle p}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle O(Log(n))}$${\displaystyle O(n^{2})}$

素朴な方法で使用されるデータ構造で本当に時間がかかるのは、ストリップから次のストリップに移動するときに、物事をソート順に保つために使用しているデータ構造のスナップショットを取得する必要があることに気付くでしょう。 と交差するセグメントを取得すると、 に移動するときに、から が離れるか、 が入るかのどちらかであることがわかります。 にあるものと にあるものの違いが 1 つの挿入または削除だけである場合、からにすべてをコピーするのは得策ではありません。秘訣は、各コピーが前のコピーと 1 つの挿入または削除だけ異なるため、変更された部分のみをコピーする必要があることです。 をルートとするツリーがあると仮定します。 ツリーにキーを挿入すると、 を含む新しいリーフが作成されます。 ツリーのバランスを再調整するために回転を実行すると、 からへのパスのノードのみが変更されます。 ツリーにキーを挿入する前に、 からへのパス上のすべてのノードを にコピーします。これで、ツリーの 2 つのバージョンができました。1 つは を含まない元のツリー、もう 1 つは を含み、ルートが のルートのコピーである新しいツリーです。からへのパスをコピーしても挿入時間が一定係数を超えて増加することはないため、永続データ構造への挿入には時間がかかります。 削除については、削除によって影響を受けるノードを見つける必要があります。削除によって影響を受ける各ノードについて、ルートから へのパスをコピーします。これにより、ルートが元のツリーのルートのコピーである新しいツリーが作成されます。次に、新しいツリーで削除を実行します。最終的に 2 つのバージョンのツリーが作成されます。 を含む元のツリーと を含まない新しいツリーです。削除ではルートから へのパスのみが変更され、適切な削除アルゴリズムは で実行されるため、永続データ構造での削除には かかります。挿入と削除のすべてのシーケンスにより、それぞれが操作 の結果である辞書、バージョン、またはツリーのシーケンスが作成されます。それぞれに要素が含まれている場合、それぞれでの検索には かかります。この永続的なデータ構造を使用すると、の代わりにクエリ時間と空間で次の要素の検索問題を解決できます。次の検索問題に関連する例のソース コードを以下に示します。 ${\displaystyle s_{i}}$${\displaystyle s_{i+1}}$${\displaystyle s_{i}}$${\displaystyle s_{i+1}}$${\displaystyle s_{i}}$${\displaystyle s_{i+1}}$${\displaystyle T}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle T}$${\displaystyle k}$${\displaystyle k}$${\displaystyle T}$${\displaystyle k}$${\displaystyle k}$${\displaystyle T}$${\displaystyle k}$${\displaystyle T}$${\displaystyle O(Log(n))}$${\displaystyle v}$${\displaystyle v}$${\displaystyle k}$${\displaystyle k}$${\displaystyle v}$${\displaystyle O(Log(n))}$${\displaystyle O(Log(n))}$${\displaystyle S_{1},S_{2},\dots S_{i}}$${\displaystyle S_{i}}$${\displaystyle S_{1},S_{2},\dots S_{i}}$${\displaystyle S_{i}}$${\displaystyle m}$${\displaystyle S_{i}}$${\displaystyle O(Log(m))}$${\displaystyle O(Log(n))}$${\displaystyle O(n\cdot Log(n))}$${\displaystyle O(n^{2})}$

おそらく最も単純な永続的なデータ構造は、単方向リンク リストまたはconsベースのリストです。これは、各オブジェクトがリスト内の次のオブジェクトへの参照を保持することで形成される単純なオブジェクト リストです。これが永続的であるのは、リストの末尾(つまり、あるkの最後のk項目)を取得でき、その前に新しいノードを追加できるためです。末尾は複製されず、古いリストと新しいリストの両方で共有されます。末尾の内容が不変である限り、この共有はプログラムには見えません。

赤黒木^[7] 、スタック^[8]、トレップ^[9]などの多くの一般的な参照ベースのデータ構造は、簡単に適応させて永続バージョンを作成できます。その他のデータ構造には、キュー、デキュー、およびmin-deques（最小要素を返す追加のO(1)操作minを持つ）やランダムアクセスdeques（線形以下、ほとんどの場合は対数的な複雑さのランダムアクセス操作が追加されている）などの拡張機能など、もう少し手間がかかります。

^{また、破壊的な[明確化が必要]}操作を使用する永続データ構造も存在します。これは、純粋に関数型の言語 (状態や IO などの特殊なモナド以外では Haskell など) では効率的に実装できませんが、C や Java などの言語では可能です。これらのタイプのデータ構造は、多くの場合、異なる設計で回避できます。純粋に永続的なデータ構造を使用する主な利点の 1 つは、マルチスレッド環境での動作が向上することが多いことです。

単方向リンクリストは、関数型言語における基本的なデータ構造です。^[10] HaskellなどのML派生言語の中には、純粋に関数的な言語もあります。これは、リスト内のノードが一度割り当てられると、それを変更することはできず、何も参照していないときにガベージコレクターによってコピー、参照、または破棄することしかできないためです。( ML 自体は純粋に関数的ではありませんが、非破壊的なリスト操作のサブセットをサポートしており、これはSchemeやRacketなどのLisp (LISt Processing) 関数型言語方言にも当てはまります。)

次の 2 つのリストを考えてみましょう。

xs = [0, 1, 2]
y = [3, 4, 5]

これらはメモリ内で次のように表されます。

ここで、円はリスト内のノードを示します (外向きの矢印は、別のノードへのポインタであるノードの 2 番目の要素を表します)。

次に 2 つのリストを連結します。

zs = xs ++ ys

メモリ構造は次のようになります。

リスト内のノードはxsコピーされていますが、 内のノードはys共有されていることに注意してください。その結果、元のリスト (xsおよびys) は保持され、変更されていません。

コピーを行う理由は、 の最後のノードxs(元の値 を含むノード2) を の先頭を指すように変更することはできないためです。 ys変更すると の値が変更されてしまいます。xs

二分探索木[ 10 ^]を考えてみましょう。木内のすべてのノードには、左 のサブツリーに含まれるすべてのサブノードの値がノードに格納されている値以下であり、右のサブツリーに含まれるサブノードの値がノードに格納されている値より大きいという再帰不変条件があります。

例えば、データセット

xs = [a, b, c, d, f, g, h]

次の二分探索木で表すことができます。

バイナリ ツリーにデータを挿入し、不変条件を維持する関数は次のとおりです。

 楽しい insert  ( x ,  E )  =  T  ( E ,  x ,  E ) 
   |  insert  ( x ,  s  as  T  ( a ,  y ,  b ))  = 
        x < y の場合 、T ( insert ( x , a ), y , b ) 、それ以外の場合、 x > yの場合、T ( a , y , insert ( x , b )) 、それ以外の場合、 s         
                   
         

実行後

ys = 挿入 ("e", xs)

次の構成が生成されます。

2 つの点に注意してください。1 つ目は、元のツリー ( ) が存続することです。2 つ目は、多くの共通ノードが古いツリーと新しいツリーの間で共有されることです。このような存続と共有は、ライブ参照のないノードを自動的に解放する何らかのガベージ コレクションxs(GC)がなければ管理が困難です。そのため、GC は関数型プログラミング言語でよく見られる機能です。

Fat Nodes、Copy-on-Write、およびパス コピー テクニックを使用した永続的な BST の実装を含む GitHub リポジトリ。

永続的な BST 実装を使用するには、リポジトリをクローンし、README ファイルに記載されている手順に従うだけです。

リンク: https://github.com/DesaultierMAKK/PersistentBST

永続ハッシュ配列マップトライは、ハッシュ配列マップトライの特殊な変形であり、更新時に以前のバージョンを保存します。これは、汎用の永続マップデータ構造を実装するためによく使用されます。^[11]

ハッシュ配列マップトトライは、もともとPhil Bagwellによる 2001 年の論文「理想的なハッシュツリー」で説明されました。この論文では、可変ハッシュテーブルが紹介され、「挿入、検索、削除の時間は短く一定で、キーセットのサイズとは無関係で、操作は O(1) です。挿入、検索、削除操作の最悪ケースの時間が短いことが保証され、ミスのコストは成功した検索よりも低くなります」と説明されています。^{[12]このデータ構造はその後}Rich Hickeyによって変更され、Clojureプログラミング言語で使用できるように完全に永続的になりました。^[13]

概念的には、ハッシュ配列マップトトライは、ノードを階層的に保存し、特定の要素までのパスをたどってノードを取得するという点で、一般的なツリーと同様に機能します。主な違いは、ハッシュ配列マップトトライは最初にハッシュ関数を使用して、検索キーを（通常は32ビットまたは64ビットの）整数に変換することです。次に、その整数のバイナリ表現のスライスを使用して、ツリーの各レベルでスパース配列にインデックスを付けることで、ツリーのパスが決定されます。ツリーのリーフノードは、ハッシュテーブルの構築に使用されるバケットと同様に動作し、ハッシュ衝突に応じて複数の候補を含む場合と含まない場合があります。^[11]

永続ハッシュ配列マップトライの実装のほとんどは、その実装で分岐係数 32 を使用しています。つまり、実際には永続ハッシュ配列マップトライへの挿入、削除、および検索にはO (log n ) の計算複雑性がありますが、ほとんどのアプリケーションでは実質的に定数時間です。これは、操作に 12 ステップ以上かかるようにするには、非常に多くのエントリが必要になるためです。^[14]

Haskellは純粋関数型言語であるため、変更は許可されません。したがって、言語内のすべてのデータ構造は永続的であり、関数型セマンティクスを持つデータ構造の以前の状態を保存しないことは不可能です。^{[15]これは、データ構造の以前のバージョンを無効にするようなデータ構造の変更は、}参照の透明性に違反するためです。

Haskellの標準ライブラリには、リンクリスト^[16]、マップ（サイズバランスのとれた木として実装）^[17]、セット^[18]などの効率的な永続実装が含まれています。^[19]

Lispファミリーの多くのプログラミング言語と同様に、Clojureにはリンクリストの実装が含まれていますが、他の方言とは異なり、リンクリストの実装では慣例的に永続的であるのではなく、強制的に永続化されています。^{[20] Clojureには、永続ハッシュ配列マップトライに基づく永続ベクター、マップ、セットの効率的な実装もあります。これらのデータ構造は}、Javaコレクションフレームワークの必須の読み取り専用部分を実装しています。^[21]

Clojure言語の設計者は、可変データ構造よりも永続データ構造の使用を推奨しています。永続データ構造には値セマンティクスがあり、安価なエイリアスを使用してスレッド間で自由に共有でき、作成が容易で、言語に依存しないという利点があるためです。^[22]

これらのデータ構造は、データ競合やアトミックな比較とスワップのセマンティクスを回避するために操作を簡単に再試行できるため、 Clojureの並列コンピューティングサポートの基礎を形成します。^[23]

Elmプログラミング言語はHaskellと同様に純粋に関数型であり、必然的にすべてのデータ構造を永続化します。Elmには、リンクリストの永続的な実装だけでなく、永続的な配列、辞書、セットも含まれています。^[24]

Elmは、Elmデータの永続性を利用したカスタム仮想DOM実装を使用しています。2016年の時点で、この仮想DOMにより、Elm言語は人気のJavaScriptフレームワークであるReact、Ember、Angularよりも高速にHTMLをレンダリングできることがElmの開発者によって報告されました。^[25]

Javaプログラミング言語は特に機能的ではありません。それにもかかわらず、コアJDKパッケージjava.util.concurrentには、コピーオンライト技術を使用して実装された永続的な構造であるCopyOnWriteArrayListとCopyOnWriteArraySetが含まれています。ただし、Javaの通常の並行マップ実装であるConcurrentHashMapは永続的ではありません。完全に永続的なコレクションは、サードパーティのライブラリ、^[26]または他のJVM言語で利用できます。

人気のJavaScriptフロントエンドフレームワークReactは、Fluxアーキテクチャを実装する状態管理システムと一緒に頻繁に使用されます。^{[27] [28]}その人気の実装はJavaScriptライブラリReduxです。Reduxライブラリは、Elmプログラミング言語で使用される状態管理パターンに触発されており、ユーザーがすべてのデータを永続的なものとして扱うことを義務付けています。^[29]その結果、Reduxプロジェクトは、特定のケースでは、強制的で効率的な永続データ構造のためにライブラリを使用することをユーザーに推奨しています。これにより、通常のJavaScriptオブジェクトを比較またはコピーする場合よりもパフォーマンスが向上すると言われています。^[30]

永続データ構造のそのようなライブラリの 1 つである Immutable.js は、Clojure と Scala によって利用可能になり普及したデータ構造に基づいています。^[31] Redux のドキュメントでは、強制的な不変性を提供できる可能性のあるライブラリの 1 つとして言及されています。^[30] Mori.js は、Clojure に似たデータ構造を JavaScript にもたらします。^[32] Immer.js は、「現在の状態を変更することで次の不変状態を作成する」という興味深いアプローチをもたらします。 ^[33] Immer.js はネイティブの JavaScript オブジェクトを使用し、効率的な永続データ構造ではないため、データ サイズが大きい場合にパフォーマンスの問題が発生する可能性があります。

Prolog項は本来不変であるため、データ構造は一般的に永続的なデータ構造です。そのパフォーマンスは、Prologシステムが提供する共有とガベージコレクションに依存します。^[34]非基底Prolog項への拡張は、探索空間の爆発的な増加のため、必ずしも実行可能ではありません。遅延目標は、この問題を軽減する可能性があります。

それでも、一部のPrologシステムはsetarg/3のような破壊的な操作を提供しており、コピーの有無や状態変化のバックトラックの有無など、さまざまなバリエーションがある。制約ソルバーのような新しい宣言層を提供するためにsetarg/3が使用される場合もある。^[35]

Scalaプログラミング言語は、「オブジェクト関数型スタイル」を使用してプログラムを実装するための永続データ構造の使用を推進しています。^{[36] Scalaには、リンクリスト、}赤黒木、Clojureで導入された永続ハッシュ配列マップトラインなど、多くの永続データ構造の実装が含まれています。 ^[37]

永続データ構造は、多くの場合、データ構造の連続バージョンが基礎となるメモリを共有するような方法で実装されるため^[38]、このようなデータ構造を人間工学的に使用するには、通常、参照カウントやマークアンドスイープなどの何らかの自動ガベージコレクションシステムが必要です。^[39]永続データ構造が使用されている一部のプラットフォームでは、ガベージコレクションを使用しないという選択肢がありますが、ガベージコレクションを使用するとメモリリークが発生する可能性がありますが、場合によってはアプリケーションの全体的なパフォーマンスにプラスの影響を与える可能性があります。^[40]

• コピーオンライト
• ナビゲーションデータベース
• 永続データ
• 遡及的なデータ構造
• 純粋に関数的なデータ構造

• 永続的な赤黒木の軽量 Java 実装
• C# における効率的な永続構造