Манипулирование строками против регулярных выражений

Question

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

Однако, принимая во внимание накладные расходы на выполнение некоторых манипуляций со строками ( не говоря об ошибках алгоритма - этодругое дело ), особенно в PHP или Perl (может быть Java), что такое предел , и в этом случае мы можем считать манипулирование строками лучшей альтернативой?Какие регулярные выражения особенно жадные для процессора?

Например, для следующих операций в C++, Java, PHP или Perl, что бы вы порекомендовали

Регулярные выражения будутвероятно, будет быстрее:

• s/abc/def/g или решение на основе ... while((i=index("abc",$x)>=0) ...$y .= substr()...?
• s/(\d)+/N/g или алгоритм сканирования

Но как насчет

• регулярное выражение проверки электронной почты?
• s/((0|\w)+?[xy]*[^xy]){2,7}/u/g

не будет ли ручной и конкретный алгоритм быстрее (и дольше писать)?

edit

Суть вопроса в том, чтобы определить, какой тип регулярного выражения будет лучше переписан специально для данной проблемы с помощью манипуляции со строками?

edit2

Распространенной реализацией является Perl regexp.Например, в Perl - что требует знать, как они реализованы - какого вида регулярного выражения следует избегать, потому что реализация сделает процесс длительным и неэффективным?Это может быть не сложное регулярное выражение ...

редактировать июль 2011 (на основе комментариев)

Я не говорю, что все регулярные выражения медленные.Известно, что некоторые конкретные шаблоны регулярных выражений являются медленными из-за конкретной обработки их и из-за их реализации.Например, в недавних реализациях Perl / PHP, что, как известно, является довольно медленным - и его следует избегать?Ответ ожидается от людей, которые уже провели свои собственные исследования (профилировщик ...) и которые могут дать своего рода общие рекомендации о том, что рекомендуется / чего следует избегать.

Answer 1

Кто сказал, что регулярные выражения были медленными?По крайней мере, в Perl они, как правило, являются предпочтительным методом манипулирования строками.

Регулярные выражения плохи в некоторых вещах, таких как проверка электронной почты, потому что тема слишком сложна, а не потому, что они медленные.* правильное регулярное выражение проверки электронной почты имеет длину более 6000 символов, и он даже не обрабатывает все случаи (сначала вы должны удалить комментарии).

По крайней мере в Perl 5,если у него есть грамматика, его, вероятно, не следует анализировать с помощью одного регулярного выражения.

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

Кажется, вы обеспокоены скоростью регулярного выражения по сравнению с пользовательским алгоритмом, но это не является действительной проблемой, пока выдокажите, что это с профилировщиком.Напишите код наиболее понятным способом.Если регулярное выражение ясно, то используйте регулярное выражение.Если пользовательский алгоритм понятен, используйте пользовательский алгоритм.Если после профилирования кода вы обнаружите, что либо занимает много времени, то начинайте искать альтернативы.

Answer 2

Приятной особенностью манипулирования текстом с помощью регулярных выражений является то, что шаблоны являются высокоуровневыми и декларативными. Это оставляет реализацию значительным пространством для оптимизации, такой как выделение самого длинного общего префикса или использование Boyer-Moore для статических строк. Краткая запись делает для быстрого чтения экспертами. Я сразу понимаю, что

if (s/^(.)//) {
  ...
}

делает, а index($_, 0, 1) = "" выглядит шумно в сравнении.

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

Answer 3

какой тип регулярного выражения лучше было бы переписать специально для данной проблемы с помощью обработки строк?

Easy.

1. Определите, нужно ли вам что-либо переписывать.
   (положительный ответ будет примерно для 1 на 10000 сценариев, массивный разбор текста, критический ресурс)
2. Do профиль возможные решения.
3. Используйте один подходящий вам для данной проблемы

Что касается остальных 9999 дел, не тратьте свое время на такую ​​мелочь и используйте все, что вам больше нравится.

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

Answer 4

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

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

Я столкнулся с этим решением ранее в этом году.На самом деле задача была на внешней стороне того, что было возможно с регулярными выражениями.В конце концов я решил написать свой собственный синтаксический анализатор, встроенный pushdown, который невероятно эффективен для того, что я пытался сделать.Задача, между прочим, заключалась в том, чтобы создать что-то, что могло бы анализировать регулярные выражения и обеспечивать для них подсказку, похожую на Intellisense.

Несколько иронично, что я не использовал регулярные выражения для разбора регулярных выражений, но вы можете прочитать об этой мысли здесь ... http://blog.regexhero.net/2010/03/code-hinting-for-regular-expressions.html

Answer 5

Регулярные выражения никогда не будут быстрее, чем ручной алгоритм для очень конкретной цели. Хуже того, в PHP они должны компилироваться при первом использовании (впоследствии используется кеш).

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

Например, preg_replace('/a/', 'b', $string) почти наверняка будет быстрее, чем зацикливание в PHP через строку. Но это постоянный штраф во времени выполнения, и иногда регулярные выражения из-за обратного отслеживания могут иметь гораздо худшее асимптотическое поведение.

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

Answer 6

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