Este link contem uma boa explicação a respeito, cujas ideias eu também explico aqui abaixo, com um exemplo que construí e rodei na minha máquina.
Entradas inválidas podem causar uma performance muito ruim com expressões regulares mal definidas. Um exemplo de expressões regulares mal definidas são as que reconhecem a entrada de mais de uma maneira possível, e, por consequência, tentam reconhecer entradas inválidas de várias formas possíveis.
De maneira geral, o tempo gasto para reconhecer uma entrada inválida pode aumentar de maneira exponencial com respeito ao número de caracteres n
da entrada
Exemplo
A expressão regular xx+y
pode ser escrita também como (x+x+)+y
. A primeira expressão traduz-se para um autômato finito determinístico, sem backtracking, enquanto que a segunda expressão utiliza backtracking. Quando uma entrada válida é reconhecida, não há problema, pois o autômato encerra a busca imediatamente. Quando uma entrada inválida é fornecida, no entando, o mecanismo de reconhecimento vai tentar todas as formas de reconhecimento possíveis, até ter certeza de que a entrada não pode ser reconhecida pela Regex.
Segue um exemplo de código e sua saída correspondente, na minha máquina. O exemplo é em C#, mas os conceitos são agnósticos de tecnologia:
using System;
using System.Diagnostics;
using System.Text.RegularExpressions;
namespace TesteRegex
{
class Program
{
static void Main(string[] args)
{
string padraoMau = "(x+x+)+y";
string padraoBom = "xx+y"; ;
string[] arrayBom = new string[] { "xxy", "xxxxxxy", "xxxxxxxxxxxxxxxxxxxxy", "xxxxxxxxxxxxxxxxxxxxxxy", "xxxxxxxxxxxxxxxxxxxxxxxxxxy" };
string[] arrayMau = new string[] { "xxx", "xxxxxxx", "xxxxxxxxxxxxxxxxxxxxx", "xxxxxxxxxxxxxxxxxxxxxxx", "xxxxxxxxxxxxxxxxxxxxxxxxxxx" };
Console.WriteLine("---- Backtracking: sim; Entrada válida: sim ----");
TestaRegex(padraoMau, arrayBom);
Console.WriteLine("------------------------------------------------");
Console.WriteLine("---- Backtracking: sim; Entrada válida: não ----");
TestaRegex(padraoMau, arrayMau);
Console.WriteLine("------------------------------------------------");
Console.WriteLine("---- Backtracking: não; Entrada válida: sim ----");
TestaRegex(padraoBom, arrayMau);
Console.WriteLine("------------------------------------------------");
Console.WriteLine("---- Backtracking: não; Entrada válida: não ----");
TestaRegex(padraoBom, arrayMau);
Console.WriteLine("------------------------------------------------");
Console.ReadLine();
}
private static void TestaRegex(string padrao, string[] array)
{
Console.WriteLine("Tamanho da entrada | Tempo gasto");
Console.WriteLine("------------------------------------");
Stopwatch sw = new Stopwatch();
for (int i = 0; i < array.Length; i++)
{
sw.Start();
Regex.IsMatch(array[i], padrao);
sw.Stop();
Console.WriteLine(" " + string.Format("{0,2}", array[i].Length) + "| " + sw.Elapsed.ToString("ss\\.ffffff"));
sw.Reset();
}
}
}
}
Saída:
---- Backtracking: sim; Entrada válida: sim ----
Tamanho da entrada | Tempo gasto
------------------------------------
3| 00.000347
7| 00.000021
21| 00.000003
23| 00.000002
27| 00.000002
------------------------------------------------
---- Backtracking: sim; Entrada válida: não ----
Tamanho da entrada | Tempo gasto
------------------------------------
3| 00.000011
7| 00.000039
21| 00.594714
23| 02.359978
27| 38.033123
------------------------------------------------
---- Backtracking: não; Entrada válida: sim ----
Tamanho da entrada | Tempo gasto
------------------------------------
3| 00.000043
7| 00.000005
21| 00.000014
23| 00.000017
27| 00.000024
------------------------------------------------
---- Backtracking: não; Entrada válida: não ----
Tamanho da entrada | Tempo gasto
------------------------------------
3| 00.000008
7| 00.000007
21| 00.000019
23| 00.000020
27| 00.000024
------------------------------------------------
O único caso de performance sofrível foi o de entradas inválidas, numa regex com backtracking (38 segundos com backtracking versus menos de um milésimo para a versão sem backtracking, para um entrada de tamanho 27).
O problema é que o número de formas de tentar reconhecer um string inválida, na versão sem backtracking, está associado ao número de partições de um número inteiro , que é exponencial no tamanho da entrada, o que causa a performance ruim.
Solução: ao definir uma expressão regular, assegure-se de que há uma forma (ou o menor número de formas possível) apenas para reconhecer tanto entradas válidas quanto inválidas. Prefira expressões simples, como xx+y, ao invés de (x+x+)y .
No caso dos exemplos que você forneceu para comparação, eles vão possuir performance similar (boa).