Wydajna lista unikatowych ciągów C #

86

Jaki jest najskuteczniejszy sposób przechowywania listy ciągów, ignorując wszelkie duplikaty? Pomyślałem, że słownik najlepiej będzie wstawiać ciągi znaków, pisząc dict [str] = false; i wyliczanie za pomocą kluczy w postaci listy. Czy to dobre rozwiązanie?

c# unique-values

111

Jeśli używasz .NET 3.5, zestaw HashSet powinien działać dla Ciebie.

Klasa HashSet <(Of <(T>)>) zapewnia operacje na zestawach o wysokiej wydajności. Zestaw to zbiór, który nie zawiera zduplikowanych elementów i którego elementy nie są w określonej kolejności.

— JP Alioto
źródło

5

Ale HashSetstraci kolejność elementów. Funkcja a Listzapewnia.

— aggsol

4

Dodatkowe: istnieje również SortedSet <T>, który jest wygodnym posortowanym zestawem HashSet.

— WhoIsRich

Należy również zauważyć, że do HashSet nie można uzyskać dostępu za pośrednictwem indeksu, tylko przez moduł wyliczający, a nie List.

— Andrew,

23

Możesz spróbować zrobić coś takiego

var hash = new HashSet<string>();
var collectionWithDup = new []{"one","one","two","one","two","zero"}; 

// No need to check for duplicates as the Add method
// will only add it if it doesn't exist already
foreach (var str in collectionWithDup)
    hash.Add(str);

— Perpetualcoder
źródło

33

Nie potrzebujesz czeku Contains za pomocą HashSet. Możesz po prostu wywołać metodę Add bezpośrednio i zwróci ona wartość true lub false w zależności od tego, czy element już istnieje.

— LukeH

1

Odpowiedź należy edytować, aby usunąć wezwanie do zbędnych Zawartości. To wszystko, czego potrzebujesz, aby powyższy przykład zadziałał: var collectionWithDup = new [] {"one", "one", "two", "one", "two", "zero"}; var uniqueValues = new HashSet <string> (collectionWithDup);

— user3285954

14

Nie jestem pewien, czy liczy się to jako dobra odpowiedź, ale w obliczu potrzeby posiadania unikalnego zestawu, który utrzymuje kolejność reklam, poszedłem na kompromis z HashSet i List obok siebie. W takim przypadku za każdym razem, gdy dodajesz do zestawu, wykonaj następujące czynności:

if(hashSet.Add(item))
    orderList.Add(item);

Podczas wyjmowania elementów pamiętaj, aby usunąć je z obu. Tak więc, dopóki możesz być pewien, że nic innego nie dodało pozycji do listy, będziesz mieć unikalny zestaw uporządkowany przez wstawienie!

— rożek
źródło

10

Możesz również użyć Linq w:

using System.Linq;

var items = new List<string>() { "one", "one", "two", "one", "two", "zero" };

List<string> distinctItems = items.Distinct().ToList();

— Dave Hollingsworth
źródło

8

Użyj HashSet, nie musisz sprawdzać .Contains (), po prostu dodaj swoje pozycje do listy i jeśli się zduplikuje, nie doda go.

   HashSet<int> uniqueList = new HashSet<int>();
   uniqueList.Add(1); // List has values 1
   uniqueList.Add(2);  // List has values 1,2
   uniqueList.Add(1);  // List has values 1,2
   Console.WriteLine(uniqueList.Count); // it will return 2

— Priyang
źródło

2

Nie jest to część przestrzeni nazw systemu, ale wykorzystano kolekcje Iesi.Collections z http://www.codeproject.com/KB/recipes/sets.aspx z NHibernate. Obsługuje zestaw haszowany wraz z zestawem posortowanym, zestawem słowników i tak dalej. Odkąd został użyty z NHibernate, był szeroko stosowany i bardzo stabilny. To również nie wymaga .Net 3.5

— AndrewB
źródło

2

Oto inne rozwiązanie bez użycia HashSet.

var items = new List<string>() { "one", "one", "two", "one", "two", "zero" };
var uniqueItems = items.Where((item, index) => items.IndexOf(item) == index);

Został przejęty z tego wątku: javascript - Unikalne wartości w tablicy

Test:

using FluentAssertions;

uniqueItems.Count().Should().Be(3);
uniqueItems.Should().BeEquivalentTo("one", "two", "zero");

Test wydajności dla List, HashSeti SortedSet. 1 milion iteracji:

List: 564 ms
HashSet: 487 ms
SortedSet: 1932 ms

Testuj kod źródłowy (treść)

— Alexey Solonets
źródło