Высокая производительность «содержит» поиск в списке строк в C #

Question

У меня есть список ок.500 000 строк, каждая ок.100 символов в длину.По заданному поисковому запросу я хочу идентифицировать все строки в списке, которые содержат поисковый запрос.В настоящее время я делаю это с простым старым набором данных, используя метод Select («MATCH% term%»).Это занимает около 600 мс на моем ноутбуке.Я хотел бы сделать это быстрее, может быть, 100-200 мс.

Какой рекомендуемый подход?

Производительность имеет решающее значение, поэтому я могу при необходимости поменять объем памяти для повышения производительности (в пределах разумного основания).).Список строк не изменится после инициализации, поэтому расчет хэшей также будет возможен.

У кого-нибудь есть рекомендации и какие структуры данных C # лучше всего подходят для этой задачи?

Answer 1

Я слышал хорошие вещи о Lucene.NET , когда дело доходит до выполнения быстрого полнотекстового поиска. Они сделали работу, чтобы выяснить самые быстрые структуры данных и тому подобное для использования. Я бы посоветовал сделать это.

В противном случае, вы можете просто попробовать что-то вроде этого:

var matches = list.AsParallel().Where(s => s.Contains(searchTerm)).ToList();

Но это, вероятно, не приведет вас к 100 мс.

Answer 2

Вы пробовали следующее?

list.FindAll(x => x.Contains("YourTerm")).ToList();

По некоторым причинам List.AsParallel (). Where (...) медленнее, чем list.FindAll (...) на моем ПК.

list.AsParallel().Where(x => x.Contains("YourTerm")).ToList();

Надеюсь, это поможет вам.

Answer 3

Три или дерево суффиксов поможет сделать это быстрее - это, по сути, то, что использует полнотекстовый поиск (обычно).

Существуют реализации на C #, которые вы можете использовать, такжеэтот поток SO: Ищете реализацию суффиксного дерева в C #?

Также, как уже упоминалось в @leppie, параллельное выполнение, вероятно, уже обеспечит вам требуемый прирост производительности x3.Но опять же, вам придется тщательно измерять, без этого никто не догадывается.

Answer 4

public static bool ContainsFast<T>(this IList<T> list, T item)
{
    return list.IndexOf(item) >= 0;
}

Исходя из проведенных мной тестов, эта вариация Contains была примерно на 33% быстрее с моей стороны.

Answer 5

Вы пытались загрузить свои строки в List<string> и затем использовать метод Linq extensions Contains?

var myList = new List<string>();
//Code to load your list goes here...

var searchTerm = "find this";
var match = myList.Contains(searchTerm);

Answer 6

В соответствии с этими критериями самый быстрый способ проверить, встречается ли строка в строке:

for (int x = 0; x < ss.Length; x++)
    for (int y = 0; y < sf.Length; y++
        c[y] += ((ss[x].Length - ss[x].Replace(sf[y], String.Empty).Length) / sf[y].Length > 0 ? 1 : 0);

Таким образом, вы могли бы:

1. Перебрать список с помощью конструкции Parallel.For
2. Реализуйте код выше, чтобы проверить, содержит ли строка то, что вы ищете. «SS» - строка [] строк для поиска; «SF» - это строка [] строк для поиска; c [y] - общее количество каждого найденного.

Очевидно, вам придется адаптировать их к вашему списку [строка] (или к любой структуре данных, которую вы используете).

Answer 7

Вы должны попытаться использовать словарь класса. Это намного быстрее, чем List, потому что это индексированный поиск.

Dictionary<String, String> ldapDocument = new Dictionary<String, String>();
//load your list here
//Sample -> ldapDocument.Add("014548787","014548787");
var match = ldapDocument.ContainsKey(stringToMatch);