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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если вы можете отсортировать свои объекты, тогда есть гораздо более быстрый способ сделать это, а затем выполнить ключевые поиски в hash-таблицу или 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 

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

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

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

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

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

Это предполагает, что LookupCollection – это HashSet

  • Сортировка коллекции объектов
  • Что такое коллекция java?
  • Получение списка активных активных streamов в .NET?
  • Быстрее добавлять в коллекцию, сортировать ее или добавлять в сортированную коллекцию?
  • Как найти объект в ArrayList по свойству
  • Сортировка коллекции Java
  • какова хорошая постоянная структура коллекций для использования в java?
  • Почему Java Map не расширяет коллекцию?
  • Как сортировать в алфавитном порядке, игнорируя регистр?
  • Разница между HashMap и ArrayList в Java?
  • Печать HashMap в Java
  • Interesting Posts

    Как увеличить размер моего диска C на XP

    широковещательный приемник не получит событие камеры

    Резюме прерванной копии файла Mac OS X

    Присвоение строк массивам символов

    Расположение профилей XCode Provisioning

    Обфускация в Android Studio

    Измельчение базы данных в node.js?

    Как создать отдельные 7z-файлы из каждого выбранного каталога с помощью командной строки 7zip?

    Как я могу перекрыть блокировку кепки, когда ключ Caps Lock переназначен?

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

    ASP.NET MVC3 и Windows Auth на IIS продолжают перенаправлять / Account / Login

    Tmux вызывает проблемы с Bash up-arrow

    Как разрешить ввод только числа (цифры и десятичная точка) на входе?

    расширять имена файлов, которые имеют переменные среды на своем пути

    почему переменная экземпляра суперclassа не переопределяется в методе подclassа

    Давайте будем гением компьютера.