2010-02-09 7 views
8

Sto cercando una struttura dati simile a un dizionario che restituisca l'insieme di tutti gli elementi correlati a una chiave.Esiste una struttura dati che contiene insiemi di dati in .NET?

Ad esempio, userei così:

var data = new FancyDataStructure(); 

data.Add(new string[] {"Elizabeth", "Liz", "Betty"}); 
data.Add(new string[] {"Bob", "Robert", "Rob"}); 

string[] alternateNames1 = data["Betty"]; 
string[] alternateNames2 = data["Liz"] 

In questo caso, alternateNames1 sarebbe una matrice contenente "Liz" e "Elizabeth", e alternateNames2 sarebbe una matrice contenente "Elizabeth" e "Betty".

Non voglio reinventarlo, ma non ho trovato alcun esempio di tale struttura.

Aggiornamento

Grazie a coloro che hanno scritto di nuovo con suggerimenti. Molte persone hanno suggerito di utilizzare una versione di Dictionary<string, IEnumerable<string>>. Attualmente sto usando questo approccio, ma in realtà non soddisfa il requisito senza essere terribilmente difficile da mantenere. Ogni valore in ogni elenco deve essere in grado di funzionare come chiave per ogni altro valore aggiunto ad esso in un set.

Così, dato il seguente:

