Existe-t-il une structure de données persistante d'index efficace avec plusieurs index

Question

Je recherche une structure de données persistante indexée efficace. Je travaille généralement en .NET et suis conscient de la carte de FSharp, mais cette implémentation et la plupart des autres dont je suis au courant ne fournissent qu’un seul "index", le côté gauche de la cartographie.

En gros, voici le scénario

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

Où l'ID d'un objet sera un ensemble d'éléments globalement unique ajouté. GroupId peut avoir des valeurs en double et je veux pouvoir interroger toutes les valeurs avec un GroupId correspondant et, dans un GroupId, les noms seront uniques mais pourront être dupliqués entre différents GroupId. Ce n'est pas une situation où je peux simplement créer une clé composite des 3 champs car j'ai besoin d'un accès indépendant à des groupes d'éléments basés sur des valeurs de champs particulières.

Je peux le faire et utiliser dans le passé des dictionnaires de dictionnaires, ce qui a été recommandé dans d'autres publications sur STackoverflow ... mais je souhaite également que la structure de données soit 1) Entièrement persistant et tout ce qui signifie 2) efficace en mémoire - ce qui signifie que les versions doivent partager autant de nœuds que possible 3) efficace dans les modifications - je voudrais que ce soit rapide

Je réalise que je demande pas mal de choses ici, mais je voulais demander d'éviter même d'essayer de réinventer la roue si cela a déjà été fait.

Merci

Answer 1

Je ne suis pas sûr de savoir pourquoi ailleurs, et dans les réponses existantes à votre question, les gens recommandent d'imbriquer les structures existantes. Les structures imbriquées (cartes de cartes, cartes de listes, dictionnaires de dictionnaires, ...) ne fonctionnent que pour deux index si l'un est plus lâche que l'autre (deux valeurs ayant le même index pour Index1 impliquent que ces deux valeurs ont le même index pour Index2 ), ce qui est une contrainte inutile.

J'utiliserais un enregistrement de cartes, autant que vous le souhaitez, pour conserver différents index, et je maintiendrais l'invariant selon lequel chaque valeur présente dans une carte est présente dans toutes les autres du même enregistrement. L'ajout d'une valeur nécessite évidemment de l'ajouter à toutes les cartes de l'enregistrement. De même pour l'enlèvement. L’invariant peut être rendu impossible à transgresser de l’extérieur par l’encapsulation.

Si vous craignez que les valeurs stockées dans votre structure de données ne soient dupliquées, ne le faites pas. Chaque carte ne contiendrait qu'un pointeur. Ils indiqueraient tous la même représentation unique de la valeur. Le partage sera aussi bon qu’il l’est déjà avec de simples cartes à un seul index.

Answer 2

De la même manière que vous pourriez utiliser un dictionnaire de dictionnaires, par exemple, une carte F # de cartes peut être ce que vous voulez, par exemple

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

peut-être? Je ne sais pas si vous avez également besoin d'un accès rapide par identifiant entier.

Vous pouvez également consulter la bibliothèque de Clojure; Je ne connais pas grand-chose à propos de Clojure, mais une gamme de structures de données persistantes efficaces semble être l’un des atouts de Clojure.

Answer 3

Il semble que vous tentiez d'appliquer les principes de la programmation orientée objet à votre application de PF.

Si vous pensez en termes de fonctions, qu'est-ce que vous essayez de faire?

Si vous utilisez une liste, par exemple, vous pouvez simplement lui indiquer que vous souhaitez extraire tous les objets ayant une certaine valeur de groupe.

Si vous avez besoin d'un accès rapide par groupe, vous pouvez disposer d'une carte des listes afin de pouvoir afficher tous les objets d'un groupe.

Il existe différentes structures de données et de nombreuses fonctions qui fonctionnent sur chacune d’elles, mais vous devez d’abord penser à votre problème à partir d’un POV fonctionnel et non orienté objet.