[regex] Snelheid bij grote strings dramatisch
Heeft iemand een verklaring hiervoor? Ik heb een testbestand gebouwd en een grafiek opgebouwd in excel. Tussen de 600 en 1600 tekens gaat de snelheid van regex dramatisch omlaag, echt met factoren van 10 tot 100x trager.
Ik vind dit nogal opmerkelijk. Is hier een verklaring voor?
Om te checken of een bepaalde string in een andere string voorkomt, zijn functies als strpost() of strstr() waarschijnlijk wel sneller zijn...
Hierbij de link: http://phphulp.storeman.nl/regex.jpg
Vanaf ongeveerl 1300 tekens/bytes begint het behoorlijk toe te nemen
Gewijzigd op 01/01/1970 01:00:00 door storeman storeman
zon regulare expressie is meestal toch een combinatie van verschillende patronen waarbij je eigenlijk iets krijgt van:
zijn de eerste 3 tekens letters of cijfers, zoja.. staat er dan een punt, en tussen het volgende punt bevinden zich dan ook nog letters of cijfers en eindigt na deze punt voor de slash het domein in een 2 a 4 tekens extensie.
Terwijl je met strpos kunt zoeken naar :// als begin, en eindigt te zoeken met bijvoorbeel slash of een aanhalingsteken om het zelfde te bereiken.
Soms moet je bepaalde dingen afwegen wat handiger is, ook al wil je het soms heel mooi, strak en deftig doen met zo min mogelijke code.
Die twee gaan over het algemeen niet altijd even goed samen zoals hier ook maar weer blijkt. Een regex is functioneel maar beduidend trager, terwijl je met strpos() enkel de locatie van 1 bepaalde string kunt bepalen maar welke daarentegen wel veel sneller is.
Weeg af welke functionaliteit je nodig hebt en afhankelijk daarvan kies je de te gebruiken functie. Overigens praten we hier wel weer over echte micro-optimalisatie. Wat is nou het verschil tussen 0,005 en 0,0005 seconden. Ok, het eens is 10x zo lang, maar in de praktijk zul je daar echt niets van merken...
Er zijn waarschijnlijk eerder andere functies/constructies die veel langer duren en waar optimalisatie dus eerder gewenst is. Een goed voorbeeld is bijvoorbeeld het aanbrengen van de juiste indexen in een database. Een snelheidsverschil van bijv. 40s naar een krappe 2s noem ik de moeite waard...
voor mij is dit momenteel wel van belang, gezien het grote aantal localisaties dat ik moet doen in zeer grote tekstbestanden (>1MB). Terwijl onderstaande functie er met 0,02s mee klaar is, doet een eenvoudige regex met dezelfde functionaliteit, er ruim 4.5 seconde over. Dit zijn toch wel winsten waar je wat mee kan (okee, wordt 1 maal 500x geloopt, maar bij grote tekstbestanden is dat wel realistisch).
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
<?
/*
StaticString::_MatchByTagTheOldWay(
$strText, // Text to search in
$strTagOpen, // The start string of the match, is used in regex, thus think about escaping special chars
$strTagClose, // The end string of the match, is used in regex, thus think about escaping special chars
$arrMatch, // Reference array
$iOffset, // Charactor to start at in the strText
$iLimit // Upper limit of matches to do
);
*/
public static function _MatchByTagTheOldWay(
$strText, // Text to search in
$strTagOpen, // The start string of the match, is used in regex, thus think about escaping special chars
$strTagClose, // The end string of the match, is used in regex, thus think about escaping special chars
&$arrMatch, // Reference array
$iOffset = 0, // Charactor to start at in the strText
$iLimit = null // Upper limit of matches to do
){
$iCount = 0;
$iStartPos = 0;
$iCurrentPos = $iOffset;
// Determine the length of both tags
$iTagOpenLength = strlen($strTagOpen);
$iTagCloseLength = strlen($strTagClose);
// Walk through the text, using the substr function, to find the first occurance
// Save the first occurance position in the iStartpos
// If the currentposition is outside the textrange, the loop will quit
while ($iCurrentPos < strlen($strText)
&& ($iStartPos = strpos($strText, $strTagOpen, $iCurrentPos)) !== false
&& ($iLimit == null || $iCount < $iLimit) )
{
// Update the current pos, set it to the startposition plus the length of the startstring
$iCurrentPos = $iStartPos + $iTagOpenLength;
// Try to match the endstring, if not successful, match it to the end of the text
$iEndPos = strpos($strText, $strTagClose, $iCurrentPos);
if ($iEndPos === false) $iEndPos = strlen($strText);
// Update the current position
$iCurrentPos = $iEndPos + $iTagCloseLength;
$arrMatch[] = array($iStartPos, // Begin pos
$iCurrentPos, // Last pos
$iCurrentPos - $iStartPos, // Total length
$iCurrentPos - $iStartPos - $iTagOpenLength - $iTagCloseLength // Internal length
, substr($strText, $iStartPos+$iTagOpenLength, $iCurrentPos-$iStartPos-$iTagOpenLength-$iTagCloseLength) // The text
);
$iCount++;
}
if($iCount){
return $iCount;
}
}
?>
/*
StaticString::_MatchByTagTheOldWay(
$strText, // Text to search in
$strTagOpen, // The start string of the match, is used in regex, thus think about escaping special chars
$strTagClose, // The end string of the match, is used in regex, thus think about escaping special chars
$arrMatch, // Reference array
$iOffset, // Charactor to start at in the strText
$iLimit // Upper limit of matches to do
);
*/
public static function _MatchByTagTheOldWay(
$strText, // Text to search in
$strTagOpen, // The start string of the match, is used in regex, thus think about escaping special chars
$strTagClose, // The end string of the match, is used in regex, thus think about escaping special chars
&$arrMatch, // Reference array
$iOffset = 0, // Charactor to start at in the strText
$iLimit = null // Upper limit of matches to do
){
$iCount = 0;
$iStartPos = 0;
$iCurrentPos = $iOffset;
// Determine the length of both tags
$iTagOpenLength = strlen($strTagOpen);
$iTagCloseLength = strlen($strTagClose);
// Walk through the text, using the substr function, to find the first occurance
// Save the first occurance position in the iStartpos
// If the currentposition is outside the textrange, the loop will quit
while ($iCurrentPos < strlen($strText)
&& ($iStartPos = strpos($strText, $strTagOpen, $iCurrentPos)) !== false
&& ($iLimit == null || $iCount < $iLimit) )
{
// Update the current pos, set it to the startposition plus the length of the startstring
$iCurrentPos = $iStartPos + $iTagOpenLength;
// Try to match the endstring, if not successful, match it to the end of the text
$iEndPos = strpos($strText, $strTagClose, $iCurrentPos);
if ($iEndPos === false) $iEndPos = strlen($strText);
// Update the current position
$iCurrentPos = $iEndPos + $iTagCloseLength;
$arrMatch[] = array($iStartPos, // Begin pos
$iCurrentPos, // Last pos
$iCurrentPos - $iStartPos, // Total length
$iCurrentPos - $iStartPos - $iTagOpenLength - $iTagCloseLength // Internal length
, substr($strText, $iStartPos+$iTagOpenLength, $iCurrentPos-$iStartPos-$iTagOpenLength-$iTagCloseLength) // The text
);
$iCount++;
}
if($iCount){
return $iCount;
}
}
?>
Gewijzigd op 01/01/1970 01:00:00 door storeman storeman
Vanuit dit oogpunt zou het echter wel beter kunnen zijn om een functie te schrijven die net doet wat hij moet doen, dan dat je een functie gebruikt waarvan een groot deel van de functionaliteit overbodig is.
Puur uit nieuwsgierigheid: wat zijn dat voorbestanden die je moet doorzoeken?
Ik blijf het vreemd vinden dat er bij ongeveer 1300 byte een grens ligt welke de snelheid van de regex dramatisch doet afnemen. Terwijl daaronder de regex sneller is (ongeveer 50%).
Ohja, ik gebruik dat soort functies ook om xmlbestanden te maken en te lezen.
Een voorbeeld met 'backtracken', regex die elke mogelijke oplossing uitprobeert tot hij er een gevonden heeft is te vinden op de onderstaande url. Ik zou aan blanche willen toevoegen dat een efficient geschreven regex niet zoveel langer zou moeten zijn als een strpos. Vaak is de oplossing te vinden in het optimaliseren van de regex, of het op te splitsen in twee regexes.
http://blog.stevenlevithan.com/archives/greedy-lazy-performance
Kortom: plaats ook je regex even, dat is van behoorlijk belang.
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
<?
/**
* Returns the start and endpostion of each matched set, which is mached
* by an openingstring and closing string.
*
* Array(
* Array(iStartpos, iEndPos, $iLengthWithTags, $iLengthWithoutTags, $strMatchWithoutTags),
* Array(iStartpos, iEndpos, $iLengthWithTags, $iLengthWithoutTags, $strMatchWithoutTags)
* )
*
* @param string $strText
* @param string $strTagOpen
* @param string $strTagClose
* @param reference array $arrMatch
* @param int $iOffset
* @param int $iLimit
* @return int number of matches or false in case of error
*/
public static function MatchByTag(
$strText, // Text to search in
$strTagOpen, // The start string of the match, is used in regex, thus think about escaping special chars
$strTagClose, // The end string of the match, is used in regex, thus think about escaping special chars
&$arrMatch, // Reference array
$iOffset = 0, // Charactor to start at in the strText
$iLimit = null // Upper limit of matches to do
){
// Array that is used to put regex results in
$arrWorkMatch = array();
// Save the status, true if everyting is fine
$blnStatus = true;
// Build the regular expression
if(floatval(phpversion()) < 5){
$strMatch = '/'.StaticString::RegexEscape($strTagOpen).'(.*?)'.StaticString::RegexEscape($strTagClose).'/s';
}else{
$strMatch = '/'.self::RegexEscape($strTagOpen).'(.*?)'.StaticString::RegexEscape($strTagClose).'/s';
}
$strMatch = '/'.$strTagOpen.'(.*?)'.$strTagClose.'/s';
//If the limit of matches is 1
if(!is_null($iLimit) && $iLimit == 1){
// Use a single preg_match
$arrSubWorkMatch = array();
$blnStatus = preg_match($strMatch, $strText, $arrSubWorkMatch, PREG_OFFSET_CAPTURE, $iOffset);
if($blnStatus !== false && isset($arrSubWorkMatch[0])){
// Because preg_match has not the same array structure as preg_match_all, reform it
$arrWorkMatch = array();
$arrWorkMatch[0] = array();
$arrWorkMatch[1] = array();
$arrWorkMatch[0][0] = $arrSubWorkMatch[0];
$arrWorkMatch[1][0] = $arrSubWorkMatch[1];
}
} else {
// Otherwise search for matches in the string using regex
$blnStatus = preg_match_all($strMatch, $strText, $arrWorkMatch, PREG_OFFSET_CAPTURE, $iOffset);
}
$iCount = 0;
if($blnStatus !== false && $blnStatus>0 && isset($arrWorkMatch[1])){
// Set the maximum number of matches to return
if($iLimit > $blnStatus || is_null($iLimit)){
$iCount = $blnStatus;
}else{
$iCount = $iLimit;
}
$iOpentagLength = strlen($strTagOpen);
$iClosetagLength = strlen($strTagClose);
// Array(iStartpos, iEndPos, $iLengthWithTags, $iLengthWithoutTags, $strMatchWithoutTags),
for($i=0; $i<$iCount; $i++){
$iStringLength = strlen($arrWorkMatch[1][$i][0]);
$arrMatch[] = array($arrWorkMatch[1][$i][1] - $iOpentagLength, // Begin pos
$arrWorkMatch[1][$i][1] + $iClosetagLength + $iStringLength, // Last pos
$iOpentagLength + $iClosetagLength + $iStringLength, // Total length
$iStringLength // Internal length
, $arrWorkMatch[1][$i][0] // The text
);
//$arrMatch[$i][0] = $arrWorkMatch[1][$i][1] - $iOpentagLength;
//$arrMatch[$i][1] = $arrWorkMatch[1][$i][1] + $iClosetagLength + $iStringLength;
//$arrMatch[$i][2] = $iOpentagLength + $iClosetagLength + $iStringLength;
//$arrMatch[$i][3] = $iStringLength;
//$arrMatch[$i][4] = $arrWorkMatch[1][$i][0];
}
}
// Return false if an error occured
if($blnStatus === false){
return false;
}else{
// Otherwise return the number of matches found
return $iCount;
}
}
?>
/**
* Returns the start and endpostion of each matched set, which is mached
* by an openingstring and closing string.
*
* Array(
* Array(iStartpos, iEndPos, $iLengthWithTags, $iLengthWithoutTags, $strMatchWithoutTags),
* Array(iStartpos, iEndpos, $iLengthWithTags, $iLengthWithoutTags, $strMatchWithoutTags)
* )
*
* @param string $strText
* @param string $strTagOpen
* @param string $strTagClose
* @param reference array $arrMatch
* @param int $iOffset
* @param int $iLimit
* @return int number of matches or false in case of error
*/
public static function MatchByTag(
$strText, // Text to search in
$strTagOpen, // The start string of the match, is used in regex, thus think about escaping special chars
$strTagClose, // The end string of the match, is used in regex, thus think about escaping special chars
&$arrMatch, // Reference array
$iOffset = 0, // Charactor to start at in the strText
$iLimit = null // Upper limit of matches to do
){
// Array that is used to put regex results in
$arrWorkMatch = array();
// Save the status, true if everyting is fine
$blnStatus = true;
// Build the regular expression
if(floatval(phpversion()) < 5){
$strMatch = '/'.StaticString::RegexEscape($strTagOpen).'(.*?)'.StaticString::RegexEscape($strTagClose).'/s';
}else{
$strMatch = '/'.self::RegexEscape($strTagOpen).'(.*?)'.StaticString::RegexEscape($strTagClose).'/s';
}
$strMatch = '/'.$strTagOpen.'(.*?)'.$strTagClose.'/s';
//If the limit of matches is 1
if(!is_null($iLimit) && $iLimit == 1){
// Use a single preg_match
$arrSubWorkMatch = array();
$blnStatus = preg_match($strMatch, $strText, $arrSubWorkMatch, PREG_OFFSET_CAPTURE, $iOffset);
if($blnStatus !== false && isset($arrSubWorkMatch[0])){
// Because preg_match has not the same array structure as preg_match_all, reform it
$arrWorkMatch = array();
$arrWorkMatch[0] = array();
$arrWorkMatch[1] = array();
$arrWorkMatch[0][0] = $arrSubWorkMatch[0];
$arrWorkMatch[1][0] = $arrSubWorkMatch[1];
}
} else {
// Otherwise search for matches in the string using regex
$blnStatus = preg_match_all($strMatch, $strText, $arrWorkMatch, PREG_OFFSET_CAPTURE, $iOffset);
}
$iCount = 0;
if($blnStatus !== false && $blnStatus>0 && isset($arrWorkMatch[1])){
// Set the maximum number of matches to return
if($iLimit > $blnStatus || is_null($iLimit)){
$iCount = $blnStatus;
}else{
$iCount = $iLimit;
}
$iOpentagLength = strlen($strTagOpen);
$iClosetagLength = strlen($strTagClose);
// Array(iStartpos, iEndPos, $iLengthWithTags, $iLengthWithoutTags, $strMatchWithoutTags),
for($i=0; $i<$iCount; $i++){
$iStringLength = strlen($arrWorkMatch[1][$i][0]);
$arrMatch[] = array($arrWorkMatch[1][$i][1] - $iOpentagLength, // Begin pos
$arrWorkMatch[1][$i][1] + $iClosetagLength + $iStringLength, // Last pos
$iOpentagLength + $iClosetagLength + $iStringLength, // Total length
$iStringLength // Internal length
, $arrWorkMatch[1][$i][0] // The text
);
//$arrMatch[$i][0] = $arrWorkMatch[1][$i][1] - $iOpentagLength;
//$arrMatch[$i][1] = $arrWorkMatch[1][$i][1] + $iClosetagLength + $iStringLength;
//$arrMatch[$i][2] = $iOpentagLength + $iClosetagLength + $iStringLength;
//$arrMatch[$i][3] = $iStringLength;
//$arrMatch[$i][4] = $arrWorkMatch[1][$i][0];
}
}
// Return false if an error occured
if($blnStatus === false){
return false;
}else{
// Otherwise return the number of matches found
return $iCount;
}
}
?>
Ik heb al eea uitgezocht en veel dingen geescaped, de tijd gaat echt in de regex zitten, dus niet in andere zaken.