Какая коллекция .NET обеспечивает самый быстрый поиск

Question

У меня есть 60 тыс. Предметов, которые необходимо проверить по списку поиска 20 тыс. Есть ли объект коллекции (например, List, HashTable), который обеспечивает исключительно быстрый метод Contains()? Или я должен буду написать свой собственный? Другими словами, это метод Contains() по умолчанию, просто сканирующий каждый элемент, или он использует лучший алгоритм поиска.

foreach (Record item in LargeCollection)
{
    if (LookupCollection.Contains(item.Key))
    {
       // Do something
    }
}

Примечание . Список поиска уже отсортирован.

Answer 1

В самом общем случае рассмотрим System.Collections.Generic.HashSet в качестве структуры данных по умолчанию "Contains" рабочей лошадки, поскольку для оценки Contains требуется постоянное время.

Фактический ответ на вопрос «Что такое коллекция с самым быстрым поиском» зависит от вашего конкретного размера данных, упорядоченности, стоимости хэширования и частоты поиска.

Answer 2

Если вам не нужно заказывать, попробуйте HashSet<Record> (новичок в .Net 3.5)

Если вы это сделаете, используйте List<Record> и позвоните BinarySearch.

Answer 3

Рассматривали ли вы List.BinarySearch(item)?

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

Answer 4

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

Согласно результатам, BinarySearch в List и SortedList были лучшими игроками, постоянно работавшими на шее, когда смотрели на что-то как на «ценность».

При использовании коллекции, которая допускает «ключи», словарь, ConcurrentDictionary, Hashset и HashTables показали наилучшие результаты в целом.

Answer 5

Храните оба списка x и y в отсортированном порядке.

Если x = y, выполните свое действие, если x

Время выполнения этого пересечения пропорционально мин (размер (х), размер (у))

Не запускайте цикл .Contains (), это пропорционально x * y, что намного хуже.

Answer 6

Если вы используете .Net 3.5, вы можете сделать более чистый код, используя:

foreach (Record item in LookupCollection.Intersect(LargeCollection))
{
  //dostuff
}

У меня нет .Net 3.5 здесь, и поэтому это не проверено.Он опирается на метод расширения.Не то чтобы LookupCollection.Intersect(LargeCollection), вероятно, не то же самое, что LargeCollection.Intersect(LookupCollection) ... последнее, вероятно, намного медленнее.

Это предполагает, что LookupCollection равен HashSet

Answer 7

Если есть возможность отсортировать ваши элементы, тогда есть гораздо более быстрый способ сделать это, чем поиск ключей в хеш-таблице или b-дереве. Хотя, если ваши вещи не сортируются, вы все равно не сможете поместить их в би-дерево.

В любом случае, если сортировка сортируется по обоим спискам, нужно просто просмотреть список поиска по порядку.

Walk lookup list
   While items in check list <= lookup list item
     if check list item = lookup list item do something
   Move to next lookup list item

Answer 8

Если вы не беспокоитесь о том, чтобы пискать до последней капли производительности, предложение использовать HashSet или бинарный поиск вполне обоснованно. Ваши наборы данных просто недостаточно велики, так что это будет проблемой в 99% случаев.

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