Рекомендации по работе с регулярными выражениями VS sheer iteration

Question

Мне было интересно, существуют ли какие-либо общие рекомендации по использованию regex VS "string".contains("anotherString") и/или другим вызовам String API?

Хотя вышеописанное решение для .contains() тривиально (зачем беспокоиться о регулярном выражении, если вы можете сделать это за один раз), реальная жизнь приносит более сложные варианты. Например, лучше ли делать два вызова .contains() или одно регулярное выражение?

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

Другим, часто упускаемым из виду аргументом является производительность. Как узнать, сколько итераций (как в «Big O») требуется для этого регулярного выражения? Будет ли это быстрее, чем простое повторение? Почему-то все предполагают, что если регулярное выражение выглядит короче, чем 5 if, то оно должно быть быстрее. Но всегда ли это так? Это особенно важно, если регулярное выражение не может быть предварительно скомпилировано заранее.

Answer 1

Ответ (как обычно) заключается в том, что это зависит.

В вашем конкретном случае, я думаю, альтернативой было бы сделать регулярное выражение «this | that», а затем сделать находку. Эта конкретная конструкция действительно вызывает у слабостей регулярных выражений. «OR» в этом случае действительно не знает, что пытаются использовать подмаски, и поэтому не может легко оптимизировать.Он заканчивает тем, что делает эквивалент (в псевдокоде):

for(i = 0; i < stringLength; i++) { 
    if(stringAt pos i starts with "this") 
     found! 
    if(stringAt pos i starts with "that") 
     found! 
} 

Там почти не медленнее способ сделать это. В этом случае два вызова() будут намного быстрее.

С другой стороны, полное совпадение: ".*this.*|.*that.*" может оптимизироваться лучше.

Для меня регулярное выражение должно использоваться, когда код, который нужно сделать иначе, сложный или громоздкий. Поэтому, если вы хотите найти одну или две строки в целевой строке, тогда просто используйте contains. Но если вы хотите найти слова, начинающиеся с «A» или «B» и заканчивающиеся на «g» - «m» ... затем используйте regex.

И тогда вас не будет так беспокоить несколько циклов здесь и там.

Answer 2

Я бы настоятельно рекомендовал вам написать код для обоих и время его. Это довольно просто сделать, и вы получите ответы, которые не являются общим «эмпирическим правилом», а скорее очень конкретным ответом на ваш проблемный домен.

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

http://msdn.microsoft.com/en-us/magazine/cc500596.aspx

Если вы хотите мое личное «правило thumb ", то это то, что RegEx часто медленнее для такого рода вещей, но вы должны игнорировать меня и измерять его самостоятельно :-)

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

http://www.amazon.co.uk/Regular-Expressions-Cookbook-Jan-Goyvaerts/dp/0596520689/ref=sr_1_1?ie=UTF8&s=books&qid=1259147763&sr=8-1

... как это имеет огромное количество советов по ускорению кода RegEx. Я оптимизировал код RegEx в 10 раз, следуя советам из этой книги.

Answer 3

Трудно оценить производительность без использования профайлера, как правило, лучшей стратегией является написать то, что делает наиболее логичный смысл и легче понять/прочитать. Если два вызова .contains() легче логически понять, тогда это лучший маршрут, та же логика применяется, если регулярное выражение имеет больше смысла.

Также важно учитывать, что другие разработчики в вашей команде могут не иметь большого понимания регулярного выражения. Если в более позднее время в производстве использование regex over .contains() (или наоборот) идентифицируется как узкое место, попробуйте и профиль обоих.

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

Answer 4

RegexBuddy имеет встроенный отладчик регулярных выражений. Он показывает, сколько шагов требуется движку регулярных выражений, чтобы найти совпадение или не найти совпадение. Используя отладчик в строках разной длины, вы можете получить представление о сложности (большой O) регулярного выражения. Если вы посмотрите «контрольный показатель» в индексе файла справки RegexBuddy, вы получите еще несколько советов о том, как интерпретировать это.

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

Чтобы использовать ваш 5, если заявления в качестве примера, регулярное выражение one|two|three|four|five сканирует входную строку раз, делая немного дополнительной работы, когда o, t или f встречается. Но 5, если утверждения, проверяющие, содержит ли строка слово, будут искать всю строку 5 раз, если ни одно из слов не может быть найдено. Если five происходит в начале строки, то регулярное выражение находит совпадение мгновенно, в то время как первые 4-х операторы сканируют всю строку напрасно до того, как инструкция 5-го встречает совпадение.