Most optimized way to get minimum strpos from multiple needles

Question

function min_strpos_array($haystack, $needles) {
    $min = null;
    for ($i = 0; $i < count($needles); $i++) {
        $strpos = strpos($haystack, $needles[$i]);
        if ($strpos !== FALSE) {
            $min = $strpos;
            for ($i = $i + 1; $i < count($needles); $i++) {
                $strpos = strpos($haystack, $needles[$i]);
                if ($strpos !== FALSE) {
                    $min = $min < $strpos ? $min : $strpos;
                }
            }
        }
    }
    return $min;
}

echo min_strpos_array('hello#,?', array('#', '?')); //5

Answer 1

Well, any time you have nested for loops, you should cringe a little because it means you're running in O(n^2) time. Sometimes it's unavoidable, but often you can do something to bring it down significantly. Edit: this algorithm is actually O(n).

In your case, you can reduce your algorithm to O(n), which is a huge performance boost.

Here are your new steps:

Loop through each needle
    Get the position of the needle in the haystack
    If the position is less than our current minimum:
        Set the minimum to the position of the needle

Basically, we find the first minimum and then overwrite it as each new minimum is found.

Here is my version of your code:

function min_strpos_array($haystack, $needles){
    $length = count($needles);
    $min = strlen($haystack) + 1;
    for($i = 0; $i < $length; $i++){
        $strpos = strpos($haystack, $needles[$i]);
        if ($strpos !== FALSE){
            if($strpos < $min){
                $min = $strpos;
            }
        }
    }
    return $min;
}

echo min_strpos_array('hello#,?', array('#', '?')); //5

Outside of the algorithm, I made a few other changes.

for ($i; $i < count($needles); $i++) became for ($i = 0; $i < $length; $i++). When you have a function in a for loop, it gets called every iteration, which is unnecessary when the value doesn't change. Just get the number of needles outside the loop and reference that. You could also use a foreach loop, but I'm not familiar enough with PHP to definitively say that it's better.

$min = null; became $min = strlen($haystack) + 1;. This ensures that if our needle exists in the haystack, we can compare the position with our minimum. It also has the side effect of returning strlen($haystack) + 1 if none of the needles are found in the haystack, which may or may not be desirable. If you don't like that, just add an if statement before you return.

You really don't need to nest your if statements like you did either, but I decided to leave those in in case you chose to so intentionally.

Two important things to take away from this:

1. Watch out for nested for loops. Pretend they're screaming at you to find a better algorithm.
2. Don't call functions in the argument of a for loop unless you need to get a value that might change during the loop.