.NET: Как эффективно проверить уникальность в List <string> из 50 000 элементов?

В некотором библиотечном коде у меня есть Список, который может содержать 50 000 элементов или больше.

Вызывающие библиотеки могут вызывать методы, которые приводят к добавлению строк в список. Как я могу эффективно проверить уникальность добавляемых строк?

В настоящее время, перед добавлением строки, я просматриваю весь список и сравниваю каждую строку с добавленной строкой. Это начинает показывать масштабные проблемы, превышающие 10 000 предметов.

Я сравню это, но интересуюсь проницательностью.

Если я заменил List < > на словарь < > , будет ContainsKey() заметно быстрее, так как список увеличится до 10 000 элементов и далее?
Если я отложил проверку уникальности до тех пор, пока не будут добавлены все элементы, будет ли она быстрее? В этот момент мне нужно будет проверить каждый элемент на каждый другой элемент, все еще выполняющий операцию n ^^ 2.

ИЗМЕНИТЬ

Некоторые базовые результаты. Я создал абстрактный класс, который предоставляет 2 метода: Fill and Scan. Заполнение только заполняет коллекцию n элементами (я использовал 50 000). Сканирование просматривает список m раз (я использовал 5000), чтобы увидеть, присутствует ли данное значение. Затем я построил реализацию этого класса для List, а другой для HashSet.

Используемые строки были равномерно длиной 11 символов и случайным образом сгенерированы методом абстрактного класса.

Очень простой микро-бенчмарк.

Hello from Cheeso.Tests.ListTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.4428266
Time to scan: 00:00:13.0291180

Hello from Cheeso.Tests.HashSetTester
filling 50000 items...
scanning 5000 items...
Time to fill: 00:00:00.3797751
Time to scan: 00:00:00.4364431

Итак, для строк этой длины HashSet примерно на 25 раз быстрее, чем List, при сканировании на уникальность. Кроме того, для такого размера коллекции HashSet имеет нулевое наказание за List при добавлении элементов в коллекцию.

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

Спасибо всем.

EDIT2

После добавления рандомизации и многопроцессорных испытаний, HashSet последовательно превосходит List в этом случае примерно на 20x.

Эти результаты не обязательно выполняются для строк переменной длины, более сложных объектов или разных размеров коллекции.

Ответ 1

Вы должны использовать класс HashSet<T>, который специально разработан для того, что вы делаете.

Ответ 2

Используйте HashSet<string> вместо List<string>, тогда он должен масштабироваться очень хорошо.

Ответ 3

Из моих тестов HashSet<string> не хватает времени по сравнению с List<string>:)

Ответ 4

Возможно, вне темы, но если вы хотите масштабировать очень большие уникальные наборы строк (миллионы +) независимым от языка образом, вы можете проверить Фильтры цветка.

Ответ 5

Я прочитал, что словарь < > реализуется как ассоциативный массив. На некоторых языках (не обязательно связанных с .NET) строковые индексы сохраняются как древовидная структура, которая вилки на каждом node на основе символа в node. См. http://en.wikipedia.org/wiki/Associative_arrays.

Аналогичная структура данных была разработана Ахо и Корасиком в 1973 году (я думаю). Если вы сохраняете 50 000 строк в такой структуре, тогда важно не сколько строк, которые вы храните. Это важнее длина струн. Если они примерно одинаковой длины, то вы, вероятно, никогда не увидите замедление поиска, потому что алгоритм поиска является линейным во время выполнения по отношению к длине строки, которую вы ищете. Даже для дерева с красно-черным деревом или AVL время выполнения поиска больше зависит от длины строки, которую вы ищете, а не от количества элементов в индексе. Однако, если вы решите реализовать свои индексные ключи с помощью хэш-функции, теперь вы берете на себя стоимость хэширования строки (будет O (m), m = длина строки), а также поиск строки в индексе, которая вероятно, будет порядка O (log (n)), n = количество элементов в индексе.

edit: Я не являюсь гуру .NET. Другие более опытные люди предлагают другую структуру. Я бы сказал им свое слово.

edit2: ваш анализ немного не подходит для сравнения уникальности. Если вы используете структуру хэширования или словарь, то это не будет операция O (n ^ 2) из-за рассуждений, которые я опубликовал выше. Если вы продолжаете использовать список, то вы правы, что это O (n ^ 2) * (максимальная длина строки в вашем наборе), потому что вы должны каждый раз проверять каждый элемент в списке.

Ответ 6

Функция Contains(T) не работает для вас?