.NET: Как эффективно проверить на уникальность в Списке <строка> 50 000 объектов?

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

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

Судя по моим тестам, HashSet не требует времени по сравнению с List :)

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

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

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

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

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