Esiste una struttura dati persistente di indice efficiente con più indici

Question

Sto cercando una struttura di dati persistente indicizzata efficiente. In genere lavoro in .NET e sono a conoscenza di Map di FSharp, tuttavia l'implementazione e la maggior parte degli altri di cui sono a conoscenza forniscono un solo 'indice', il lato sinistro del mapping.

Fondamentalmente ecco lo scenario

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

Dove l'ID di un oggetto sarà un insieme univoco globale di elementi aggiunti. GroupId può avere valori duplicati e desidero essere in grado di eseguire una query per tutti i valori con un GroupId corrispondente e all'interno di un GroupId i nomi saranno univoci ma potrebbero essere duplicati su GroupId diversi. Questa non è una situazione in cui posso semplicemente creare una chiave composita dei 3 campi in quanto ho bisogno di un accesso indipendente a gruppi di elementi in base a valori di campo particolari.

Posso farlo, e in passato, usando dizionari di dizionari, che è stato raccomandato in altri post qui su STackoverflow ... tuttavia, voglio anche che la struttura dei dati sia 1) Completamente persistente e tutto ciò che significa 2) efficiente in memoria, il che significa che le versioni devono condividere il maggior numero possibile di nodi 3) efficiente nelle modifiche - vorrei che fosse veloce

Mi rendo conto che sto chiedendo un bel po 'qui, ma volevo evitare di provare anche a reinventare la ruota se è già stata fatta.

Grazie

Answer 1

Non sono sicuro del perché altrove, e nelle risposte esistenti alla tua domanda, le persone raccomandano di imbricare le strutture esistenti. Le strutture imbricanti (mappe di mappe, mappe di elenchi, dizionari di dizionari, ...) funzionano solo per due indici se uno è più libero dell'altro (due valori con lo stesso indice per Index1 implica che questi due valori hanno lo stesso indice per Index2 ), che costituisce un vincolo inutile.

Userei un record di mappe, quante ne desideri quante indici diversi, e manterrei l'invariante che ogni valore presente in una mappa è presente in tutte le altre nello stesso record. L'aggiunta di un valore richiede ovviamente l'aggiunta a tutte le mappe nel record. Allo stesso modo per la rimozione. L'invariante può essere reso impossibile da trasgredire dall'esterno attraverso l'incapsulamento.

Se temi che i valori memorizzati nella tua struttura dati vengano duplicati, non farlo. Ogni mappa conterrebbe solo un puntatore. Indicherebbero tutti la stessa singola rappresentazione del valore. La condivisione sarà valida come lo è già con semplici mappe a indice singolo.

Answer 2

Proprio come potresti usare un Dizionario dei dizionari, mi aspetto che ad es. una mappa F # di Maps può essere ciò che desideri, ad esempio

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

forse? Non sono chiaro se è necessario anche un accesso rapido tramite ID intero.

Puoi anche dare un'occhiata alla biblioteca di Clojure; Non so molto di Clojure, ma una serie di efficienti strutture di dati persistenti sembra essere uno dei punti di forza di Clojure.

Answer 3

Sembra che tu stia cercando di applicare i principi OOP alla tua applicazione FP.

Se pensi in termini di funzioni, cosa stai cercando di fare?

Se usi un Elenco, ad esempio, puoi semplicemente dirgli che vuoi estrarre tutti gli oggetti che hanno un certo valore di gruppo.

Se hai bisogno di un accesso rapido per gruppo, potresti avere una Mappa di Elenchi in modo da poter estrarre tutti gli oggetti in un gruppo.

Esistono diverse strutture dati e molte funzioni che funzionano su ciascuna, ma dovresti prima pensare al tuo problema da un POV funzionale, non orientato agli oggetti.