Какой самый быстрый / самый безопасный метод для перебора HashSet?

Question

Я все еще довольно новичок в C #, но заметил заметки в сообщениях на форуме о том, что в некоторых случаях HashSet вместо List.

В моем нынешнем случае дело не в том, что я храню огромное количество данных в одном List, а скорее в том, что мне приходится часто проверять его членов.

Загвоздка в том, что мне действительно нужно перебирать и ее, но порядок их хранения или получения на самом деле не имеет значения.

Я читал, что для каждого цикла на самом деле медленнее, чем для следующего, так как еще я мог бы сделать это самым быстрым способом?

Количество проверок .Contains(), которые я делаю, определенно ухудшает мою производительность со списками, поэтому по крайней мере сравнение с HashSet было бы удобно.

Редактировать: в настоящее время я использую списки, перебирая их в разных местах, и в каждом месте выполняется разный код. Чаще всего текущие списки содержат координаты точек, которые я затем использую для ссылки на двумерный массив, для чего я затем выполняю ту или иную операцию на основе критериев списка.

Если нет прямого ответа на мой вопрос, это нормально, но я предположил, что могут быть другие методы итерации по HashSet, чем просто foreach цикл. В настоящее время я не знаю, какие еще методы могут быть, какие преимущества они предоставляют и т. Д. Предполагая, что существуют другие методы, я также предположил, что существует типичный предпочтительный метод выбора, который игнорируется только тогда, когда это не соответствует потребностям (мои потребности довольно простые).

Что касается преждевременной оптимизации, я уже знаю, что списки используются, поскольку я являюсь узким местом. Как помочь этому вопросу - вот где я застреваю. Даже не застрял точно, но я не хотел заново изобретать колесо, проводя многократные тесты, чтобы убедиться, что я уже делаю это наилучшим образом (это большой проект, на который вложено более 3 месяцев, списки есть везде , но есть определенно те, которые я не хочу дублировать, иметь много данных, их не нужно хранить в каком-либо определенном порядке и т. д.).

Answer 1

Цикл foreach имеет небольшое количество дополнительных затрат на индексированные коллекции (например, массив).Это происходит главным образом потому, что foreach выполняет немного большую проверку границ, чем цикл for.

HashSet не имеет индексатора, поэтому вы должны использовать перечислитель.

В этом случае foreach эффективен какон вызывает только MoveNext () при перемещении по коллекции.

Также Parallel.ForEach может значительно улучшить вашу производительность, в зависимости от работы, которую вы выполняете в цикле, и размера вашего HashSet.

Как уже упоминалось, профилирование - ваш лучший выбор.

Answer 2

Вы не должны сначала перебирать хэш-набор, чтобы определить, есть ли в нем элемент.Вы должны использовать метод HashSet (не LINQ).HashSet разработан таким образом, что ему не нужно просматривать каждый элемент, чтобы увидеть, находится ли какое-либо заданное значение внутри набора.Вот что делает его таким мощным средством поиска по списку.

Answer 3

Не строго отвечая на вопрос в шапке, но больше касающийся вашей конкретной проблемы:

Я бы создал ваш собственный Collection объект, который использует как HashSet, так и List для внутреннего использования. Повторение выполняется быстро, поскольку вы можете использовать список, проверка на Contains выполняется так же быстро, как вы можете использовать HashSet. Просто сделайте его IEnumerable, и вы также сможете использовать эту коллекцию в foreach.

Недостатком является увеличение памяти, но ссылок на объект в два раза больше, а не в два раза больше. В худшем случае это всего лишь вдвое больше памяти, но вы, кажется, гораздо больше озабочены производительностью.

Таким образом, добавление, проверка и повторение выполняются быстро, только удаление по-прежнему равно O (N) из-за List.

РЕДАКТИРОВАТЬ: Если удаление также должно быть O (1), используйте двусвязный список вместо обычного списка, и вместо этого сделайте hashSet Dictionary<KeyType, Cell>. Вы можете проверить словарь на Contains, но также быстро найти ячейку с данными, поэтому удаление из структуры данных происходит быстро.

Answer 4

У меня была та же проблема, когда HashSet очень хорошо подходит для добавления уникальных элементов, но очень медленно при получении элементов в цикле for. Я решил это, преобразовав HashSet в массив, а затем запустив для него метод.