3

効率的なインデックス付き永続データ構造を探しています。私は通常.NETで作業し、FSharpのマップを認識していますが、その実装と私が認識している他のほとんどは、マッピングの左側である単一の「インデックス」のみを提供しています。

基本的にシナリオはこちら

public class MyObject
    public int Id { get; }
    public int GroupId { get; }
    public string Name { get; }

オブジェクトの Id は、追加されたアイテムのグローバルに一意のセットになります。GroupId の値が重複している可能性があります。一致する GroupId を持つすべての値を照会できるようにしたいと考えています。GroupId 内の名前は一意ですが、異なる GroupId 間で重複する可能性があります。これは、特定のフィールド値に基づいてアイテムのグループに個別にアクセスする必要があるため、3 つのフィールドの複合キーを単純に作成できる状況ではありません。

私はこれを行うことができ、過去に、STackoverflowの他の投稿で推奨されている辞書の辞書を使用していました...ただし、データ構造も1）完全に永続的であり、2）効率的であることを望んでいますメモリ内 - バージョンはできるだけ多くのノードを共有する必要があることを意味します 3) 変更が効率的 - 高速にしたい

ここでかなりのことを求めていることは承知していますが、車輪の再発明がすでに行われている場合は、それを再発明しようとさえしないようにお願いしたかったのです。

ありがとう

4

3 に答える 3

2

なぜ他の場所で、そしてあなたの質問への既存の回答で、人々は既存の構造を併合することを勧めているのかわかりません。複雑な構造 (マップのマップ、リストのマップ、辞書の辞書など) は、一方が他方より緩い場合にのみ 2 つのインデックスに対して機能します (Index1 の同じインデックスを持つ 2 つの値は、これら 2 つの値が Index2 の同じインデックスを持つことを意味します)。 )、これは不要な制約です。

異なるインデックスが必要な数のマップのレコードを使用し、マップに存在するすべての値が同じレコード内の他のすべての値に存在するという不変条件を維持します。値を追加するには、レコード内のすべてのマップに値を追加する必要があります。取り外しも同様。不変式は、カプセル化によって外部からの違反を不可能にすることができます。

データ構造に格納された値が重複するのではないかと心配している場合は、心配しないでください。各マップにはポインターのみが含まれます。それらはすべて、値の同じ単一表現を指します。共有は、単純な単一インデックス マップの場合と同様に良好です。

于 2009-10-25T01:01:23.303 に答える
0

FPアプリケーションにOOPの原則を適用しようとしているようです。

機能的に考えると、何をしようとしているのですか？

たとえば、リストを使用する場合は、特定のグループ値を持つすべてのオブジェクトをプルするように指示するだけです。

グループごとの高速アクセスが必要な場合は、リストのマップを作成して、グループ内のすべてのオブジェクトをプルアップできます。

さまざまなデータ構造とそれぞれで機能する多くの機能がありますが、最初に、オブジェクト指向ではなく機能的なPOVから問題について考える必要があります。

于 2009-10-24T00:22:18.950 に答える
0

Dictionary of Dictionaries を使用できるのと同じように、F# Map of Maps が必要な場合があると思います。

Map<int, Map<string, MyObject> >  // int is groupid, string is name

多分？整数 ID による高速アクセスも必要かどうかは不明です。

Clojure のライブラリもチェックしてみてください。私は Clojure についてあまり知りませんが、さまざまな効率的な永続データ構造が Clojure の強みの 1 つであるように思われます。

于 2009-10-23T21:38:46.223 に答える