Понятно, что эффективность поиска универсального HashSet<T>
класса выше, чем универсального List<T>
класса. Просто сравните ключ на основе хеша с линейным подходом в List<T>
классе.
Однако вычисление ключа хеша само по себе может занять несколько циклов ЦП, поэтому для небольшого количества элементов линейный поиск может стать реальной альтернативой HashSet<T>
.
Мой вопрос: где безубыточность?
Чтобы упростить сценарий (и быть справедливым), давайте предположим, что List<T>
класс использует метод элемента Equals()
для идентификации элемента.
.net
performance
collections
list
hash
Михаил Даматов
источник
источник
Ответы:
Многие люди говорят, что, как только вы доберетесь до размера, где скорость на самом деле является проблемой,
HashSet<T>
которая всегда побеждаетList<T>
, но это зависит от того, что вы делаете.Предположим, у вас есть
List<T>
только 5 предметов. В течение большого количества циклов, если один элемент добавляется или удаляется в каждом цикле, вам лучше использовать aList<T>
.Я проверил это на своей машине, и, чтобы получить преимущество, он должен быть очень маленьким
List<T>
. Для списка коротких строк преимущество ушло после размера 5, для объектов после размера 20.Вот эти данные отображаются в виде графика:
Вот код:
источник
List<T>
для игрового движка, и, поскольку у меня обычно будет большой объем объектов, этот вид коллекции будет идеальным.Вы смотрите на это неправильно. Да, линейный поиск по списку превзойдет HashSet для небольшого количества элементов. Но разница в производительности обычно не имеет значения для небольших коллекций. Как правило, о больших коллекциях вы должны беспокоиться, и именно здесь вы думаете о Big-O . Однако, если вы измерили реальное узкое место в производительности HashSet, вы можете попытаться создать гибридный List / HashSet, но вы сделаете это, проведя множество эмпирических тестов производительности - не задавая вопросов по SO.
источник
when small collection becomes large enough to worry about HashSet vs List?
десятков, десятков тысяч, миллиардов элементов?HashSet<T>
. В случаях с небольшим числом, гдеList<T>
может быть быстрее, разница незначительна «.По сути, бессмысленно сравнивать две структуры по производительности, которые ведут себя по-разному. Используйте структуру, которая передает намерение. Даже если вы скажете, что у вас
List<T>
не будет дубликатов, и порядок итераций не имеет значения, делая его сравнимым с aHashSet<T>
, его все равно плохой выбор,List<T>
поскольку он относительно менее отказоустойчив.Тем не менее, я буду проверять некоторые другие аспекты производительности,
Несмотря на то, что сложение равно O (1) в обоих случаях, оно будет относительно медленным в HashSet, поскольку требует затрат на предварительную обработку хеш-кода перед его сохранением.
Превосходная масштабируемость HashSet имеет стоимость памяти. Каждая запись хранится как новый объект вместе со своим хеш-кодом. Эта статья может дать вам представление.
источник
Использовать ли HashSet <> или List <> зависит от того, как вам нужен доступ к вашей коллекции . Если вам нужно гарантировать порядок товаров, используйте Список. Если вы этого не сделаете, используйте HashSet. Позвольте Microsoft беспокоиться о реализации своих алгоритмов хеширования и объектов.
HashSet будет обращаться к элементам без нумерации коллекции (сложность O (1) или около нее), и поскольку список гарантирует порядок, в отличие от HashSet, некоторые элементы должны быть перечислены (сложность O (n)).
источник
List
предпочтительным является a , поскольку вы можете запомнить индекс - это ситуация, в которой вы описываю.Просто подумал, что я бы включил некоторые тесты для различных сценариев, чтобы проиллюстрировать предыдущие ответы:
И для каждого сценария ищем значения, которые появляются:
Перед каждым сценарием я генерировал случайные по размеру списки случайных строк, а затем передавал каждый список в хэш-набор. Каждый сценарий выполнялся 10000 раз, по сути:
(тестовый псевдокод)
Пример вывода
Проверено на Windows 7, 12 ГБ оперативной памяти, 64-разрядных, Xeon 2,8 ГГц
источник
List
все еще требуется всего 0,17 миллисекунды для выполнения одного поиска, и вряд ли потребуется заменаHashSet
до тех пор, пока частота поиска не достигнет абсурдных уровней. К тому времени использование List обычно является наименьшей из проблем.Безубыток будет зависеть от стоимости вычисления хэша. Хеш-вычисления могут быть тривиальными или нет ... :-) Всегда есть класс System.Collections.Specialized.HybridDictionary, чтобы не беспокоиться о точке безубыточности.
источник
Ответ, как всегда, « Это зависит ». Я полагаю из тегов, которые вы говорите о C #.
Ваш лучший выбор - определить
и написать несколько тестов.
Это также зависит от того, как вы сортируете список (если он вообще сортируется), какого рода сравнения необходимо выполнить, сколько времени занимает операция «Сравнить» для определенного объекта в списке или даже как вы собираетесь использовать коллекция.
Как правило, лучший выбор не столько зависит от размера данных, с которыми вы работаете, сколько от того, как вы намереваетесь получить к нему доступ. У вас есть каждый фрагмент данных, связанный с определенной строкой или другими данными? Лучше всего подойдет коллекция на основе хешей. Важен ли порядок хранимых данных или вам потребуется доступ ко всем данным одновременно? Обычный список может быть лучше.
Дополнительно:
Конечно, мои комментарии выше предполагают, что «производительность» означает доступ к данным. Что еще нужно рассмотреть: что вы ищете, когда говорите «производительность»? Производительность индивидуальной ценности смотрит вверх? Это управление большими (10000, 100000 или более) наборами значений? Производительность заполнения структуры данных данными? Удаление данных? Доступ к отдельным битам данных? Замена значений? Перебирая значения? Использование памяти? Скорость копирования данных? Например, если вы обращаетесь к данным по строковому значению, но основным требованием к производительности является минимальное использование памяти, у вас могут возникнуть конфликтующие проблемы проектирования.
источник
Вы можете использовать HybridDictionary, который автоматически обнаруживает точку разрыва и принимает нулевые значения, делая его практически таким же, как HashSet.
источник
Это зависит. Если точный ответ действительно имеет значение, сделайте профилирование и узнайте. Если вы уверены, что в наборе никогда не будет больше определенного количества элементов, используйте Список. Если число не ограничено, используйте HashSet.
источник
Зависит от того, что вы хэшируете. Если ваши ключи целые числа, вам, вероятно, не нужно много элементов, прежде чем HashSet станет быстрее. Если вы вводите его в строку, это будет медленнее и зависит от входной строки.
Конечно, вы могли бы довольно легко поднять отметку?
источник
Одним из факторов, который вы не учитываете, является надежность функции GetHashcode (). С идеальной функцией хеширования HashSet, несомненно, будет иметь лучшую производительность поиска. Но с уменьшением хеш-функции время поиска HashSet будет уменьшаться.
источник
Зависит от множества факторов ... Реализация списка, архитектура процессора, JVM, семантика цикла, сложность метода equals и т. Д. К тому времени, когда список становится достаточно большим, чтобы эффективно тестировать (более 1000 элементов), двоичный двоичный код поиск превосходит линейный поиск, и оттуда разница только увеличивается.
Надеюсь это поможет!
источник