Java регулярное выражение или слишком медленно

Question

Почему шаблон

[0123]123456|98765 

дважды медленно, как выполнить [0123] 123456, а затем в Java? Поэтому быстрее искать их отдельно, чем выполнять с OR. У кого-нибудь есть объяснение?

UPD

См тестового примера с результатами: https://gist.github.com/cy6erGn0m/5077720

UPD2

я обнаружил, что причина заключается в java.util.regex. Следующий тест дает понять: https://gist.github.com/cy6erGn0m/5083426

Так как вы можете видеть, что Matcher делает значительно больше запросов к исходной последовательности символов. Таким образом, первый шаблон требует примерно в 2 раза больше запросов к источнику, чем двух отдельных шаблонов.

Многострочный и нечувствительный к регистру не имеет значения. Или оператор влияет на сложность.

Answer 1

OK. Похоже, я нашел половину ответа.

Когда у нас есть только шаблон, похожий на 123456, то в regexp engine используется алгоритм соответствия строк Boyer-Moore. Но если у вас есть ИЛИ, то он не использует его и просто сравнивает каждый символ.

Из-за своей природы алгоритм Бойер-Мура может быть намного более эффективным, поэтому поэтому второй подход выполняется быстрее.

Например, если у меня есть строка ввода «11223344» и рисунок «123456», то в соответствии с реализацией Бойера-Мура единственный символ должен быть отмечен «3» на 5-й позиции. Это намного эффективнее, чем пытаться проверить шаблон против КАЖДОГО символа.