php-resource



Zurück   PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr > Entwicklung > PHP Developer Forum
 

Login

 
eingeloggt bleiben
star Jetzt registrieren   star Passwort vergessen
 

 

 


PHP Developer Forum Hier habt ihr die Möglichkeit, eure Skriptprobleme mit anderen Anwendern zu diskutieren. Seid so fair und beantwortet auch Fragen von anderen Anwendern. Dieses Forum ist sowohl für ANFÄNGER als auch für PHP-Profis! Fragen zu Laravel, YII oder anderen PHP-Frameworks.

Antwort
 
LinkBack Themen-Optionen Thema bewerten
  #16 (permalink)  
Alt 27-05-2008, 15:59
PHP-Desaster
 PHP Expert
Links : Onlinestatus : PHP-Desaster ist offline
Registriert seit: Mar 2006
Beiträge: 3.105
PHP-Desaster befindet sich auf einem aufstrebenden Ast
Standard

Zitat:
Ich hoffe der eine oder andere fands interessant.
Super erklärt, vielen Dank für den kleinen Einblick in die Interna der Regex-Engine
Mit Zitat antworten
  #17 (permalink)  
Alt 27-05-2008, 16:32
Benutzerbild von onemorenerd onemorenerd
  Moderator
Links : Onlinestatus : onemorenerd ist offline
Registriert seit: Mar 2005
Ort: Berlin
Beiträge: 9.471
onemorenerd wird schon bald berühmt werdenonemorenerd wird schon bald berühmt werden
Standard

Bei deinem Beispiel gab es einen Mismatch für den letzten Slash im Pattern.
Das Backtracking ist aber linear, es geht Zeichen für Zeichen zurück: /foo/bar, /foo/ba, /foo/b, /foo/. Deswegen eignet sich dein Beispiel nicht für Performancetests.

Der Performanceeinbruch zeigt sich, wenn in den Backtracking-Schritten noch weitere Expansionen getestet werden müssen. Ein klassisches Beispiel hierfür ist die beliebige Wiederholung eines Musters, das über mehrere Pfade gematcht werden kann.

((/foo)+(/foo)+)+/bar ist so ein "schlechtes" Pattern.
Um es übersichtlich zu halten, vereinfache ich es mal zu x+x+y.

Jeder sieht sofort, dass es äquivalent zu x{2,}y ist. Aber x{2,}y ist ein "gutes" Pattern. Angewendet auf xxy matcht es so lange x'e bis es nicht mehr geht, dann ein y und alles ist gut. 4 Zeichenvergleiche genügen also.

Das Pattern x+x+y beginnt genau so. Anfangs wird x+ auf xx expandiert. Das ist die Greedy-Eigenschaft.
Nun kommt im String ein y, aber das Pattern verlangt nach x+. Backtracking, einen Schritt zurück.
Jetzt matcht x+ mit x und das zweite x+ kann ein x matchen.
Zum Schluß noch das y.
Insgesamt 5 Zeichenvergleiche, also schon einer mehr als bei dem "guten" Pattern.

Natürlich ist ein Zeichenvergleich mehr kein Drama. Aber jetzt nehmen wir mal einen String, der nicht matcht: xxx.
Sehr kurz, aber mit viel Potential! Die Regex-Engine muss alle Expansionen der Wiederholungsgruppen durchprobieren. Es gibt zwei davon und wenn ich mich nicht verzählt habe, sind dafür 6 Zeichenvergleiche nötig. Das "gute" Pattern hätte wieder nur 4 gebraucht.

Jetzt nehmen wir mal xxxx, also ein x mehr. Für x+x+ gibt es nun schon 3 mögliche Expansionen und es sind 10 Zeichenvergleiche nötig.

Wie man sieht, steigt die Zahl der Backtracking-Schritte und Zeichenvergleiche gleichermaßen an, wenn man die Anzahl der x'e erhöht. Und in jedem Backtracking-Schritt muss wieder expandiert werden und darin wieder Backtracking und darin wieder Expansion ...
Die Performance geht exponentiell in den Keller!

Geändert von onemorenerd (27-05-2008 um 16:35 Uhr)
Mit Zitat antworten
  #18 (permalink)  
Alt 27-05-2008, 23:18
Griecherus
 PHP Senior
Links : Onlinestatus : Griecherus ist offline
Registriert seit: May 2005
Ort: Berlin
Beiträge: 1.036
Griecherus ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Ah, OK. Hatte jetzt erst die Gelegenheit, mir das mal genauer durchzulesen. Danke für das interessante Beispiel

Grüße
Mit Zitat antworten
  #19 (permalink)  
Alt 02-06-2008, 09:14
frank7l7
 Registrierter Benutzer
Links : Onlinestatus : frank7l7 ist offline
Registriert seit: Aug 2003
Beiträge: 810
frank7l7 ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Top, ... super erklärung. das sollte man in das php manual posten!
Mit Zitat antworten
Antwort

Lesezeichen


Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
 

Themen-Optionen
Thema bewerten
Thema bewerten:

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are an


PHP News

Die RIGID-FLEX-Technologie
Die RIGID-FLEX-TechnologieDie sogenannte "Flexible Elektronik" , oftmals auch als "Flexible Schaltungen" bezeichnet, ist eine zeitgemäße Technologie zum Montieren von elektronischen Schaltungen.

06.12.2018 | Berni

ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlicht
ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlichtDie bekannte Marktplatzsoftware ebiz-trader ist in der Version 7.5.0 veröffentlicht worden.

28.05.2018 | Berni


 

Aktuelle PHP Scripte

WeltExplorer v1.0

WeltExplorer v1.0 ist ein Dateimanager zum Browsen und Operieren im Dateisystem. Bei installiertem cURL können Ordner und Dateien zu entfernten FTP-Servern hochgeladen bzw. von diesen heruntergeladen werden, etwa zum Erstellen von Backups oder Mirrorsites

06.02.2019 weltvolk | Kategorie: PHP/ File
PG Job Site Pro

> Job Site Pro - web-basiertes Programm, auf PHP/MySQL für Erstellung der funktionellen Job Board Site gebaut. Das hat erweitertes Management-System für Arbeitssuchenden und Arbeitgeber und kann für bestimmte Länder, Regionen oder einfach generelle Job Si

05.02.2019 submit@ | Kategorie: PHP/ Management
ModuleStudio ansehen ModuleStudio

Modellgetriebene Entwicklung von Erweiterungen für das Open Source Framework Zikula.

15.01.2019 Guite | Kategorie: PHP ENTWICKLUNGSUMGEBUNG
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 07:57 Uhr.