Наиболее эффективный способ тестирования большого количества строк против большого списка <string>

Я рассмотрел ряд других подобных вопросов, но приведенные методы кажутся слишком медленными для того, что я пытаюсь выполнить, или тестируют частичные совпадения, которые мне не нужны и должны быть медленнее.

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

Второй список (строк для удаления) содержит 160 000 строк. Я загрузил это в List<String>, а затем читал каждую строку более крупного файла и тестировал его с помощью List<String>.Any(line.contains).

Даже с небольшой частью первого списка (строки 40k) это занимает много времени, возможно, более 20 минут на моем компьютере с быстрым развитием.

Здесь Мой вопрос

Есть ли больше/Что является наиболее эффективным способом сравнения большого списка строк отдельно от другого более крупного списка строк, если нет частичных совпадений.

Ответ 1

Вместо использования List<string> используйте HashSet<string>. Он имеет O (1) поиск вместо O (n), как и список. Если вы сделаете это изменение, вы должны увидеть ускорение порядка.

Это может также дать вам немного лучшую производительность, чтобы использовать HashSet.Contains(), а не метод расширения LINQ .Any().

Ответ 2

Во-первых, я думаю, что ваша логика просто неверна. Передача делегата в метод Содержит к любому будет выполнять частичные совпадения строк, и вы явно заявили, что хотите только точные соответствия.

Оставляя это в стороне, ваша проблема с производительностью связана с характером структуры данных списка; он не был разработан для эффективного поиска через "Любой".

Проблема в том, что "Any" просто выполняет линейный поиск, начиная с начала списка и пробивая его, пока не найдет совпадение. Если в списке есть 100K записей, то каждая "промашка" будет выполнять сопоставления строк в 100 тыс., И каждый "удар" будет выполнять в среднем сравнение строк в 50 тыс..

Это ужасно.

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

Другая возможная оптимизация - сортировать один из списков, который является операцией O (n lg n), а затем двоичный поиск отсортированного списка, который является операцией O (lg n).

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

A, B, C, D, G, I
B, D, E, H, I

Затем вы начинаете с индексов, указывающих на A и B. "A" меньше, поэтому вы указываете первый индекс на "B". Теперь они одинаковы; у вас есть матч. Продвиньте их обоих. Первый индекс - "C", а второй - "D". "C" меньше ", поэтому продвиньте его...

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

Ответ 3

Используйте операторы Union и Except, чтобы получить различия и сходства между вашими двумя списками.

Союз: http://msdn.microsoft.com/en-us/library/bb341731.aspx

За исключением: http://msdn.microsoft.com/en-us/library/system.linq.enumerable.except.aspx

Каждая функция возвращает список, содержащий результирующие данные.

Ответ 4

Вы можете вставить каждый элемент первого списка в HashSet<string>, а затем проверить каждый элемент второго для присутствия в наборе. Это только один раз ударяет каждый элемент, а вставка и тестирование должны быть O (1) (если только ваш набор данных не является патологическим по какой-либо причине.)

Ответ 5

Я не понимаю, почему никто не упомянул Enumerable.Intersect. Это довольно эффективная и очень простая функция для использования здесь.

Ответ 6

Строки известны спереди, поэтому отсортированный вектор будет быстрее, чем хэш-карта. Хешируйте строки из файла меньшего размера с помощью хэша, удобного для строк, такого как FNV и помещаем их в

vector<pair<int, string> >

Определите функции, чтобы сделать его сортируемым и сопоставимым по хешу, тогда sort вектор.

bool operator < (pair<int, string> const&, pair<int, string> const&) { ... }
bool operator < (pair<int, string> const&, int) { ... }
bool operator < (int, pair<int, string> const&) { ... }

Теперь прочитайте каждую строку из более крупного файла, запишите ее и найдите вектор с помощью equal_range. Сравните все строки только там, где совпадают хэши. (Примечание: для поиска по хешу может потребоваться дополнительная магия вместо использования манекена pair<int, string>.)

Если более длинная задержка до начала вывода приемлема и доступно достаточное пространство, может быть быстрее загрузить оба файла в отсортированные векторы, найти соответствующие хэши с set_intersection и сравните их полные строки. Я оставлю детали как упражнение для читателя (:-). Помните, что с обеих сторон могут быть хеш-столкновения.