У меня есть 60 тыс. Элементов, которые нужно проверить по списку поиска из 20 тыс. Есть ли объект коллекции (например List, HashTable), который предоставляет исключительно быстрый Contains()метод? Или мне придется писать свою? Другими словами, Contains()метод по умолчанию - просто сканировать каждый элемент или использует лучший алгоритм поиска.
foreach (Record item in LargeCollection)
{
if (LookupCollection.Contains(item.Key))
{
// Do something
}
}
Примечание . Список подстановки уже отсортирован.
c#
.net
search
collections
Ондрей Яначек
источник
источник
Ответы:
В наиболее общем случае считается
System.Collections.Generic.HashSet, что структура данных "содержит" по умолчанию является рабочей лошадкой, потому что для ее оценки требуется постоянное времяContains.Фактический ответ на вопрос «Какая самая быстрая коллекция с возможностью поиска?» Зависит от конкретного размера данных, упорядоченности, стоимости хеширования и частоты поиска.
источник
Если вам не нужен заказ, попробуйте
HashSet<Record>(впервые в .Net 3.5)Если да, используйте
List<Record>и позвонитеBinarySearch.источник
ImmutableSortedSetот System.ImmutableCollectionsВы думали
List.BinarySearch(item)?Вы сказали, что ваша большая коллекция уже отсортирована, так что это прекрасная возможность? Хеширование определенно будет самым быстрым, но это вызывает свои проблемы и требует гораздо больше накладных расходов на хранение.
источник
Вы должны прочитать этот блог, что скорость протестировала несколько различных типов коллекций и методов для каждого, используя как однопоточные, так и многопоточные методы.
Согласно результатам, BinarySearch on a List и SortedList были лучшими исполнителями, постоянно сталкиваясь с трудностями при поиске чего-либо в качестве «ценности».
При использовании коллекции, допускающей использование «ключей», Dictionary, ConcurrentDictionary, Hashset и HashTables показали лучшие результаты в целом.
источник
Храните оба списка x и y в отсортированном порядке.
Если x = y, выполните свое действие, если x <y, продвиньте x, если y <x, продвиньте y, пока любой из списков не станет пустым.
Время прохождения этого пересечения пропорционально min (размер (x), размер (y))
Не запускайте цикл .Contains (), он пропорционален x * y, что намного хуже.
источник
Если есть возможность отсортировать элементы, есть гораздо более быстрый способ сделать это, чем поиск ключей в хеш-таблице или b-дереве. Хотя, если ваши предметы не сортируются, вы все равно не сможете поместить их в 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источник
Если вы используете .Net 3.5, вы можете сделать более чистый код, используя:
foreach (Record item in LookupCollection.Intersect(LargeCollection)) { //dostuff }У меня здесь нет .Net 3.5, поэтому это не проверено. Он полагается на метод расширения. Не то чтобы
LookupCollection.Intersect(LargeCollection)это, вероятно, не то же самое, чтоLargeCollection.Intersect(LookupCollection)... последнее, вероятно, намного медленнее.Предполагается, что LookupCollection является
HashSetисточник
Если вы не беспокоитесь о писке каждой последней бит производительности, предложение использовать HashSet или двоичный поиск является твердым. Ваши наборы данных недостаточно велики, чтобы это было проблемой в 99% случаев.
Но если это всего лишь один из тысяч раз, когда вы собираетесь это сделать, а производительность критична (и доказано, что это неприемлемо с использованием HashSet / двоичного поиска), вы, безусловно, могли бы написать свой собственный алгоритм, который проходил бы отсортированные списки, выполняя сравнения по мере вашего продвижения. Каждый список будет просматриваться не более одного раза, и в патологических случаях было бы неплохо (если бы вы пошли по этому маршруту, вы, вероятно, обнаружили бы, что сравнение, предполагая, что это строка или другое нецелое значение, будет реальными расходами и что оптимизация будет следующим шагом).
источник