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

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

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

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

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

Ответы

Ответ 1

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

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

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

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

Ответ 2

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

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

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

Ответ 3

Вы пытались загрузить ваши строки в 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);

Ответ 4

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

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

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

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

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

Ответ 5

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

Основываясь на тестах, которые я сделал, этот вариант Contains был на 33% быстрее на моей стороне.

Ответ 6

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

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

Ответ 7

Согласно этим тестам, самый быстрый способ проверить, встречается ли строка в строке, заключается в следующем:

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] - общее количество каждого найденного.

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