Получите случайный элемент из С# HashSet быстро

Мне нужно сохранить набор элементов. Мне нужна функциональность для

удалить (одиночные) элементы и
добавить (множество) элементов и
каждый объект должен быть установлен только один раз и
получить случайный элемент из набора

Я выбрал HashSet (С#), так как он поддерживает быстрые методы для удаления элементов (hashSet.remove(element)), добавление наборов (hashSet.UnionWith(anotherHashSet)) и характер HashSet гарантирует, что дубликатов нет, поэтому соблюдаются требования 1-3.

Единственный способ получить случайный элемент -

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

Но это очень медленно, так как я назову его один раз для каждого пикселя моей карты (создавая случайную заливку заливки из нескольких начальных точек, на данный момент отображает 500x500, но я хотел бы увеличить), а hashset многие предметы. (Быстрый тест показывает, что он дует до 5752 записей, прежде чем снова сжиматься.)

Профилирование (выборка процессора) говорит мне, что мои вызовы ElementAt занимают более 50%.

Я понимаю, что операции 500x500 по большому hashset - непростая задача, но другие операции (Remove and UnionWith) вызываются так же часто, как ElementAt, поэтому основной проблемой является операция, а не количество вызовов.

Я смутно понимаю, почему получение определенного элемента из HashSet очень дорого (по сравнению с его получением из списка или другой упорядоченной структуры данных, но я просто хочу случайный выбор. Неужели это действительно так сложно и нет ли способа обойти это? Есть ли лучшая структура данных для моей цели?

Изменение всего на Списки не помогает, потому что теперь другие методы становятся узкими местами, и это занимает еще больше времени.

Отбрасывание HashSet в массив и выбор моего случайного элемента из него, как ожидается, не поможет, потому что, когда выбор случайного элемента из массива выполняется быстро, наложение хэш-набора на массив в первую очередь занимает больше времени, чем запуск hashSet.ElementAt само по себе.

Если вы хотите лучше понять, что я пытаюсь сделать: Ссылка на мой вопрос и ответ.

Ответ 1

Основная проблема - это индексирование.

В массиве или списке данные индексируются его координатом - обычно просто простым индексом int. В HashSet вы сами выбираете индекс - ключ. Однако побочный эффект заключается в том, что нет "coördinate" - вопрос "элемент в индексе 3" на самом деле не имеет смысла. Способ, которым он фактически реализован, состоит в том, что перечисляется весь HashSet, элемент после элемента и возвращается n-й элемент. Это означает, что для получения 1000-го элемента вам необходимо перечислить все 999 предметов до этого. Это больно.

Лучший способ решить эту задачу - выбрать случайный, основанный на фактическом ключе HashSet. Конечно, это работает только в том случае, если разумно выбирать случайные ключи именно так.

Если вы не можете выбрать ключ наугад удовлетворительным образом, вы, вероятно, захотите сохранить два отдельных списка - всякий раз, когда вы добавляете новый элемент в HashSet, добавьте его ключ в List<TKey>; вы можете легко выбрать случайный ключ из List и следовать ему. В зависимости от ваших требований дубликаты могут быть не очень сложными.

И, конечно, вы можете сэкономить на перечислениях ElementAt, если вы только выполните перечисление один раз - например, перед поиском HashSet вы можете преобразовать его в List. Это имеет смысл только в том случае, если вы выбираете сразу несколько случайных индексов сразу (например, если вы выбираете 5 индексов в случайном порядке одновременно, вы сэкономите примерно 1/5 раз) - если вы всегда выбираете один, затем изменив HashSet и выбрав другой, это не поможет.

В зависимости от вашего конкретного варианта использования, возможно, стоит взглянуть на SortedSet. Он работает аналогично HashSet, но он сохраняет порядок в ключах. Полезная часть состоит в том, что вы можете использовать метод GetViewBetween для получения целого ряда ключей - вы можете использовать это достаточно эффективно, если ваши ключи разрежены, но хорошо сбалансированы между произвольными диапазонами. Вы только сначала выбираете диапазон наугад, а затем получаете предметы в диапазоне GetViewBetween и выбираете случайный из них. По сути, это позволит вам разбить результаты поиска и сэкономить немало времени.

Ответ 2

Я думаю, что OrderedDictionary может соответствовать вашим целям:

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

У этого есть быстрая добавка и удаление, а O (1) индексирование. Он работает только с клавишами object и значениями - нет никакой общей версии.