永続的なデータ構造

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

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

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

部分的な持続性と完全な持続性

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

以前のバージョンを保存するためのテクニック

コピーオンライト

永続的なデータ構造を作成する方法の一つは、プラットフォームが提供する一時的なデータ構造（例えば配列）を用いてデータをデータ構造に格納し、そのデータ構造全体をコピーすることです。これは、書き込みごとに基盤となるデータ構造全体をコピーする必要があるため、非効率的な手法です。サイズnの配列をm 回変更した場合、最悪のケースではパフォーマンス特性が低下します。 コピーオンライトメモリ管理は、更新にかかるコストを から に削減できます。ここで、Bはメモリブロックサイズ、u は1回の操作で更新されるページ数です。 お（n⋅メートル）{\displaystyle O(n\cdot m)}Θ（n）{\displaystyle \Theta (n)}お（Bあなた）{\displaystyle O(Bu)}

ファットノード

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

ファットノードの複雑さ

ファットノード方式を使用すると、変更ごとに O(1) のスペースが必要になり、新しいデータを保存するだけです。変更ごとに、変更を変更履歴の最後に保存するために O(1) の追加時間がかかります。これは、変更履歴が成長可能な配列に格納されていると仮定した、償却時間境界です。アクセス時に、構造を走査しながら各ノードの正しいバージョンを見つける必要があります。m回の変更が行われた場合、配列で最も近い変更を見つけるコストにより、各アクセス操作の速度が低下します。代わりに、各ノードでファン・エムデ・ボアズ木(ハッシュを使用したスペース効率の高いバージョンの可能性あり) を使用して、更新時間を まで増やすことで、アクセス時間を まで短縮できます。部分的な永続性のみが必要な場合は、ランダム化と償却を法として、更新時間を元の大きさのオーダーに保つことができます (ファットノードへの単一の更新時間は期待どおりに償却できるため[ 6 ] )。 お（ログ⁡メートル）{\displaystyle O(\log m)}お（ログ⁡ログ⁡メートル）{\displaystyle O(\log \log m)}お（ログ⁡ログ⁡メートル）{\displaystyle O(\log \log m)}お（1）{\displaystyle O(1)}

パスのコピー

この手法では、データ構造がノードのリンクグラフであると仮定します。更新時には、変更対象となるノードへのパス上にあるすべてのノードのコピーが作成されます。これらの変更は、データ構造を通じてカスケードされ、古いノードを指していたすべてのノードは、新しいノードを指すように変更されます。これらの変更によってさらにカスケードされた変更が発生し、ルートノードに到達するまでこれが繰り返されます。

パスコピーの複雑さ

m回の変更の場合、追加検索時間はO(log m)になります。変更時間とメモリ使用量は、データ構造内の任意のノードの最大祖先数と、一時データ構造における更新コストの積によって制限されます。親ポインタのないバランス型二分探索木では、最悪の場合の変更時間計算量はO(log n + 更新コスト)です。しかし、リンクリストでは、最悪の場合の変更時間計算量はO(n + 更新コスト)です。

組み合わせ

Driscoll、Sarnak、Sleator、Tarjanは[ 1 ] 、ファットノードとパスコピーの技術を組み合わせることで、アクセス速度をO(1)に抑え、変更ごとに空間と時間の償却オーバーヘッドをO(1)に抑える手法を考案した。彼らの手法では、各ノードへのポインタが最大d個（ dは既知の定数） であるリンクデータ構造を仮定している。

各ノードには、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 減少します。) 最後のステップでは、変更ボックスが満たされ、時間がかかり、ϕ が1 増加します。

これらをまとめると、ϕの変化はΔϕ =1 − kとなる。したがって、このアルゴリズムはO( k +Δϕ ) = O(1)の空間とO( k +Δϕ +1 ) = O(1)の時間を要する。

持続性の一般化形式

パスコピーは、二分探索木などの特定のデータ構造において永続性を実現するための簡単な方法の一つです。任意のデータ構造で動作する永続性を実装するための一般的な戦略があれば便利です。これを実現するために、有向グラフGを考えます。 Gの各頂点vには、ポインタで表される定数c 個の出力エッジがあると仮定します。各頂点には、データを表すラベルが付けられます。頂点には、その頂点に繋がるエッジの数が制限されているd個があり、これを inedges( v )と定義します。 Gに対して、以下の異なる操作を許可します。

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

上記の操作はいずれも特定の時間に実行され、永続的なグラフ表現の目的は、いつでもGの任意のバージョンにアクセスできるようにすることです。この目的のために、 Gの各頂点vに対してテーブルを定義します。テーブルにはc列とc行が含まれます。各行には、出力エッジへのポインタに加えて、頂点のデータを表すラベルと、操作が実行された時刻t が含まれます。さらに、vへのすべての入力エッジを追跡する配列 inedges( v ) があります。テーブルがいっぱいになると、行を含む新しいテーブルを作成できます。古いテーブルは非アクティブになり、新しいテーブルがアクティブ テーブルになります。 d+1{\displaystyle d+1}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つのクレジットが格納され、テーブルには行数と同じ数のクレジットが格納されます。この不変条件がCREATE-NODE、CHANGE-EDGE、CHANGE-LABELの3つの操作すべてに適用されることを確認しましょう。

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

