Regex match бросает stackoverflow в java [duplicate]
Мы можем улучшить решение @ JaredPar, чтобы сделать истинную ленивую оценку. Мы используем метод GroupAdjacentBy , который дает группы последовательных элементов с одним и тем же ключом:
sequence
.Select((x, i) => new { Value = x, Index = i })
.GroupAdjacentBy(x=>x.Index/3)
.Select(g=>g.Select(x=>x.Value))
Поскольку группы получаются один за другим, это решение работает эффективно с длинными или бесконечными последовательностями.
3 ответа
Перед исправлением проблемы с StackOverflowError ...
- Я хотел бы указать, что ваше текущее regex
(\d\*?(;(?=\d))?)+не может проверить это условие. Каждое значение может включать в себя один * в конце (используется как подстановочный знак для другого соответствия). Он не может отклонить случай23*4*4*;34*434*34, как показано здесь здесь 1. - Ваше регулярное выражение будет делать ненужный откат на несоответствующем входе.
- Java использует один кадр стека для каждого повторения группы
(\d\*?(;(?=\d))?)(который повторяется 1 или более раз+).
Правильное регулярное выражение будет:
\d+\*?(?:;\d+\*?)*
Обратите внимание, что это отклонит *, что не слишком ясно из вашего требования, хотите ли вы принять или отклонить это.
Это не устраняет проблему StackOverflow, так как каждое повторение группы (?:;\d+\*?) также будет использовать стек. Чтобы исправить это, сделайте все кванторы притяжательными , так как нет необходимости в обратном отслеживании, поскольку грамматика не является двусмысленной:
\d++\*?+(?:;\d++\*?+)*+
Ввод в строковый литерал:
"\\d++\\*?+(?:;\\d++\\*?+)*+"
Я проверил вышеописанное выражение с совпадающим и несоответствующим входом, который имеет более 3600 токенов (разделенных ;).
Сноска
1: regex101 использует аромат PCRE, который немного отличается от аромата Java regex. Однако функции, используемые в вашем регулярном выражении, являются общими между ними, поэтому не должно быть расхождений.
Приложение
- На самом деле, из моего тестирования с вашим регулярным выражением
(\d\*?(;(?=\d))?)+( который является неправильным в соответствии с вашим требованием), что делает большинство+притяжательных++, по-видимому, исправляет проблемуStackOverflowError, по крайней мере, в моем тестировании с примерно 3600 токенами (разделенными;, строка длиной около 20 тыс. символов). Это также, похоже, не приводит к длительному времени выполнения при тестировании на несоответствующую строку. - В моем решении сделать квантификатор
*для группы(?:;\d+\*?)собственником достаточно, чтобы разрешитьStackOverflowError.
Тем не менее, я делаю все притяжательным, чтобы быть в безопасности."\\d+\\*?(?:;\\d+\\*?)*+"
То, что вы можете захотеть, это увеличить максимальный размер вашего стека, чтобы он не переполнялся. Вы можете прочитать о том, как это сделать здесь.
В принципе, вы запускаете свою программу с помощью опции -Xss. Например, -Xss4m Когда я начал свой код с -Xss4m, ваша программа работала без переполнения стека для меня (она возвращает true).
-
1Спасибо за предложение. Но на самом деле я не хочу настраивать параметры JVM, но я буду рассматривать его как последнее средство. – Genzer 26 February 2013 в 08:45
Вы regexp немного неэффективны и не соответствуют вашему описанию. У вас есть '\ d \ *?' - это одна цифра, указанная опционально *. Затем необязательно '; (? = \ D)' - ';' с контрольной цифрой. String '1 * 2 * 3 *' будет соответствовать вашему регулярному выражению, но не вашему описанию. Вы можете использовать regexp. Он соответствует вам ввода и немного более эффективно.
final String TEST_REGEX = "(\\d+\\*?)(?:;\\d+\\*?)+";
Он пройдет тест, когда count & lt; 300, но все еще не удалось получить большие значения. Для проверки ввода используйте операцию простой строки, например indexOf и подстроку .
-
1– Genzer 26 February 2013 в 08:55
StackOverflowError. Я не знал о вещахpossessive. Не могли бы вы предложить любые ссылки RegEx, которые я могу улучшить? – Genzer 26 February 2013 в 12:45