Regex zajmuje zaskakująco dużo czasu

Question

Mam ciąg wyszukiwania wpisany przez użytkownika. Normalnie łańcuch wyszukiwania jest dzielony przy użyciu białych znaków, a następnie wykonywane jest wyszukiwanie OR (element pasuje, jeśli pasuje do dowolnego elementu łańcucha wyszukiwania). Chcę udostępnić kilka "zaawansowanych" funkcji zapytań, takich jak możliwość użycia cudzysłowów do zawarcia fraz dosłownie zawierających spacje.

Chociaż udało mi się wymyślić przyzwoity regex, aby podzielić mi struny, ale wykonanie zaskakująco długiego czasu (> 2 sekundy na mojej maszynie). Zerwałam go, aby dowiedzieć się, gdzie jest czkawka, a jeszcze ciekawiej wydaje się, że po ostatnim Match jest dopasowany (prawdopodobnie na końcu wejścia). Wszystkie mecze do końca pasują do siebie w krótszym czasie, niż mogę to zrobić, ale ten ostatni mecz (jeśli tak jest - nic nie wraca) zajmuje prawie wszystkie 2 sekundy.

Miałem nadzieję, że ktoś może mieć pewien wgląd w to, w jaki sposób mogę nieco przyspieszyć to regex. Wiem, że używam lookbehind z nieograniczonym kwantyfikatorem, ale, jak powiedziałem, nie wydaje się to powodować żadnych problemów z wydajnością, dopóki nie zostanie dopasowany ostatni mecz.

KOD

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Text.RegularExpressions; 

namespace RegexSandboxCSharp { 
    class Program { 
     static void Main(string[] args) { 

      string l_input1 = "# one \"two three\" four five:\"six seven\" eight \"nine ten\""; 

      string l_pattern = 
       @"(?<=^([^""]*([""][^""]*[""])?)*)\s+"; 

      Regex l_regex = new Regex(l_pattern); 

      MatchCollection l_matches = l_regex.Matches(l_input1); 
      System.Collections.IEnumerator l_matchEnumerator = l_matches.GetEnumerator(); 

      DateTime l_listStart = DateTime.Now; 
      List<string> l_elements = new List<string>(); 
      int l_previousIndex = 0; 
      int l_previousLength = 0; 
      //  The final MoveNext(), which returns false, takes 2 seconds. 
      while (l_matchEnumerator.MoveNext()) { 
       Match l_match = (Match) l_matchEnumerator.Current; 
       int l_start = l_previousIndex + l_previousLength; 
       int l_length = l_match.Index - l_start; 
       l_elements.Add(l_input1.Substring(l_start, l_length)); 

       l_previousIndex = l_match.Index; 
       l_previousLength = l_match.Length; 
      } 
      Console.WriteLine("List Composition Time: " + (DateTime.Now - l_listStart).TotalMilliseconds.ToString()); 

      string[] l_terms = l_elements.ToArray(); 

      Console.WriteLine(String.Join("\n", l_terms)); 

      Console.ReadKey(true); 

     } 
    } 
} 

WYJŚCIE
(To jest dokładnie to, o co mi chodzi.)

jeden
„dwa trzy "
cztery
pięć:" sześć siedem”
osiem
"dziewięć dziesięć"

Answer 1

Spróbuj zmienić regex następujące:

(?<=^((?>[^"]*)(["][^"]*["])?)*)\s+ 

Jedyną zmianą jest tutaj wstaw [^"]* do atomic group, co zapobiega występowaniu .

Uwaga: regex powyżej jest oczywiście nie używać C# regex składni ciąg, który jestem zaznajomiony z, ale myślę, że byłoby następujące:

@"(?<=^((?>[^""]*)([""][^""]*[""])?)*)\s+"; 

Dlaczego katastrofalne wycofywania następuje:
Po znalezieniu wszystkich ważnych wyników, następnym próbą jest miejsce wewnątrz ostatniej cytowanej sekcji. Lookbehind zakończy się niepowodzeniem, ponieważ przed spacją znajduje się nieparzysta liczba cudzysłowów.

W tym momencie regex wewnątrz lookbehind zacznie się cofać. Zakotwiczenie oznacza, że ​​zawsze zaczyna się od początku łańcucha, ale nadal może się cofać poprzez upuszczenie elementów od końca tego, co zostało dopasowane.Spójrzmy na regex wewnątrz lookbehind:

^([^"]*(["][^"]*["])?)* 

Ponieważ cytowane sekcje są opcjonalne, mogą zostać pominięte jako regex cofa. Dla każdego fragmentu cudzysłowów, które nie znajdują się w cytowanej sekcji, przed powrotem do tyłu każdy znak zostałby dopasowany jako część [^"]* na początku wyrażeń regularnych. Gdy zacznie się cofanie w tej sekcji, ostatnia postać zostanie usunięta z tego, co pasuje do [^"]* i zostanie pobrana przez zewnętrzne powtórzenie. W tym momencie staje się bardzo podobny do przykładu na powyższym katastroficznym łączu zwrotnym.