Как быстро на c# искать в строке массив строк?

Question

[prog323]

Сейчас ищу в строке line вхождение массива строк s

string[] s = { "тест1","тест2","тест3","тест4" };

for (int j = 0; j < s.Length; j++)
{
  if (line.IndexOf(s[j]) > 0)
  {

  }
}

Как можно искать ещё быстрее этого кода?

Comments

[AlexP11223]

Задача-то в чем состоит? Может вам и не массив строк нужен.

И зачем быстрее?

[prog323]

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

[AlexP11223]

Ну задачу-то расскажите, может можно как-то более эффективно хранить эти строки.

[Сергей Протько]

@prog323, количество итераций и сложность алгоритма будет приблизительно одинаковой, как вы эту функцию не крутите.

Правда я крайне сомневаюсь что этот маленький циклик узкое место.

Answer 1

[AM5800]

Я не нашел точной информации, но, похоже, что string.IndexOf использует простоейший алгоритм поиска подстроки, который работает за O(nm). (n - длина исходной строки, m - длина образца).
А поскольку у вас еще p образцов - получаем кубическую сложность.

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

Но, на первый взгляд мне кажется, что вам вполне подойдет алгоритм Ахо—Корасик

Comments

[prog323]

@AM5800 а как на c# будет это выглядеть?

[prog323]

то есть - есть ли что то встроенное лучше indexof или нужно писать?

[AlexP11223]

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

[AM5800]

Встроенного, на сколько я знаю, нет. Можно поискать готовую реализацию в сторонних библиотеках.

[AM5800]

Вот, например, один из первых результатов поиска
https://github.com/pdonald/aho-corasick

[prog323]

@AM5800 спасибо понял, а что может быть ещё быстрее c++/erlang? или на c# еще что то может быть?

[AM5800]

C++ теоретически может быть быстрее. На практике - может и не быть быстрее. Нужно пробовать.

Улучшения производительности после Ахо—Корасика вам не хватило?

[prog323]

@AM5800 да спасибо, ускорение в разы

Answer 2

[lam0x86]

Прошу прощение за некропостинг, но есть гораздо более простое решение, чем Ахо-Корасики =)

string[] array = { "тест1", "тест2", "тест3", "тест4" };

if (new Regex(string.Join("|", array.Select(Regex.Escape))).IsMatch(line))
{
    // do work
}