Zbiór C# Set?

Jeśli używasz. NET 3.5, możesz użyć HashSet<T>. To prawda, że. NET nie obsługuje zestawów tak dobrze, jak Java.

Wintellect PowerCollections może również pomóc.

Struktura danych HashSet<T>:

Struktura danych biblioteki klas Framework HashSet<T> została wprowadzona w. NET Framework 3.5. Pełna lista jej członków znajduje się na stronie referencyjnej MSDN dlaHashSet<T>.

HashSet<T> jest mniej lub bardziej wzorowany na zbiorze matematycznym , co oznacza, że:

1. Nie może zawierać zduplikowanych wartości.

2. Jego elementy nie są w określonej kolejności, dlatego Typ nie wdrożyć IList<T> interfejs, ale bardziej podstawowy ICollection<T>. W konsekwencji elementy wewnątrz zestawu skrótów nie mogą być losowo dostępne za pomocą indeksów; mogą być tylko iterowane przez enumerator.

3. Niektóre funkcje zestawu, takie jak Union, Intersection, IsSubsetOf, IsSupersetOf są dostępne. Mogą się one przydać podczas pracy z wieloma zestawami.

Inną różnicą między HashSet<T> i List<T> jest wywołanie metody Add(item) zbioru hash Zwraca wartość logiczną: true jeśli element został dodany i false w przeciwnym razie (ponieważ został już znaleziony w zestawie).

Dlaczego nie List<T>?

Ponieważ HashSet<T> jest po prostu zbiorem unikalnych obiektów, możesz się zastanawiać, dlaczego musi to być struktura danych. Normalny List<T> może mieć takie samo zachowanie, sprawdzając, czy obiekt znajduje się na liście przed dodaniem go.

Krótka odpowiedź to szybkość. Przeszukiwanie normalnego List<T> staje się bardzo powolne, bardzo szybkie, ponieważ więcej elementy są dodawane. A HashSet<T> wymaga projektu struktury, która pozwoli na szybkie wyszukiwanie i szybkość wstawiania.

Benchmarki:

Porównajmy szybkość działania HashSet<T> vs. a List<T>.

Każda próba polegała na dodaniu liczb całkowitych od 0 do 9999 do każdej kolekcji. Jednak mod 25 został zastosowany do każdej liczby całkowitej. Mod 25 sprawia, że maksymalne typy przedmiotów 25. Ponieważ dodano 10 000 elementów, zmusiło to do wystąpienia 400 Kolizji, dając dane struktury szansą na wykorzystanie swoich algorytmów wyszukiwania. Czasy były mierzone 3 razy po 10 000 próbach i uśrednione.

Nie zwracaj zbyt dużej uwagi na konkretne czasy uruchamiania testów, ponieważ są one zależne od mojego sprzętu, ale spójrz na to, jak się ze sobą porównują.

           Average time [ms]
----------------------------
HashSet<T>             2,290
List<T>                5,505

Teraz zróbmy elementy obiektów zamiast prymitywnych typów. Napisałem szybką Person klasę z trzema polami: Name, LastName, i ID. Ponieważ nie uwzględniłem żadnego konkretnego sposobu porównywania obiekty, wszystkie elementy zostaną dodane bez kolizji. Tym razem 1000 Person obiektów zostało dodanych do każdej kolekcji w ramach jednej próby. Całkowity czas 3 zestawów 1000 prób został uśredniony.

           Average time [ms]
----------------------------
HashSet<Person>          201
List<Person>           3,000

Jak widać, różnica w czasie pracy staje się astronomiczna przy użyciu obiektów, dzięki czemu HashSet<T> jest korzystna.

Jeśli używasz. NET 4.0 lub nowszego:

W przypadku, gdy potrzebujesz sortowania, użyj SortedSet<T>. W przeciwnym razie, jeśli tego nie zrobisz, użyj HashSet<T> ponieważ jest to O(1) dla operacji wyszukiwania i manipulowania. Natomiast SortedSet<T> jest O(log n) dla operacji wyszukiwania i manipulowania.

Używam Iesi.Kolekcje http://www.codeproject.com/KB/recipes/sets.aspx

Jest używany w wielu projektach OSS, po raz pierwszy natknąłem się na niego w NHibernate

Używam wrappera wokół Dictionary<T, object>, przechowującego null w wartościach. Daje to o(1) add, lookup I remove na klawiszach i do wszystkich celów działa jak zestaw.

Zapraszamy do zapoznania się z naszą ofertą. Oprócz zestawu i OrderedSet posiada kilka innych przydatnych typów kolekcji, takich jak Deque, MultiDictionary, Bag, OrderedBag, OrderedDictionary i OrderedMultiDictionary.

Aby uzyskać więcej zbiorów, istnieje również C5 Generic Collection Library.

Jak już wspomnieli inni, nie wydaje się, aby w standardzie.NET istniała implementacja zestawu z semantyką zestawu.

Zobacz to pytanie Dlaczego {[2] }nie zawsze jest pożądane jako implementacja zestawu.

Jeśli jesteś zainteresowany włączeniem własnej klasy set, oto jedno proste podejście:

public sealed class MathSet<T> : HashSet<T>, IEquatable<MathSet<T>>
{
    public override int GetHashCode() => this.Select(elt => elt.GetHashCode()).Sum().GetHashCode();

    public bool Equals(MathSet<T> obj) => SetEquals(obj);

    public override bool Equals(object obj) => Equals(obj as MathSet<T>);

    public static bool operator ==(MathSet<T> a, MathSet<T> b) =>
        ReferenceEquals(a, null) ? ReferenceEquals(b, null) : a.Equals(b);

    public static bool operator !=(MathSet<T> a, MathSet<T> b) => !(a == b);
}

Przykładowe użycie:

var a = new MathSet<int> { 1, 2, 3 };
var b = new MathSet<int> { 3, 2, 1 };

var c = a.Equals(b);                        // true

var d = new MathSet<MathSet<int>> { a, b }; // contains one element

var e = a == b;                             // true

Możesz zaimplementować własną, wykonalną implementację zestawu w ciągu kilku godzin. Użyłem tego, gdy musiałem to zrobić (przepraszam, nie mam pod ręką kodu): http://java.sun.com/j2se/1.4.2/docs/api/java/util/Set.html

Wiem, że to stary wątek, ale napotkałem ten sam problem i uznałem HashSet za bardzo zawodny, ponieważ biorąc pod uwagę ten sam seed, GetHashCode () zwrócił różne kody. Pomyślałem więc, dlaczego po prostu nie użyć listy i nie ukryć metody dodawania w ten sposób

public class UniqueList<T> : List<T>
{
    public new void Add(T obj)
    {
        if(!Contains(obj))
        {
            base.Add(obj);
        }
    }
}

Ponieważ List używa metody Equals wyłącznie do określenia równości, możesz zdefiniować metodę Equals na twoim typie T, aby upewnić się, że uzyskasz pożądane wyniki.