[issue44699] Simple regex appears to take exponential time in length of input
János Brezniczky
report at bugs.python.org
Wed Jul 21 11:21:57 EDT 2021
New submission from János Brezniczky <brezniczky at gmail.com>:
I don't know if it's normal, but it's impractical.
I seem to have come by an expression consuming o(c^n) CPU cycles with c around 2.
Regex:
\*([^*]+)*\*
Resulted in times (in seconds) of
0.17 (* is there anybody out?)
0.34 1
0.69 12
1.36 123
2.73 1234
5.44 12345
11.1 123456 (* is there anybody123456 out?)
Please see the source for more details/repro.
----------
components: Regular Expressions
files: regex_test.py
messages: 397948
nosy: brezniczky, ezio.melotti, mrabarnett
priority: normal
severity: normal
status: open
title: Simple regex appears to take exponential time in length of input
type: performance
versions: Python 3.8
Added file: https://bugs.python.org/file50169/regex_test.py
_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue44699>
_______________________________________
More information about the Python-bugs-list
mailing list