.NET RegExp оптимизации производительности поисковой

Question

У меня есть коллекция Список с около 35000 строк

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

"<i>füüs</i>ampri tähis;lüh ld-st<i>anno</i>, aastal;<i>maj</i> lüh pr-st<i>argent</i>, raha (kursisedelitel)" 

В основном эта строка содержит кучу слов на эстонском языке :)

Мне нужно разрешить пользователю выполнять поиск RegExp по 35 000 строк

Если я выполняю поиск с использованием выражения /ab.*/, то поиск принимает меньше, чем как econd

Если я выполнить поиск с помощью /.*ab/ выражения, то поиск занимает около 10 секунд

Мой вопрос: Как я могу сделать второй поиск быстрее (менее 1,5 секунды)?

Большое спасибо

Answer 1

Использование compiled regular expressions для лучшей производительности

http://en.csharp-online.net/CSharp_Regular_Expression_Recipes -Compiling_Regular_Expressions

копия вставьте полный URL, выглядит как есть делает проблему с этой ссылки.

Answer 2

Я получил эту сумасшедшую идею, что вы также можете хранить строки в обратном порядке и искать эти строки с помощью/ba. */если пользователь вводит /. * ab /.

Answer 3

Ваше второе выражение будет соответствовать «ab» и всем символам перед ним (кроме новой строки). Вы можете попробовать только поиск/ab /, получить индекс соответствия и, как результат, выполнить часть строки, предшествующую совпадению, с совпадением.

Answer 4

Это то, как обрабатываются регулярные выражения, которые заставляют их выполнять разные действия. Для того, чтобы объяснить, что на основе ваших примеров:

• /.*ab/ Это выражение состоит на два подвыражения, в .* и буквальном ab. Это будет обрабатываться следующим образом: в нормальном жадном режиме, где каждый квантор и, следовательно, совпадение расширяется до максимального значения, .* сначала будет соответствовать всей строке. Затем он попытается сопоставить следующие ab. Но поскольку это невозможно (мы уже находимся в конце строки), backtracking будет использоваться, чтобы найти последнюю точку, где совпадают оба подвыражения. Таким образом, матч .* уменьшается на один символ и снова тестируется ab. Если целое выражение не может быть сопоставлено, совпадение .* снова будет уменьшено на один символ, пока не будет согласовано все выражение. В худшем случае в строке нет ab, и алгоритм будет делать n +1 backtracks и дополнительные тесты для ab, пока он не сможет определить, что совпадение невозможно.

• /ab.*/ Это выражение также состоит из двух подвыражений. Но здесь порядок меняется, сначала буквал ab, а не .*. Это обрабатывается следующим образом: сначала алгоритм пытается найти литерал ab путем сравнения одного символа с другим.Если есть совпадение, он пытается найти соответствие для .*, что очевидно легко.

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

Попробуйте использовать инструмент анализа регулярных выражений, такой как RegexBuddy, чтобы визуально увидеть разницу.

Answer 5

Есть две возможные модификации, которые я могу предложить для медленного выражения .*ab.

Я выполнил свои тесты с помощью этой тестовой строки «1234567890 ab 1234567890», используя функцию бенчмаркинга в Regex Hero.

A. 5X быстрее, чем оригинальный

^.*ab 
RegexOptions.None 

или

B. 8X быстрее, чем оригинал

.*ab 
RegexOptions.RightToLeft 

Иногда экспериментирование окупается. Вариант RightToLeft был моим «ах-ха!». момент. Это, по сути, возвращает ту же производительность, что и ваше другое выражение ab.*, предотвращая появление массивного обратного отсчета.