Regex Performance
In Abschnitt 4.3.2 wird diskutiert, wie die Wahl einer Implementationsmethode für eine Regex-Engine sich auf die Performance auswirkt. Auf einem deterministischen endlichen Automaten aufbauende Engines haben immer Laufzeit O(n), während sich für nicht deterministische endliche Automaten reguläre Ausdrücke konstruieren lassen, die zu exponentiell wachsender Laufzeit führen.
Der reguläre Ausdruck
bestehend aus n optionalen a und n obligatorischen a akzeptiert das Wort an, nicht deterministische Regex-Engines brauchen typischerweise exponentielle Zeit, um dies festzustellen.
Anklicken der Buttons zeigt Codebeispiele in verschiedenen Sprachen, mit denen man messen kann, ob die getestete Regex-Engine DEAs oder NEAs für die Implementation verwendet. Der vollständige Sourcecode kann als regex-1.0.tar.gz heruntergeladen werden.