3
\$\begingroup\$

I have to check a given amount of regular expressions, which are defining number ranges for dial plans, against an input number range. The target is to check and see, if any of the numbers in the range are free, or which regular expression matches for the number. Last situation is said to be an occupied number, otherwise if no regex matches, the number is defined as free.

I match every number from the input range against every regexp and generate some output code. The main problem is, that this sort of "brute force" causes huge load on server and for 50.000 numbers the default php timeout is thrown. Anyhow, this is in my eyes also too long to wait for. The output is not even the real problem (but could and will get optimized anyhow), but for now I need a more efficient way to match.

Here is my code:

$start_time = microtime(true);  // Startzeit


                $rangeStart = $_POST["search_numberrange_start"];
                $rangeEnd = $_POST["search_numberrange_end"];

                $this->applicationManager->sortAppsByNumber();
                $isdn_applications = $this->applicationManager->getISDNapps();
                $sip_applications = $this->applicationManager->getSIPapps();                

                $isdn_regexp = array();
                $sip_regexp = array();

                for($i = 0; $i < count($isdn_applications); $i++)
                    array_push($isdn_regexp, "/".$isdn_applications[$i]->getNumber()."/");

                for($i = 0; $i < count($sip_applications); $i++)
                    array_push($sip_regexp, "/".$sip_applications[$i]->getNumber()."/");

                $matched_sip = array();
                $matched_isdn = array();

                $number = $rangeStart;

                do {

                    $matched = false;
                    $code = $number;

                    if($this->numberRangeCheckType == "default" || $this->numberRangeCheckType == "isdn") {
                        for($i = 0; $i < count($isdn_regexp); $i++) {

                            if(preg_match($isdn_regexp[$i],$number)) {
                                $code = $code." <a href='#application_".$i."' class='applink'>".$isdn_applications[$i]->getName()."</a>";
                                $matched = true;
                            }
                        }
                    }

                    if(!$matched) {
                        $code = "<li class='free'>".$number." FREI</li>";
                        array_push($matched_isdn, array("code" => $code));
                    }
                    else {
                        $code = "<li class='occupied'>".$code."</li>";
                        array_push($matched_isdn, array("code" => $code));
                    }

                    $code = $number;
                    $matched = false;

                    if($this->numberRangeCheckType == "default" || $this->numberRangeCheckType == "sip") {
                        for($i = 0; $i < count($sip_regexp); $i++) {

                            if(preg_match($sip_regexp[$i],$number)) {
                                $code = $code." <a href='#application_".$i."' class='applink'>".$sip_applications[$i]->getName()."</a>";
                                $matched = true;
                            }
                        }
                    }

                    if(!$matched) {
                        $code = "<li class='free'>".$number." FREI</li>";
                        array_push($matched_sip, array("code" => $code));
                    }
                    else {
                        $code = "<li class='occupied'>".$code."</li>";
                        array_push($matched_sip, array("code" => $code));
                    }

                    $number++;
                }while($number < $rangeEnd);

                $end_time = microtime(true);
                $time = $end_time - $start_time;
                echo "<p>Seite generiert in ".round($time, 5)." Sekunden</p>";  

                /*switch($this->numberRangeCheckType) {
                    case "isdn":    echo "<p class='match_caption'>ISDN:</p>";
                                    $this->printMatchedEntry($matched_isdn);
                                    break;

                    case "sip":     echo "<p class='match_caption'>SIP:</p>";
                                    $this->printMatchedEntry($matched_sip);
                                    break;

                    case "default": echo "<p class='match_caption'>ISDN:</p>";
                                    $this->printMatchedEntry($matched_isdn);
                                    echo "<p class='match_caption'>SIP:</p>";
                                    $this->printMatchedEntry($matched_sip);
                                    break;
                    }   */      


            $end_time = microtime(true);
            $time = $end_time - $start_time;

$isdn_applications are objects that hold a name and number for an application. (same for sip_) $isdn_regexp hold the regexp that are built from the numbers. (note: numbers itself are stored and hold regexp, only / / is missing for preg_match which is there attached).

Feel free to ask questions if something is not clearly enough and thanks for taking time!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Review! It's quite hard to see for ourselves what's taking a lot of time. How many regexes? How large can the range be? Is it possible to define a regex that would apply to search_numberrange_start or search_numberrange_end and thus avoiding the outer loop? Simple testable code that exhibits the problem would be a good way to get help. \$\endgroup\$ Sep 17, 2012 at 8:35

1 Answer 1

1
\$\begingroup\$

