Pobierz losowy element z C# HashSet szybko

Question

Potrzebuję przechowywać zestaw elementów. Co potrzebne jest funkcjonalność

1. Usuń (single) elementów i
2. add (zestawy) elementy i
3. każdy obiekt powinien być dostępny tylko w zestawie raz
4. dostać losowy element z ustawić

wybrałem HashSet (C#), ponieważ sport szybkich metod usuwania elementów (hashSet.remove (element)), dodawanie zestawów (hashSet.UnionWith (anotherHashSet)), a charakter programu HashSet gwarantuje, że nie ma duplikatów, więc zadbano o wymagania od 1 do 3.

Jedynym sposobem znalazłem się dostać element losowy jest

Object object = hashSet.ElementAt(rnd.Next(hashSet.Count)); 

Ale to jest bardzo powolny, ponieważ ja to nazywam raz dla każdego piksela mojej mapie (tworząc losowo Wypełnienie z wielu punktów wyjściowych; mapize 500x500 w tej chwili, ale chciałbym go powiększyć), a hashset zawiera raczej wiele elementów. (Szybki test pokazuje, że wysuwa się do 5752 wpisów przed ponownym zmniejszeniem.)

Profilowanie (próbkowanie procesora) mówi mi, że moje połączenia z ElementAt przejmują 50%.

Realizuję operacje 500x500 na dużym haszowaniu nie jest łatwym zadaniem, ale inne operacje (Remove i UnionWith) są wywoływane tak często, jak ElementAt, więc głównym problemem wydaje się być operacja, a nie liczba połączeń.

Niejasno rozumiem, dlaczego uzyskanie określonego elementu z HashSet jest bardzo kosztowne (w porównaniu do uzyskania go z listy lub innej uporządkowanej struktury danych, ale po prostu chcę losowy wybór Czy to naprawdę jest takie trudne i istnieje żaden sposób wokół niego? Czy istnieje lepsza struktura danych dla mojego celu?

Zmiana wszystko do list nie pomaga, bo teraz inne metody stają się wąskie gardła, a to trwa nawet dłużej.

Casting HashSet do array i wybierz mój losowy element z tego, co oczekiwane, nie pomaga, ponieważ podczas wybierania losowego elementu z tablicy jest szybki, casting hashset do tablicy w pierwszej kolejności zajmuje więcej czasu niż uruchomienie samego hashSet.ElementAt.

Jeśli chcesz lepiej zrozumieć, co próbuję zrobić: A link to my question and the answer.

Answer 1

Podstawowym problemem jest indeksowanie.

W tablicy lub na liście dane są indeksowane według współrzędnych - zwykle po prostu indeksu int. W HashSet sam wybierasz indeks - klucz. Efektem ubocznym jest jednak to, że nie ma "kooperacji" - pytanie "element na indeksie 3" nie ma sensu. Sposób, w jaki jest on faktycznie zaimplementowany, polega na wyliczeniu całego elementu HashSet, pozycji za pozycją i zwróceniu n-tego elementu. Oznacza to, że aby zdobyć 1000. przedmiot, musisz również wyliczyć wszystkie 999 przedmiotów. To boli.

Najlepszym sposobem rozwiązania tego problemu jest wybranie losowego na podstawie rzeczywistego klucza z HashSet.Oczywiście działa to tylko wtedy, gdy rozsądnie jest wybierać losowe klucze.

Jeśli nie możesz wybrać klucza losowo w zadowalający sposób, prawdopodobnie będziesz chciał zachować dwie osobne listy - po dodaniu nowego elementu do HashSet dodaj jego klucz do List<TKey>; następnie można łatwo wybrać losowy klucz z List i postępować zgodnie z nim. W zależności od wymagań duplikaty mogą nie stanowić większego problemu.

I oczywiście, można zaoszczędzić na ElementAt wyliczeń, jeśli tylko zrobić wyliczenie raz - na przykład przed przeszukaniem HashSet, można przekonwertować go do List. Ma to sens tylko wtedy, gdy wybierasz kilka losowych indeksów jednocześnie (np. Jeśli wybierzesz 5 indeksów naraz, zaoszczędzisz średnio o 1/5 tego czasu) - jeśli jesteś zawsze wybierając jeden, a następnie modyfikując HashSet i wybierając inny, to nie pomoże.

W zależności od konkretnego przypadku użycia, warto również rzucić okiem na SortedSet. Działa w sposób podobny do HashSet, ale zachowuje porządek w kluczach. Pomocną częścią jest to, że możesz użyć metody GetViewBetween, aby uzyskać całą gamę kluczy - możesz to wykorzystać całkiem skutecznie, jeśli twoje klucze są rzadkie, ale dobrze zrównoważone między dowolnymi zakresami. Najpierw wybierzesz losowo zakres, a następnie uzyskasz pozycje w zakresie od GetViewBetween i wybierzesz losowy z nich również. W efekcie pozwoli to na podzielenie wyników wyszukiwania na partycje i zaoszczędzi sporo czasu.

Answer 2

myślę że OrderedDictionary może spełnić swoje cele:

var dict = new OrderedDictionary(); 

dict.Add("My String Key", "My String"); 
dict.Add(12345, 54321); 

Console.WriteLine(dict[0]); // Prints "My String" 
Console.WriteLine(dict[1]); // Prints 54321 

Console.WriteLine(dict["My String Key"]); // Prints "My String" 
Console.WriteLine(dict[(object)12345]); // Prints 54321 (note the need to cast!) 

ten szybko dodawać i usuwać, oraz O (1) indeksowanie. Działa tylko z kluczami i wartościami object - nie ma wersji generycznej.