How can I make a loop faster?

Question

I have an array of values that represent points on a line chart:

$temperatures = [23, 24, null, '', 25, '', '', null];

I'm using PHP4, but I think it can be answered in any language.

Array contains only numbers, nulls and empty strings.

Numbers represent temperatures, nulls mean that the instruments weren't working and empty strings represent neither (instruments are working, just not measuring anything).

Points must (in most cases) be connected, since it's a line chart.

I have a variable $gap that corresponds to each point and tells whether this point is connected to the next point. If it is set to true, than the points are not connected (false otherwise). For example, $gap for temperatures[0] must be set to false, since the line is drawn between temperatures[0] and temperatures[1](they are both valid temperatures). $gap fortemperatures[1]andtemperatures[2]` must be true, since there is null following. And so on.

When there is null the $gap is absolutely true. For numbers and empty strings, it depends on: if a null follows, gap is true; if a number follows, gap is false. If empty string follows, we must check if afterwards comes null or number and apply the previous sentence accordingly. If there are just empty strings following, gap is true. Here is my code that is working too slow, but produce correct results:

$limit = count($temperatures);
for ($i = 0; $i <= limit; $i++) {
    $next_is_number = false;
    if (is_null($temperatures[i]) {
        $gap = true;
    } else {
        for ($y = $i + 1; $i <= limit; $i++) {
            if (is_null($temperatures[$y]) {
                break;
            } elsif (is_numeric($temperatures[$y]) {
                $next_is_number = true;
                break;
            }
        }

        if ($next_is_number) {
           $gap = false;
        } else {
           $gap = true;
        }
    }      
}

How can I speed it up?

Answer 1

Iterate through backwards, remembering the last valid value and putting that in when you see an empty string. Then it's O(n) worst case, not O(n^2).

Alternatively, you can work from $y - 1 to $x (or vice versa) after the inner loop, setting the values of your gaps array / outputting values, then skip past all the ones you've just done ($x = $y). This is also O(n).

Then, once you've got the algorithm as fast as you can, you can ditch PHP and write it in something like Rust or C. (I don't recall any true arrays in the language, so they're always going to be slow.)