[regex] Snelheid bij grote strings dramatisch

Overzicht Reageren

Sponsored by: Vacatures door Monsterboard

Storeman storeman

storeman storeman

02/02/2008 22:04:00
Quote Anchor link
Ik was even het eea aan het testen met regex vs strpos en substr om te filteren vanuit een string. Mijn eerdere conclusies waren dat regex ongeveer 2x zo snel was als strpos (en aanhangsels), echter bij een groot bestand deed regex (preg_match) er 4s over terwijl strpos in 0,017s klaar was.

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?
 
PHP hulp

PHP hulp

06/08/2020 00:58:37
 
Joren de Wit

Joren de Wit

02/02/2008 22:11:00
Quote Anchor link
Zal waarschijnlijk komen omdat de gehele tekst aan de hand van een reguliere expressie getest moet worden. Ik gok dat dat nou eenmaal niet de meest efficiente manier is.

Om te checken of een bepaalde string in een andere string voorkomt, zijn functies als strpost() of strstr() waarschijnlijk wel sneller zijn...
 
Storeman storeman

storeman storeman

02/02/2008 22:16:00
Quote Anchor link
Ik gebruik het wel om te matchen op tags. Dus een string die begint met 'de' en eindigt met '.'. Dus er is wel iets meer nodig dan één strpos, namelijk een countertje, substr, strlen ed. Ik zal het grafiekje even online zetten.

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
 
Danny Roelofs

Danny Roelofs

03/02/2008 01:21:00
Quote Anchor link
Ja ik verwacht ook niet dat dit de efficiënte manier, alles wat ik behandel met regulare expressies is meestal toch regel voor regel werk, of van te voren ingekort waarbij overbodige data dan al is verwijdert.

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.
 
Joren de Wit

Joren de Wit

03/02/2008 10:29:00
Quote Anchor link
Snelheid vs. Functionaliteit

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...
 
Storeman storeman

storeman storeman

03/02/2008 11:51:00
Quote Anchor link
@blanche

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)
PHP script in nieuw venster Selecteer het PHP script
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
<?
/*
    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
 
Joren de Wit

Joren de Wit

03/02/2008 12:05:00
Quote Anchor link
Wellicht dat deze functie inderdaad sneller zal zijn dan dat je een regex gebruikt. Maar wederom gaat hier mijn verhaal over snelheid vs. functionaliteit wel op. Deze functie geeft je immers niet de functionalisteit die je met een reguliere expressie hebt.

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?
 
Storeman storeman

storeman storeman

03/02/2008 18:16:00
Quote Anchor link
Een aantal phpbestanden moet ik doorzoeken, en ja, 1MB is veel, maar ik heb ervoor gekozen om één library file te gebruiken in mijn systeem. Deze wil ik strippen en onleesbaar maken. Daarnaast converteert ie m ook nog compatibel naar php4, dus dat is nogal wat, al met al.

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.
 
Arend a

Arend a

04/02/2008 20:48:00
Quote Anchor link
Het hangt zeer af van hoe je je regex weergeeft. Met name (.*) tags en of je ze greedy of non greedy gebruikt kan veel uitmaken. In dit geval lijkt er een semi lineair verband te zijn, en dus dat met het groeien te tekst regex evenredig meer combinaties uitprobeert.

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.
 
Storeman storeman

storeman storeman

04/02/2008 22:22:00
Quote Anchor link
Bij deze:

Code (php)
PHP script in nieuw venster Selecteer het PHP script
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
<?
/**
     * 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.
 
Arend a

Arend a

04/02/2008 22:24:00
Quote Anchor link
Kan je ook een klein voorbeeldje geven van wat je probeert te matchen? Dat maakt de code lezen met regex vele malen makkelijker :)
 
Sir Psycho Sexy

Sir Psycho Sexy

05/02/2008 00:02:00
Quote Anchor link
Ik snap het ook niet.
 
Arend a

Arend a

05/02/2008 11:41:00
Quote Anchor link
Ik kan overigens je resultaten niet nabootsen, dus als je ven je tekst plaatst waar het wel mee gaat en waar het niet mee gaat, kan ik je misscihen helpen.
 



Overzicht Reageren

 
 

Om de gebruiksvriendelijkheid van onze website en diensten te optimaliseren maken wij gebruik van cookies. Deze cookies gebruiken wij voor functionaliteiten, analytische gegevens en marketing doeleinden. U vindt meer informatie in onze privacy statement.