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

Question

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

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

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

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

Answer 1

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

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

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

       \[\[.+?\]\]
Атом # 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. успех

Смотреть вперед:

       \ [\ [(?:?! (\] \].))+\]\]
Атом # 1 2 3  4       5  6 7

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

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

Разновидность.NET поддерживает атомарные группы, но не собственнические кванторы

Answer 4

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