.NET: Как эффективно проверить уникальность в Списке <string>из 50 000 наименований? - PullRequest
Новая
       12

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

32 голосов
/ 07 декабря 2009

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

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

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

Я оценим это, но заинтересован в понимании.

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

EDIT

Некоторые основные результаты тестов. Я создал абстрактный класс, который предоставляет 2 метода: Fill и Scan. Заполнить просто заполняет коллекцию с n предметов (я использовал 50000). Scan сканирует список 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 имеет нулевое наказание по сравнению со списком при добавлении элементов в коллекцию.

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

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

EDIT2

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

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

Ответы [ 6 ]

60 голосов
/ 07 декабря 2009

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

19 голосов
/ 07 декабря 2009

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

5 голосов
/ 07 декабря 2009

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

3 голосов
/ 07 декабря 2009

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

0 голосов
/ 07 декабря 2009

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

0 голосов
/ 07 декабря 2009

Я прочитал, что словарь <> реализован как ассоциативный массив. В некоторых языках (не обязательно связанных с .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) из-за рассуждений, которые я опубликовал выше. Если вы продолжаете использовать список, то вы правы, что это O (n ^ 2) * (максимальная длина строки в вашем наборе), потому что вы должны проверять каждый элемент в списке каждый раз.

...