Well, REGEX is actually your first problem. A REGEX function is typically slower than its string/int counterparts. So, if you can do something with a normal function, or a few normal functions, it is normally preferable to REGEX. This is why so many people say REGEX is bad. Its not bad, just misused and misunderstood. REGEX should only be used when you can't find a normal function to do something for you, or when the normal function(s) required would just be too costly, and is usually justified by some sort of profiling attempt. However, maybe switching from REGEX isn't plausible in this situation. It appears that you might be working inside someone else's framework, at least with the procedural code mingled with OOP, I assume this is the case.

Now, REGEX isn't your only problem. There are sections in your code that are redundant and are causing some inefficiency as well. For instance, your two for loops. First off, let me say that you should keep using braces on one line statements to enhance legibility and decrease the possibility of mistakes. That isn't effecting your program's efficiency, but it might effect yours. Now, the first inefficiency is that count. For and while loops, unlike foreach loops, call functions passed in as parameters on each iteration. So you are essentially asking for a new count every time the loop restarts. While this inefficiency is usually overlooked because of its triviality, I point it out because your program is going to need all the help it can get. And its just good practice anyways. The second inefficiency is the need for two loops at all. If you get the count of both arrays, then compare them to find the larger, then you can use that larger number to loop from and use if statements to ensure that you don't go over the maximum allowed for the smaller. The last inefficiency, at least here, would be that array_push() function. Why use a function that can more easily and legibly be accomplished without one?

for( $i = 0; $i < $isdnCount || $i < sipCount; $i++ ) {
    if( $i < $isdnCount ) {
        $isdn_regexp[] = "/{$isdn_applications[ $i ]->getNumber()}/";
    }
    if( $i < $sipCount ) {
        $sip_regexp[] = "/{$sip_applications[ $i ]->getNumber()}/";
    }
}

Not to say the above is 100% efficient either. You should profile that and compare it, maybe all those comparisons made it just as bad or worse. Maybe moving the of || statement out of the for loop would make it better, after all, it is being queried on each iteration.

Why did you define $rangeStart then assign it to $number without ever using it? Anyways, that's a micro-inefficiency, this do/while loop is the biggest concern. There is a principle that will really help you here and in your future endeavors: "Don't Repeat Yourself" (DRY). As the name implies, if you do something more than once, find some way of making that task repeatable without explicitly having to rewrite it. Typically you start with a loop. If the loop doesn't fix it for you, then you move on to functions, and finally, if functions don't fix it for you, then you move on to classes. Eventually you will be able to look at a problem and intuitively know what kind of solution it requires. Besides making your script more light weight and efficient, it also makes it easier to read, which is a big issue with your current code. Now, the first repetition I see actually makes that loop I showed you above redundant. Why loop over the source to extract a new array, if you are just going to loop over the new array to do something with the previous source? Do all of your looping at once, whenever possible.

Speaking of DRY, your $matched statements can use it too. No need to tell it to push onto the end of the array twice, you've already set up your statements to pass it the same source, just move the push out of the statements so you'll only have to call it once.

if( ! $matched ) {
    $code = '<li class="free">' . $number . ' FREI</li>';
} else {
    $code = '<li class="occupied">' . $code . '</li>';
}

$matched_isdn[] = array( "code" => $code );

As above, it appears that these for loops are redundant. You could probably combine them, similarly to the one showed above. I won't write this one out, as you can extract everything you need from that previous example and apply it here.

That appears to be it for your inefficiencies. If the program is still running too slow, it is probably because you have a double loop and that internal loop is probably rather large. I can't think of any way around this, however. You have to loop over these arrays for each number. The only "fix" would be to limit the range of numbers you use on each run.

Here are some suggestions for your code

Be consistent with your naming. Your first variable uses under_score, then you switch to camelCase, then back and forth throughout the application. Choose one style, at least for the same datatype. I have seen people switch between them for functions and variables, and that is perfectly fine, but all of your variables should be the same, and all of your functions should be the same. If this means shifting your style to resemble the environment you are coding in, then so be it. Better consistent than a mess.

Validate and sanitize any user input, unless the scope of this program is purely internal and you trust all input. But even then, people make mistakes, so basic validation wouldn't hurt.

It appears that you are working with classes and OOP. In order to be effective with it, you should brush up on key OOP principles, such as the DRY principle I mentioned. There's also SOLID. Google those and you should get a whole bunch more to work with. You don't have to understand all of them right away. Just reading it so that you are aware of it is enough at first. Then, subconsciously you will be able to start looking at your code differently and can then start trying to apply these principles.

I hope this helps!

\$\endgroup\$
1
  • \$\begingroup\$ with some points you have mentioned and asynchronous processing I was able to boost the computation of a range with 50.000 numbers down to 6 seconds. Though your answer was general, I will set it as accepted because you really helped me! \$\endgroup\$
    – Stefan
    Aug 30, 2012 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.