複数のインデックスを持つ効率的なインデックス永続データ構造がありますか

Question

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

基本的にここにシナリオがあります

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）変更で効率的-高速にしたい

私はここでかなり多くのことを求めていることを理解していますが、すでに行われている場合は、車輪の再発明を試みることさえ避けたいと思いました。

ありがとう

Answer 1

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

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

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

Answer 2

辞書の辞書を使用できるのと同じように、たとえばマップのF＃マップが必要な場合があります。例：

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

たぶん？整数IDによる高速アクセスも必要かどうかはわかりません。

Clojureのライブラリもご覧ください。 Clojureについてはあまり知りませんが、効率的な永続データ構造の範囲はClojureの強みの1つであるようです。

Answer 3

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

関数の観点から考えると、何をしようとしているのですか？

たとえば、リストを使用する場合、特定のグループ値を持つすべてのオブジェクトをプルすることをリストに伝えることができます。

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

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