まとめると、CREATE_NODE とCHANGE_EDGE を呼び出すと、テーブルが作成されるという結論になります。各テーブルのサイズは再帰呼び出しを考慮に入れなくても であるため、テーブルへの入力には が必要です。したがって、一連の操作を完了するために必要な作業量は、作成されるテーブルの数に を掛けた値で制限されます。各アクセス操作は で実行でき、エッジ操作とラベル操作はm個あるため、 が必要です。結論として、 で任意のn回の CREATE-NODE、CHANGE-EDGE、および CHANGE-LABEL のシーケンスとm 回のアクセス操作を完了できるデータ構造が存在することになります。 n1{\displaystyle n_{1}}n2{\displaystyle n_{2}}2⋅n1+n2{\displaystyle 2\cdot n_{1}+n_{2}}お（d）{\displaystyle O(d)}お（dc）{\displaystyle O(dc)}お（dc）{\displaystyle O(dc)}お（ログ⁡（d））{\displaystyle O(\log(d))}メートル⋅お（ログ⁡（d））{\displaystyle m\cdot O(\log(d))}お（n⋅dc）+メートル⋅お（ログ⁡（d））{\displaystyle O(n\cdot dc)+m\cdot O(\log(d))}

永続データ構造の応用

次の要素の検索またはポイントの位置

永続性を用いて効率的に解ける有用な応用例の一つに、次要素探索があります。x軸に平行で、互いに交差せず、かつn本の線分が交わらないと仮定します。点pをクエリし、 pより上の線分（もしあれば）を返すデータ構造を構築します。まず、ナイーブな手法を用いて次要素探索を解き、次に永続的なデータ構造を用いて解く方法を説明します。

ナイーブな方法

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

永続データ構造方式

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

永続データ構造の例

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

赤黒木[ 7 ] 、スタック[ 8 ]、トリップ[ 9 ]など、多くの一般的な参照ベースのデータ構造は、簡単に永続バージョンを作成できます。キュー、デキュー、そして最小デキュー（最小要素を返すO(1)演算minを追加）やランダムアクセスデキュー（線形以下、多くの場合対数的な計算量を伴うランダムアクセス演算を追加）などの拡張機能など、その他のデータ構造には、もう少し手間がかかります。

不変 (「純粋関数型」) 構造に基づく永続データ構造は、破壊的な更新 (突然変異) を使用し、前述のファット ノードまたはパスのコピー手法を使用して永続化された構造とは対比される必要があります。

リンクリスト

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

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

xs = [0, 1, 2] ys = [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]

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

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

fun insert ( x , E ) = T ( E , x , E ) | insert ( x , s as T ( a , y , b )) = if x < y then T ( insert ( x , a ), y , b ) else if x > y then T ( a , y , insert ( x , b )) else s

実行後 

ys = 挿入 ("e", xs)

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

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

永続ハッシュ配列マップトライ

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

ハッシュ配列マップドトライは、2001年にPhil Bagwellが発表した「理想的なハッシュツリー」という論文で初めて説明されました。この論文では、「挿入、検索、削除の時間は短く一定で、キーセットのサイズに依存せず、操作は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と同様に純粋関数型であり、Haskellは必然的にすべてのデータ構造を永続化します。Elmには、リンクリスト、永続配列、辞書、集合の永続実装が含まれています。[ 24 ]

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

ジャワ

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

JavaScript

人気の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 ]

参照

