Czy istnieje struktura danych przechowująca zestawy danych w .NET?

Question

Szukam struktury danych podobnej do słownika, który zwraca zestaw wszystkich powiązanych elementów do klucza.

Na przykład, można go użyć w następujący sposób:

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"] 

W tym przypadku alternateNames1 będzie tablica zawierająca „Liz” i „Elżbieta” i alternateNames2 będzie tablica zawierająca „Elżbieta” i "Betty".

Nie chcę tego wymyślać na nowo, ale nie mogłem znaleźć żadnych przykładów takiej struktury.

Aktualizacja

Dziękuję osobom, które zostały napisane z powrotem z sugestiami. Wiele osób zasugerowało użycie wersji Dictionary<string, IEnumerable<string>>. Obecnie używam tego podejścia, ale w rzeczywistości nie spełnia ono wymagań, nie będąc strasznie trudnym do utrzymania. Każda wartość na każdej liście musi być w stanie funkcjonować jako klucz do każdej innej wartości dodanej do niego w zestawie.

Tak więc, biorąc pod uwagę, co następuje: "Liz"

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

spodziewałbym zastępcy do teraz zawierać "Elizabeth", a

Wygląda na to, że mógłbym po prostu zbudować taką konstrukcję, która odpowiadałaby moim potrzebom. Zachowaj pomysły!

Brian

Answer 1

Twój problem brzmi jak to jest naprawdę graphing problem. Pomyśl o nazwach jako węzłach i członkowaniu w zestawie jako krawędziach. Z tego punktu widzenia potrzebujesz struktury danych, która dobrze obsługuje rozrzedzone wykresy, na przykład adjacency list. Jest to oczywiście podobne do tego, co już robisz z Dictionary<string, IEnumerable<string>>, ale myślenie o tym w ten sposób może doprowadzić cię do pewnych przydatnych implementacji i algorytmów.

Answer 2

System.Collections.Generic nazw i System.Collections są ładowane z keyvalue słowników pary, sortowane słowniki, lista obiektów i wiele więcej.

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

lub lista zagnieżdżona wewnątrz słownika

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

Answer 3

Coś jak to wydaje się dość prosta.

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")); 

Answer 4

de facto standardem alt.net jest w Iesi.Collections, ale biblioteka klasa bazowa ma tylko HashSet<T> w dotnet 3.5 lub wyższej.

Użyłem klauzul "grupuj według" jak w linq, aby łatwo usunąć duplikaty z dowolnych kolekcji IEnumerable<T>, ale to nie daje ci kompletnej semantyki.

HashSet <> jest zbliżony do tego, co chcesz.

W zależności od wymagań nie sądzę, że istnieje coś z półki, które odwzorowuje ciągi do wcześniej istniejących kolekcji; w zasadzie należałoby napisać klasę, która przyjmuje metodę taką jak StoreAssociations<<T>>(IEnumerable<<T>> names), konwertuje IEnumerable na HashSet i iteruje po każdym elemencie w HashSet, aby dodać mapowanie w IDictionary<string,HashSet<T>> do nowo utworzonego hashsetu.

Answer 5

Używam tego:

• The C5 Generic Collection Library for C# and CLI.

Ma ogólne Set <rodzajem> i realizuje wszystkie piękne iteratorów, .Contains, .Count itp

Answer 6

chciałbym po prostu użyć typu Dictionary<string, IEnumerable<string>>. Aby zbudować tę strukturę z listy list, można mieć kod jak poniżej:

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); 

Answer 7

tylko myśl w innym kierunku - silnie wpisane zestawów danych wydaje się, że dużo się dzieje dla nich. Serializowane w postaci tablic bajtowych są dość szybkie do przenoszenia danych wielowymiarowych.

Iteracja i zdolności LINQ są rodzajem wbudowany.

Może przesadą na wiele rzeczy, ale mam kilka miejsc, gdzie cały zbiór danych przechowywanych w ten jeden varbinary (max) columnn w SQL.

Answer 8

Masz po prostu słownik, w którym wiele klawiszy odwzorowuje tę samą wartość. Nie ma wbudowany w strukturę danych, która obsługuje operację chcesz, ale jest łatwy do reprezentowania jako Dictionary{string, HashSet{string}} w .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"; 
} 

można myśleć o swojej datastructure jako graf skierowany, gdzie każdy węzeł ma przewagę podłączony do powiązanej nazwy. Ponieważ istnieją krawędzie n^2, słownik wymaga czasu O (n^2) do wstawienia i pamięci. Nie można skrócić czasu wyszukiwania do niczego lepszego.

Na szczęście, ponieważ jest zaimplementowany jako słownik, sprawdza się jako wciąż O (1). Usuwane są O (m) gdzie m jest liczbą wartości związanych z kluczem.

Answer 9

Spróbuj użyć słownika, coś jak:

Dictionary<string, List<string>> 

więc Słownik kluczy ciąg z wartościami Lista

Answer 10

Jak o parę struktur danych: Dictionary<string, Guid> i Dictionary<Guid, List<string>>

Aby dodać para kluczy (a, b) [możesz rozłożyć większy dodatek na pary (1 + 2, 2 + 3, ...) postępować w następujący sposób: -

Wyszukiwanie aib w pierwszym słowniku.
Jeśli nie istnieje, utwórz nowy Guid i dodaj (a, g) i (b, g) do pierwszego słownika i (g, Lista {a}) i (g, Lista {b}) do drugiego słownika.

Jeśli taki istnieje, powiedz a, wyjmij z niego guid (g) i dodaj drugi (b, g) do pierwszego słownika, a następnie dosuń b na koniec listy znalezionej w [g] w drugim słowniku .

Jeśli oba istnieją i mają ten sam przewodnik - nic nie można zrobić.

Jeśli oba istnieją i mają różne guidy, konieczne jest scalenie dwóch zestawów // To jest coś, czego większość z proponowanych rozwiązań wydaje się brakować // wybierz Guida, aby go wyeliminować, przejdź do drugiego słownika , dodaj listę ciągów do innego wpisu, a następnie usuń ten wpis. Na koniec zaznacz wszystkie słowa w pierwszym słowniku, które znajdowały się na tej liście.

Aby uzyskać wszystkie powiązane słowa, wyszukaj Guid w pierwszym słowniku i chwyć listę z drugiego słownika.

Oczywiście zwiększanie wartości statycznej o dużej wartości prawdopodobnie działałoby lepiej niż Guid.

Answer 11

Albo, ponieważ lista jest rodzajem odniesienia można zrobić następujących ...

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

postępować w następujący sposób: -

Aby dodać pojedynczy związek (a = b) {rozłożony od A lista ekwiwalencyjne}

Lookup a i b w Słowniku

Jeśli nie istnieje

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

Jeśli taki istnieje, powiedzmy,

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

Jeśli oba istnieją i wykazy są takie same (object porównać) gotowe.

Jeśli zarówno istnieje i wykazy są różne:

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

Answer 12

pisałem jakiś kod, nie wiem, jak skuteczne to, ale myślę, że robi to, co chcesz.

To wasza struktura

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(); 
     } 
    } 
} 

i można go używać, jak to

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); 
     } 
    }