Ciekawostka: implementacja wyrażeń regularnych w .NET

Ostatnio znajomy podesłał mi ciekawe wyrażenie regularne, którego wykonanie trwa bardzo długo w aktualnej implementacji REGEX. Wyrażenie to “(a?){30}a{30}”. Nic specjalnego. Najpierw mamy 30 opcjonalnych liter ‘a’, a potem 30 obowiązkowych. Nie wygląda to zbyt skomplikowanie. Spróbujmy wykonać wyrażenie na tekście “aaaaaaaaaaaaaaaaaaaaaaaaaaa”.

const int tests = 10;
for (int i = 0;i< tests; i++)
{
 var stopwatch = Stopwatch.StartNew();
var result = Regex.IsMatch(new string('a',35), 
 long time = stopwatch.ElapsedMilliseconds;
 Console.WriteLine(time);
}

Wykonanie pojedynczej operacji, zajmie kilka sekund.  Dlaczego? Związane jest to ze sposobem w jaki REGEX został zaimplementowany. Najpierw szukamy 30 znaków ‘a’ (opcjonalnych). Znajdujemy je. Następnie widzimy, że mamy 30 obowiązkowych znaków. Niestety nie znajdziemy ich. Musimy z tego względu usunąć jeden znak  z pierwszej grupy (czyli mamy 29 znaków opcjonalnych teraz) i znów dopasować drugą grupę. Oczywiście znów zabraknie nam literek ‘a’ w drugiej grupie i rozwiązanie będzie polegać na usunięciu kolejnego znaku z pierwszej grupy. Efekt jest taki, że wykonanie prostego zapytania zajmie bardzo dużo czasu. Gdybyśmy mieli więcej niż 60 liter ‘a’, nie wystąpiłby podobny problem ponieważ wszystkie znaki (zarówno opcjonalne jak i obowiązkowe), zostałby dopasowane.

Leave a Reply

Your email address will not be published.