Лучше использовать некожадный классификатор или упущение? - PullRequest
Новая
       34

Лучше использовать некожадный классификатор или упущение?

6 голосов
/ 04 июня 2010

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

Я могу придумать два способа сопоставить этот текст:

  • Использование некожадного квалификатора: /\[\[.+?\]\]/
  • Использование предвидения: /\[\[(?:(?!\]\]).)+\]\]/

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

Ответы [ 4 ]

6 голосов
/ 04 июня 2010

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

Взять этот пример строки "[[a]b]]"

Нежадный квантификатор 

       \[\[.+?\]\]
Atom # 1 2 3  4 5
  1. Атом # 1 \[ соответствует
  2. Атом # 2 \[ соответствует
  3. Атом # 3 .+? соответствует "a"
  4. Атом # 4 \] совпадений
  5. Атом # 5 \] завершается неудачно, возвращается к # 3, но сохраняет строковую позицию
  6. Атом # 3 .+? соответствует "]"
  7. Атом # 4 \] завершается неудачно, возвращается к # 3, но сохраняет строковую позицию
  8. Атом # 3 .+? соответствует "b"
  9. Атом # 4 \] совпадений
  10. Атом # 5 \] совпадений
  11. успех

Посмотрите вперед: 

       \[\[(?:(?!\]\]).)+\]\]
Atom # 1 2 3  4       5  6 7
  1. Атом # 1 \[ соответствует
  2. Атом # 2 \[ соответствует
  3. Атом # 4 (?!\]\]) успешно (т.е. не совпадает) немедленно в "a", перейти на
  4. Атом # 5 . соответствует "a", повторите на # 3
  5. Атом # 4 (?!\]\]) достигает частичного совпадения при "]"
  6. Atom # 4 (?!\]\]) успешно (т.е. не совпадает) на "b", продолжайте
  7. Атом # 5 . соответствует "]", повторите на # 3
  8. Атом # 4 (?!\]\]) успешно (т.е. не совпадает) немедленно в "b", перейти на
  9. Атом # 5 . соответствует "b", повторите на # 3
  10. Атом # 4 (?!\]\]) достигает частичного совпадения при "]"
  11. Атом # 4 (?!\]\]) достигает полного совпадения при "]", следовательно: # 4 не удалось, выход # 3
  12. Атом # 6 \] соответствует
  13. Атом # 7 \] совпадений
  14. успех

Таким образом, похоже, что у жадного квантификатора меньше работы.

Отказ от ответственности: это искусственный пример, и реальная производительность может отличаться в зависимости от ввода, фактического выражения и реализации механизма регулярных выражений. Я только на 98% уверен, что то, что я изложил здесь, - это то, что на самом деле происходит, поэтому я открыт для исправлений. Кроме того, как и во всех советах по производительности, не принимайте это за чистую монету, сделайте свои собственные сравнительные тесты, если хотите знать наверняка.

3 голосов
/ 04 июня 2010

Другой вариант: /\[\[((?:\]?[^]])+)]]/

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

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

1 голос
/ 04 июня 2010

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

\[\[(?:[^\]]++|\](?!\]))*+\]\]

[^\]]++ поглощает любые символы, кроме ], и не беспокоит сохранение информации о состоянии, которая сделала бы возможным возврат.Если он видит ], он просматривает, есть ли другой.Оборачивание всего этого в другой собственник-квантификатор означает, что он просматривает только всякий раз, когда видит ], и возвращается только один раз: когда он находит закрывающий ]].

Явные квантификаторы поддерживают Java, JGSoft, PCRE (PHP), Oniguruma (Ruby 1.9) и Perl 5.12.Все эти разновидности также поддерживают атомарные группы, которые можно использовать для достижения того же эффекта: 

\[\[(?>(?:(?>[^\]]+)|\](?!\]))*)\]\]

. Аромат .NET поддерживает атомные группы, но не обладает квантификаторами владения.

0 голосов
/ 04 июня 2010

Я думаю, что лучше использовать не жадный классификатор. Вы уверены, что в прочитанной статье не говорилось «будьте осторожны с жадным соответствием?»

...