Tenho um arquivo grande (gigabyte) onde uma expressão S aparece, e quero pular para o final da expressão S. A profundidade da expressão S é limitada a 2, então tentei usar uma expressão regular Python ( b'\\((?:[^()]|\\((?:[^()]|)*\\))*\\)'). Isso acabou consumindo muita RAM, e pesquisando mais a fundo descobri que o consumo de memória de expressões regulares moderadamente complexas parece altamente imprevisível se a correspondência for grande. Por exemplo, as quatro expressões regulares equivalentes a seguir correspondem a uma string completa de dez megabytes. A quarta (indiscutivelmente a mais complexa) usa uma quantidade razoável (30 M) de RAM, enquanto as outras consomem um gigabyte:
import re
dot = b'[' + b''.join(b'\\x%02x' % (c,) for c in range(256)) + b']'
assert re.match(b'(?:.|.)*', b'a'*10000000).end() > 1000000
assert re.match(b'(?:.|.|a)*', b'a'*10000000).end() > 1000000
assert re.match(b'(?:%s|%s)*' % (dot,dot), b'a'*10000000).end() > 1000000
assert re.match(b'(?:%s|%s|a)*' % (dot,dot), b'a'*10000000).end() > 1000000
(usando Python 3.12.3)
Existe uma maneira razoável de prever se o desempenho de uma regexp Python pode ser escalável? E, em particular, existem alguns princípios de design que eu possa seguir se quiser evitar armadilhas de desempenho?
(Esta pergunta é especificamente sobre o remódulo, porque prefiro usar bibliotecas Python padrão; suspeito que isso não seria um problema se eu mudasse para uma biblioteca de terceiros como regex)