.NET フレームワークで使用できるように、F# で永続的 (純粋に関数型、不変型など) の成長可能なベクターを実装することに興味があります。私の現在の実装は、Hash-Mapped Trie のバリアントであり、 Clojure の実装に従って行われます。
この実装を使用して、ランダムアクセスの挿入と削除 (ランダムなインデックスでの要素の挿入と削除) を実装するのに問題があります。これらの操作を効率的に可能にするアルゴリズム/変更、または私が見ることができる他の実装はありますか?
明確化：「挿入」と「削除」と言うとき、たとえば、リストが与えられた場合、位置に[1; 2; 3; 4]挿入すると. または操作を意味するものではありません。5001[1:500:2:3:4]setassociate
指の木はあなたが探しているものかもしれません. 利用可能なClojure 実装があります。
不変のベクトル/リストは通常、一方の端で挿入のみを許可し、もう一方の端で不変データを共有することにより、高速更新を提供します。ヘッド/テール以外の挿入を行いたい場合、実際にやりたいことは、コレクションの不変の最後を変更することです。挿入するアイテムの周りでベクターを分割し、それをつなぎ合わせて新しいベクターを作成する必要があります。これを実行できるのはO(n)時間です。
不変の並べ替えられたツリーの動作は少し異なりますが、O(n)時間未満でインデックス (キー) の番号を付け直すこともできません。
基本的に、誰かが不変ベクトルでのランダムアクセス挿入をサポートする効率的な方法を発見した場合、それは主流の関数型言語の 1 つでサポートされますが、そのような既知のデータ構造やアルゴリズムがないため、そのような実装はありません。
できることは、分割して結合することだけです。これは、clojure ベクターでは非常に効果的ではありません。これが、Phill Bagwell が log(n) で分割および結合できる永続的なベクトルを実装した理由です。
このビデオをご覧になることをお勧めします: http://blip.tv/clojure/phill-bagwell-striving-to-make-things-simple-and-fast-5936145
または、彼の論文に直接アクセスしてください: infoscience.epfl.ch/record/169879/files/RMTrees.pdf
Haskell HAMT ライブラリを移植しますか? 挿入操作はO ( log n)