参考文献

  1. ^ a b Driscoll JR, Sarnak N, Sleator DD, Tarjan RE (1986). 「データ構造の永続化」.第18回ACMコンピューティング理論シンポジウム議事録 - STOC '86 . pp.  109– 121. CiteSeerX  10.1.1.133.4630 . doi : 10.1145/12130.12142 . ISBN 978-0-89791-193-1. S2CID  364871 .
  2. ^ a b Kaplan, Haim (2001). 「永続データ構造」 . 『データ構造とアプリケーションハンドブック』 .
  3. ^ Conchon, Sylvain; Filliâtre, Jean-Christophe (2008)、「半永続データ構造」、プログラミング言語とシステム、コンピュータサイエンスの講義ノート、vol. 4960、Springer Berlin Heidelberg、pp.  322– 336、doi : 10.1007/978-3-540-78739-6_25、ISBN 9783540787389
  4. ^ Tiark, Bagwell, Philip Rompf (2011). RRBツリー: 効率的な不変ベクトル. OCLC 820379112 . {{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)
  5. ^ Brodal, Gerth Stølting; Makris, Christos; Tsichlas, Kostas (2006)、「純粋機能的最悪ケース定数時間連鎖可能ソートリスト」、Algorithms – ESA 2006、Lecture Notes in Computer Science、vol. 4168、Springer Berlin Heidelberg、pp.  172– 183、CiteSeerX 10.1.1.70.1493、doi : 10.1007/11841036_18、ISBN  9783540388753
  6. ^ Lenhof, Hans-Peter; Smid, Michiel (1994). 「永続データ構造を用いた探索問題への範囲制限の付加」RAIRO-理論情報学と応用. 28 (1): 25– 49. doi : 10.1051/ita/1994280100251 .
  7. ^ Neil Sarnak; Robert E. Tarjan (1986). 「Planar Point Location Using Persistent Search Trees」(PDF) . Communications of the ACM . 29 (7): 669– 679. doi : 10.1145/6138.6151 . S2CID 8745316. 2015年10月10日時点のオリジナル(PDF)からのアーカイブ。 2011年4月6日閲覧。 
  8. ^ Chris Okasaki. 「純粋関数型データ構造（論文）」（PDF） .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  9. ^ Liljenzin, Olle (2013). 「合流的持続集合とマップ」. arXiv : 1301.3388 . Bibcode : 2013arXiv1301.3388L .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  10. ^ a bこの例はOkasakiからの引用です。参考文献を参照してください。
  11. ^ a b BoostCon (2017-06-13)、C++Now 2017: Phil Nash「聖杯!? C++のための永続的なハッシュ配列マップトライ」、2021年12月21日時点のオリジナルからアーカイブ、 2018年10月22日取得
  12. ^ Phil, Bagwell (2001). 「理想的なハッシュツリー」 .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  13. ^ 「もう到着したのか？」 InfoQ 。2018年10月22日閲覧。
  14. ^ Steindorfer, Michael J.; Vinju, Jurgen J. (2015-10-23). 「高速かつ効率的な不変JVMコレクションのためのハッシュ配列マップトリップの最適化」 . ACM SIGPLAN Notices . 50 (10): 783– 800. doi : 10.1145/2814270.2814312 . ISSN 0362-1340 . S2CID 10317844 .  
  15. ^ 「Haskell言語」 . www.haskell.org . 2018年10月22日閲覧。
  16. ^ "Data.List" . hackage.haskell.org . 2018年10月23日閲覧。
  17. ^ "Data.Map.Strict" . hackage.haskell.org . 2018年10月23日閲覧。
  18. ^ "Data.Set" . hackage.haskell.org . 2018年10月23日閲覧。
  19. ^ "パフォーマンス/配列 - HaskellWiki" . wiki.haskell.org . 2018年10月23日閲覧。
  20. ^ 「Clojure - 他のLispとの違い」 . clojure.org . 2018年10月23日閲覧。
  21. ^ 「Clojure - データ構造」 . clojure.org . 2018年10月23日閲覧。
  22. ^ 「基調講演：価値の価値」 InfoQ 2018年10月23日閲覧。
  23. ^ "Clojure - Atoms" . clojure.org . 2018年11月30日閲覧。
  24. ^ "core 1.0.0" . package.elm-lang.org . 2018年10月23日閲覧。
  25. ^ "blog/blazing-fast-html-round-two" . elm-lang.org . 2018年10月23日閲覧。
  26. ^ 「JavaとKotlinの永続的（不変）コレクション」 . github.com . 2023年12月13日閲覧。
  27. ^ 「Flux | ユーザーインターフェース構築のためのアプリケーションアーキテクチャ」 . facebook.github.io . 2020年10月27日時点のオリジナルよりアーカイブ。2018年10月23日閲覧。
  28. ^ Mora, Osmel (2016-07-18). 「Reactで状態を処理する方法」 . Reactエコシステム. 2018年10月23日閲覧。
  29. ^ 「Read Me - Redux」 . redux.js.org . 2018年10月23日閲覧。
  30. ^ a b「不変データ - Redux」 . redux.js.org . 2018年10月23日閲覧。
  31. ^ "Immutable.js" . facebook.github.io . 2015年8月9日時点のオリジナルよりアーカイブ。2018年10月23日閲覧。
  32. ^ 「森」。
  33. ^ 「没入」 . GitHub。 2021年10月26日。
  34. ^ Djamboulian, Ara M.; Boizumault, Patrice (1993), The Implementation of Prolog - Patrice Boizumault , Princeton University Press, ISBN 9780691637709
  35. ^有限領域ソルバーの実装のための水銀の使用 - Henk Vandecasteele、Bart Demoen、Joachim Van Der Auwera、1999
  36. ^ 「オブジェクト関数型プログラミングの本質とScalaの実用的な可能性 - codecentric AGブログ」 . codecentric AGブログ. 2015年8月31日. 2018年10月23日閲覧。
  37. ^ ClojureTV (2013-01-07)、Extreme Cleverness: Scala の関数型データ構造 - Daniel Spiewak 、 2018年10月23日閲覧。
  38. ^ “ウラジミール・コスチュコフ - 投稿/スライド” . kostyukov.net 。2018年11月30日に取得。
  39. ^ 「不変オブジェクトとガベージコレクション」 . wiki.c2.com . 2018年11月30日閲覧。
  40. ^ 「Javaパフォーマンスの最後のフロンティア：ガベージコレクターの削除」 InfoQ 2018年11月30日閲覧。
「 https://en.wikipedia.org/w/index.php?title=Persistent_data_structure&oldid=1335321381」から取得