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

Question

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

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

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

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

Вот мой вопрос

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

Answer 1

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

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

Answer 2

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

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

Проблема в том, что «Любой» просто выполняет линейный поиск, начиная с начала списка и просматривая его, пока не найдет совпадение. Если в списке есть записи по 100 тыс., То каждое «промах» будет сравнивать строки по 100 тыс., А каждое «попадание» будет делать в среднем сравнения строк по 50 тыс.

Это ужасно.

Что вам нужно сделать, это преобразовать Список в 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" меньше ", так что продвигайте его ...

---

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

Answer 3

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

Answer 4

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

Объединение: http://msdn.microsoft.com/en-us/library/bb341731.aspx

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

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

Answer 5

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

Answer 6

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

vector<pair<int, string> >

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

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 и сравните их полные строки.Я оставлю детали в качестве упражнения для читателя (:-).Помните, что с обеих сторон могут быть коллизии хешей.