Postado por Eyal Schneider em 21 de maio de 2009 O pacote java.util.regex foi adicionado ao Java na versão 1.4. É uma ferramenta muito poderosa e é preciso se tornar um mestre para usá-la corretamente. Mesmo quando
uma expressão regular é verdadeira, ela pode ser muito lenta se não for escrita de forma inteligente. Continue lendo se quiser entender a causa dos problemas, ou vá até o final da página onde encontrará 10 dicas úteis para melhorar o desempenho de expressões regulares em Java.
É realmente tão lento?
Digamos que queremos selecionar apenas linhas contendo a sequência de caracteres “a” e “b”. A solução correta pode ser:
(a*b*)* No entanto, se você executar a expressão com, por exemplo, a string “aaaaaaaaaaaaaaaaaaaaaaaaaaaax” , levará vários minutos antes que ela termine e não relate nenhuma correspondência! Claro, o melhor regex neste caso seria:
(a|b)* Isso leva menos de um milissegundo na minha máquina com a mesma string. Claramente há um problema de desempenho aqui.
Por que isso está acontecendo?
Como a maioria dos mecanismos regexp, Java usa uma abordagem NFA (Non-Deterministic Finite Automata). O mecanismo verifica os componentes regex um por um e avança pela string de entrada de acordo. E ele pode voltar ao início para encontrar alternativas adequadas caso chegue a um “beco sem saída”. Resultados alternativos são obtidos usando estruturas regulares como quantificadores (
*, +, ? ) e alternâncias (por exemplo,
a|b|c|d ). Esta técnica de pesquisa é chamada de retrocesso. No terrível exemplo acima, o mecanismo irá realmente examinar TODAS as decomposições em série do símbolo "a" em séries menores até perceber que não há correspondências. Este exemplo mostra como o algoritmo de retrocesso pode resultar em uma estimativa de tempo exponencial (dependendo do comprimento da string de entrada). Isto também mostra uma propriedade importante do AFN: sempre haverá piores casos que quase correspondem ao padrão. Se uma correspondência for encontrada, a pesquisa será interrompida. A outra abordagem principal para uso em regex é DFA (Deterministic Finite Automaton). Nessa abordagem, a expressão regular na verdade constrói um autômato que é usado para percorrer as strings de entrada caractere por caractere sem retroceder. Isto dá tempo linear para toda a entrada, independentemente da complexidade da expressão regular. Em vez de verificar sequencialmente uma string em busca de correspondências (como no NFA), o DFA simula a verificação paralela. Então, por que Java (e .NET, Perl, Python, Ruby, PHP, etc.) usa NKA e não DKA, que tem um comportamento muito melhor? A razão é que o NKA tem uma série de vantagens significativas:
- Compila mais rápido e requer muito menos memória
- Permite alguns recursos úteis (veja o tutorial da Sun para detalhes ):
- Captura de grupo e backlinks
- Verificação posicional
- Quantificadores Estendidos (Ganancioso e Preguiçoso)
É importante notar que os termos populares NKA e DKA são imprecisos quando usados no contexto de expressões regulares. Em teoria, esses dois modelos têm o mesmo poder computacional. Isso significa que você não pode escrever uma expressão regular em um modelo de autômato que seria impossível de expressar em outro. Na prática, há necessidade de mais capacidades para que os dois tipos de implementação divirjam na semântica. Os motores NKA oferecem mais flexibilidade, tornando-os superiores aos DKA em poder de computação. Devido à velocidade do DFA e aos recursos exclusivos do NFA, existem mais 2 maneiras “pré-fabricadas” de implementar expressões regulares. Algumas implementações usam ambos os tipos (por exemplo, GNU egrep, que seleciona um mecanismo específico em tempo de execução), e algumas conseguiram implementar uma versão verdadeiramente híbrida (por exemplo, Tcl regexps) com todos os benefícios.
Conselho
A seguir estão algumas dicas sobre como evitar problemas de eficiência de regex em Java. Muitos deles visam reduzir retornos.
1) Pré-compilação
Banal, mas vale a pena mencionar. Se você usar o regexp mais de uma vez, compile-o com antecedência:
// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);
2) Quantificadores Preguiçosos vs. Quantificadores Gananciosos
Por padrão, os quantificadores (
* + ? ) são gananciosos. Isso significa que eles começam a combinar com a sequência mais longa possível e, em seguida, voltam gradualmente, se necessário. Se você sabe com antecedência que as correspondências geralmente serão curtas, você deve usar quantificadores preguiçosos. Eles começam com a menor partida e avançam se necessário. Digamos que queremos encontrar apenas linhas que correspondam à sequência “olá”.
O .*hello.* normal fará tudo certo, mas se soubermos que "hello" geralmente aparece mais próximo do início do texto, então
.*?hello.* funcionará mais rápido, em média.
3) Use quantificadores super gananciosos sempre que possível
Ao contrário dos quantificadores preguiçosos, que afetam o desempenho, mas não afetam o comportamento regular, os quantificadores supergananciosos podem, na verdade, alterar o significado de uma expressão regular. Quando
*+ for usado em vez de
* , a primeira correspondência será gananciosa (ou seja, a maior possível como se fosse apenas *), mas não haverá fallback se falhar, mesmo que isso faça com que toda a pesquisa falhe. Quando isso pode ser útil? Digamos que precisamos encontrar o texto entre aspas.
O \"[^\"]*\" regular funcionará bem. No entanto, fará recuos desnecessários em casos negativos (por exemplo, “bla bla bla). Usar
\"[^\"]*+\" eliminará reversões sem alterar o significado da expressão. O agrupamento independente obtém o mesmo efeito e oferece ainda mais controle (consulte
o tutorial da Sun ).
4) Evite captura em grupo
Qualquer expressão entre parênteses é considerada um grupo por padrão. Isso tem um pequeno impacto no desempenho. Torne seus grupos "incapturáveis" sempre que possível, iniciando-os com
(?: em vez de
( .
5) Use a intercalação com sabedoria
Quando a intercalação é usada (por exemplo,
Paul|Jane|Chris ), a ordem na qual o mecanismo tenta combinar as opções é a mesma ordem em que elas aparecem. Você pode aproveitar esse recurso e colocar as opções mais comuns mais perto do início. Isso melhorará o tempo médio de resposta positiva.
6) Evite ambigüidades
Escreva expressões regulares de forma a minimizar o número de correspondências diferentes na string de entrada. Por exemplo: a expressão regular
(a*b*)* dada no início do artigo permite que a string "aabb" seja interpretada de muitas maneiras:
(a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp
(a|b)*, por outro lado, apenas interpreta único combinações positivamente. Isto é muito importante para reduzir os retornos em casos
de quase correspondência.
7) Visualização
A visualização permite adicionar restrições às sequências à esquerda/direita da posição atual. Em particular, com um lookahead negativo, você pode procurar por linhas que não contenham alguma sequência (o que faríamos sem isso!). Como isso pode ajudar a aumentar a produtividade? Digamos que queremos obter o URL da tag do link. Considere o seguinte regexp:
a .* href=(\S*).*/ Para tags regulares, esta expressão só corresponderá ao endereço se o texto contiver o atributo "href" (\S é usado para todos os caracteres, exceto delimitadores). Mas em algumas tags incomuns, por exemplo, ocorrerá uma reversão. Por exemplo: “a href= href=href=…. href = alguma coisa.” O seguinte regexp evitará que isso aconteça ao substituir “.*” em uma expressão por algo que não corresponda a “href”:
a ((?!href).)* href=(\S*)((?!href).)*/
8) Especifique o comprimento
Java contém um otimizador regexp que verifica o comprimento da string de entrada em relação aos comprimentos mínimo e máximo obtidos da expressão regular. Isso permite que você interrompa a pesquisa imediatamente em alguns casos. Para auxiliar esse mecanismo, o número de repetições deve ser especificado sempre que possível (por exemplo,
[01]{6} corresponde a todas as strings binárias com seis caracteres).
9) Selecione linhas idênticas
Às vezes, strings iguais ficam ocultas dentro de grupos ou alternativas:
(hello|hell|heel) Esta expressão pode ser simplificada para:
he(llo|ll|el) Ao fazer isso, fornecemos mais informações ao otimizador regexp.
10) Teste sua expressão regular
Pode ser aconselhável testar primeiro a expressão regular quando ela for usada em um aplicativo de desempenho crítico. Escreva um micro-benchmark que teste sua expressão em vários dados de entrada. Certifique-se de testar dados de comprimentos variados e também dados que correspondam melhor à sua amostra.
Links:
http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -of-Expression-Processing/
GO TO FULL VERSION