Какой самый эффективный способ проверить существование с помощью набора целых чисел?

Question

У меня есть большой список целых чисел, которые отправляются на мой веб-сервис. Наши бизнес-правила гласят, что эти ценности должны быть уникальными. Какой самый эффективный способ выяснить, есть ли дубликаты? Мне не нужно знать значения, мне нужно только знать, равны ли 2 значения.

Сначала я думал об использовании общего списка целых чисел и метода list.Exists (), но это O (n);

Тогда я думал об использовании словаря и метода ContainsKey. Но мне нужны только ключи, мне не нужны значения. И я думаю, что это также линейный поиск.

Есть ли лучший тип данных, который можно использовать для поиска уникальности в списке? Или я застрял с линейным поиском?

Answer 1

Используйте HashSet<T>:

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

HashSet<T> даже выставляет конструктор, который принимает IEnumerable<T>. Передав ваш List<T> в конструктор HashSet<T>'s, вы получите ссылку на новый HashSet<T>, который будет содержать последовательность элементов, отличную от вашего исходного List<T>.

Answer 2

Звучит как работа для Hashset ...

Answer 3

Что делать:

list.Distinct().Count() != list.Count() 

Интересно насчет производительности этого. Я думаю, что это было бы так же хорошо, как O (n), но с меньшим количеством кода и все еще легко читаемым.

Answer 4

Если набор чисел редок, то, как другие предлагают использовать HashSet.

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

Answer 5

Если вы используете framework 3.5, вы можете использовать коллекцию HashSet.

В противном случае лучшим вариантом будет Dictionary. Стоимость каждого предмета будет потрачена впустую, но это даст вам лучшую производительность.

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