BrodalらによるPurely Functional Worst Case Constant Time Catenable Sorted Listsを読んでいます。そして、データ構造のコンテキストにおけるさまざまな種類の永続性への導入は、私に明らかな疑問を残します:
コンフルエントな永続性:すべてのバージョンを更新およびクエリでき、さらに 2 つのバージョンを組み合わせて新しいバージョンを作成できます。この場合、それ自体を繰り返し結合することにより、指数関数的にサイズの構造を多項式時間で作成できることに注意してください。
それ自体を繰り返し結合することにより、多項式時間で「指数関数的にサイズの」構造を作成できる実用的なアプリケーションは何ですか?
使用例を次に示します。配列がまばらであると予想される状況で、汎用の「シーケンス」データ型が配列として使用されていると想像してください (つまり、ほとんどの要素が同じ値を含み、比較的少数のスポットが他の値に設定されます)。シーケンス データ型にこのプロパティがある場合は、言及した手法を使用して (おそらく非常に大きな) 配列を構築できますが、この使用法ではスペースと時間の効率が十分に高くなります。
確かに、特にスパース配列用に専用のデータ型を作成することもできます。おそらく、汎用のデータ型よりもスペースと時間の効率が少し高くなりますが、重要なのは、汎用のデータ型がこの使用法に十分に適合することです。特殊な目的のデータ型を作成する必要さえないかもしれないパターン。
(確かに、この例は一般的な合流持続性に関するものであり、論文の「ソートされたリスト」に関するものではありません。また、論文の中で、彼らは一般的な合流持続性について問題の発言をしていましたが、具体的には独自のデータ構造についてではありませんでした。 .)
私は論文を読みませんでしたが、あなたが提供したConfluent Persistenceの定義を見ると、マージ操作で対数実行時間があり、セットユニオンの種類のアルゴリズムに非常に適している二項ヒープなどのデータ構造に関連付けることができます。ツリーが指数関数的に成長し、二項ヒープを考慮すると、ツリーがいくつかある可能性があり、それぞれを多項式時間でマージできます。和集合演算を実行することは、そのような種類のデータ構造に対して私が感じる最高のアプリケーションであり、多項式時間でもそれです。
あなたの質問は、このプロパティがそのタイプの永続性を示すデータ構造の利点であると述べているように論文を読んでいることを示唆しています。この論文を見ると、それは著者が意図したことではないと思います。それは、読者の楽しみと喜びのために指摘したかった、そのようなデータ構造のやや直観に反する特性にすぎません。
さらなる注意として、著者が話している指数サイズは、メモリ内のサイズではなく、「数学的な」サイズ (抽象的な意味でのノードの数) であると思います。多項式時間でのメモリ位置の指数数!