data.Add(new string[] {"Elizabeth", "Liz"} 
data.Add(new string[] {"Liz", "Betty"} 
alternates = data["Betty"]; 

mi aspetterei alterna a ora contengono "Elizabeth" e "Liz."

Sembra che potrei dover costruire una struttura del genere per soddisfare le mie esigenze. Tieni comunque le idee in arrivo!

Brian

+0

Duplicato di http://stackoverflow.com/questions/10458/is-there-a-set-data-structure-in-net – Eloff

+2

Non credo che sia un duplicato. Questo non richiede una struttura Set di per sé. –

risposta

1

Il tuo problema suona come esso è davvero un problema graphing. Pensa ai nomi come nodi e all'appartenenza all'insieme come ai bordi. Da questo punto di vista, si vorrebbe una struttura dati che gestisca bene i grafici sparsi, come ad esempio un adjacency list. Questo è, ovviamente, simile a quello che stai già facendo con uno Dictionary<string, IEnumerable<string>> ma pensarci in questo modo potrebbe portarti ad alcune utili implementazioni e algoritmi.

+0

Penso che probabilmente hai ragione nel trattarlo come qualcosa che non può essere facilmente composto da strutture esistenti. Ho già trovato una soluzione ai miei bisogni, ma se avrò ancora un po 'di tempo cercherò di costruire questa nuova struttura e postare qui se trovo qualcosa di utile. –

1

namespace System.Collections.Generic ei System.Collections sono caricati con dizionari coppia KeyValue, ordinati dizionari, Elenca oggetti e molto altro ancora.

System.Collections.Generic.Dictionary<int, string> dic = new Dictionary<int, string>(); 
     dic.Add(1, test); 

o un elenco nidificato all'interno di un dizionario

Dictionary<string, List<string>> dic = new Dictionary<string, List<string>>(); 
List<string> alternatives = new List<string>(); 
alternatives.Add("Brenda"); 
dic.Add("Betty", alternatives); 
0

Qualcosa di simile sembra abbastanza semplice.

var data = new List<string[]>(); 

data.Add(new string[] {"Elizabeth", "Liz", "Betty"}); 
data.Add(new string[] {"Bob", "Robert", "Rob"}); 

var alternateNames1 = data.Where(x =>x.Contains("Betty")).Select(x => x.Where(y => y != "Betty")); 
+0

Questo non verrà ridimensionato per "set" di grandi dimensioni, avrete ancora O (n) ricerche; se è OK, allora vai. –

0

lo standard de facto alt.net è in Iesi.Collections, ma la libreria di classi di base ha solo HashSet<T> in dotnet 3.5 o superiore.

Ho usato clausole simili a "group by" in linq per rimuovere facilmente i duplicati da raccolte arbitrarie IEnumerable<T>, ma questo non ti dà abbastanza semantica.

HashSet <> è vicino a ciò che si desidera.

In base alle vostre esigenze, non penso ci sia qualcosa che possa mappare le stringhe su raccolte preesistenti; in pratica, dovresti scrivere una classe che utilizza un metodo come StoreAssociations<<T>>(IEnumerable<<T>> names), converte IEnumerable in HashSet e itera su ogni elemento in HashSet per aggiungere una mappatura in un IDictionary<string,HashSet<T>> all'hashset appena creato.

-1

Io uso questo:

Ha un generico insieme < un tipo > e implementa tutte le belle iteratori, .Contains, Count, ecc

+0

cosa ha il set C5 su Bash Hashset? – Jimmy

+1

-1: il titolo di OP potrebbe essere un po 'fuorviante, ma la sua domanda non lo è. OP non vuole una classe impostata, vuole un tipo speciale di dizionario che mappa più chiavi con lo stesso valore. – Juliet

+0

HashSet non esiste nei vecchi framework :-) (prima del relativamente nuovo 3.5) –

0

vorrei solo utilizzare il tipo Dictionary<string, IEnumerable<string>>. Per costruire questa struttura da una lista di liste, si potrebbe avere codice come questo:

var alternateNames = new string[][] { 
    new string[] { "Elizabeth", "Liz", "Betty" }, 
    new string[] { "Bob", "Robert", "Rob" }, }; 
var altNameLookup = 
    (
     from nameList in alternateNames 
     from name in nameList 
     select new { 
      Name = name, NameList = nameList.Except(new string[] { name }) } 
    ).ToDictionary(o => o.Name, o => o.NameList); 
1

Solo un pensiero in un'altra direzione - dataset fortemente tipizzati sembrano avere un sacco di cose per loro. E serializzati come array di byte, sono piuttosto veloci per lo spostamento di dati strutturati multidimensionalmente.

iterazione e la capacità di Linq sono una sorta di costruito in.

Forse eccessivo per un sacco di cose, ma ho un certo numero di posti in cui ho conservato l'intero set di dati in un unico varbinary (max) columnn in SQL.

0

Fondamentalmente si dispone di un dizionario in cui più chiavi si associano allo stesso valore. Non c'è nessuna struttura di dati incorporato che supporta l'operazione che si desidera, ma è facile per rappresentare come Dictionary{string, HashSet{string}} in .NET:

static void AddNames(Dictionary<string, HashSet<string>> map, params string[] names) 
{ 
    for (int i = 0; i < names.Length; i++) 
    { 
     HashSet<string> value; 
     if (!map.TryGetValue(names[i], out value)) 
     { 
      value = new HashSet<string>(); 
      map.Add(names[i], value); 
     } 

     for (int j = 0; j < names.Length; j++) 
     { 
      value.Add(names[j]); 
     } 
    } 
} 

static void Main(string[] args) 
{ 
    Dictionary<string, HashSet<string>> names = new Dictionary<string,HashSet<string>>(); 
    AddNames(names, "Chris", "Christopher"); 
    AddNames(names, "Christina", "Chrissy", "Chris"); 

    HashSet<string> relatedToChris = names["Chris"];    // gets "Chris", "Christina", "Chrissy", "Christopher"; 
    HashSet<string> namesRelatedToChristinia = names["Christina"]; // gets "Christina", "Chrissy", "Chris"; 
} 

si può pensare della vostra datastructure come un grafo orientato in cui ogni nodo ha un vantaggio connesso al suo nome correlato. Dato che ci sono n^2 bordi, il dizionario richiede O (n^2) tempo per inserire e memoria. Non è possibile ridurre il tempo di ricerca a qualcosa di meglio.

Fortunatamente, dal momento che è stato implementato come dizionario, le ricerche sono ancora O (1). Le cancellazioni sono O (m) dove m è il numero di valori relativi a una chiave.

+0

Sembra che qui ci sia un hash distinto per ogni chiave, anche se per diverse chiavi correlate il contenuto dei loro hashset è lo stesso. Di conseguenza hai un inserimento così elevato e cancelli la complessità. Non sarebbe meglio avere un unico hashset condiviso per tutte le chiavi correlate? Quindi inserire O (m) (assumendo O (1) ricerche di chiavi) e delete sarebbe O (1). –

-1

Provare a usare un dizionario, qualcosa come:

Dictionary<string, List<string>> 

Così un dizionario di chiavi di stringa con i valori della lista

0

ne dite di un paio di strutture di dati: Dictionary<string, Guid> e Dictionary<Guid, List<string>>

Per aggiungere un paio di chiavi (a, b) [si può scomporre un grande add in coppie (1 + 2, 2 + 3, ...] procedere come segue: -

Ricerca a e b nel primo dizionario.
Se nessuno dei due esiste, creare un nuovo Guid e aggiungere (a, g) e (b, g) al primo dizionario e (g, Elenco {a}) e (g, Elenco {b}) al secondo dizionario.

Se ne esiste uno, prendi a, prendi il guid da esso (g) e aggiungi l'altro (b, g) al primo dizionario e metti b alla fine dell'elenco trovato in [g] nel secondo dizionario .

Se entrambi esistono E hanno lo stesso guid - niente da fare.

Se entrambi esistono e hanno guidi diversi è necessario unire i due set // Questo è qualcosa che la maggior parte delle altre soluzioni proposte sembrano mancare // quindi scegli un Guid per eliminare, vai a prenderlo dal secondo dizionario , aggiungere l'elenco di stringhe all'altra voce e quindi rimuovere questa voce. Infine, segna tutte le parole nel primo dizionario che erano in quella lista.

Per ottenere tutte le parole correlate, cercare la guida nel primo dizionario e prendere l'elenco dal secondo dizionario.

Ovviamente un valore lungo incrementale statico probabilmente funzionerebbe meglio di un Guid.

+0

Si potrebbe chiamare una "soluzione relazionale" :) che vale la pena espandere sulla complessità algoritmica di ricerca/inserimento/eliminazione nella propria soluzione. –

0

Oppure, dal Lista è un tipo di riferimento che si possa fare quanto segue ...

Dictionary<string, List<string>> dict = new ... 

procedere come segue: -

Per aggiungere una sola associazione (a = b) {decomposta da un elenco delle equivalenze}

Ricerca a e b nel Dizionario

Se nessuno dei due esiste

dict.Add(a, new List<string>(){a}); dict.Add(b, new List<string>(){b}); 

Se ne esiste uno, diciamo, un

var list = dict[a]; 
list.Add(b); 
dict.Add(b, list); 

se sono entrambi presenti e gli elenchi sono la stessa cosa (oggetto confronto) si è fatto.

Se entrambi esiste e gli elenchi sono diversi:

var list1 = dict[a]; 
var list2 = dict[b]; 
list1.AddRange(list2); 
dict.Remove(b); 
dict.Add(b, list1); 
0

Ho scritto un codice, non so quanto efficiente, ma penso che lo fa ciò che si vuole.

è la vostra struttura

class FancyDataStructure 
{ 
    private IDictionary<string, HashSet<string>> dictionary 
     = new Dictionary<string, HashSet<string>>(); 

    public void Add(params string[] names) 
    { 
     HashSet<string> set = new HashSet<string>(names); 
     for (int i = 0; i < names.Length; i++) 
     { 
      if (!dictionary.ContainsKey(names[i])) 
      { 
       dictionary.Add(names[i], set); 
      } 
      else 
      { 
       HashSet<string> union = 
       new HashSet<string>(set.Union<string>(dictionary[names[i]])); 
       set = union; 
       foreach (string oldName in dictionary[names[i]]) 
       { 
        dictionary[oldName] = union; 
       } 
       for (int j = 0; j < i; j++) 
       { 
        if (!dictionary.ContainsKey(names[j])) 
        { 
         dictionary.Add(names[j], union); 
        } 
       } 
      } 
     } 
    } 

    public string[] this[string key] 
    { 
     get 
     { 
      List<string> result = dictionary[key].ToList<string>(); 
      result.Remove(key); 
      return result.ToArray(); 
     } 
    } 
} 

e si può usare, come questo

static void Main(string[] args) 
    { 

     FancyDataStructure data = new FancyDataStructure(); 

     data.Add("Elizabeth", "Liz"); 
     data.Add("Liz", "Betty"); 

     string[] alternates = data["Betty"]; 
     foreach (var item in alternates) 
     { 
      Console.WriteLine(item); 
     } 
    } 
Problemi correlati