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

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

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

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

Ответ 1

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

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

Ответ 2

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

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

Ответ 3

Вы считали List.BinarySearch(item)?

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

Ответ 4

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

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

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

Ответ 5

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

Если x = y, выполните свое действие, если x < y, продвижение x, если y < x, продвигайте y до тех пор, пока ни один из них не будет пустым.

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

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

Ответ 6

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

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

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

Ответ 7

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

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

Ответ 8

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

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

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

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