如何使循环更快？

Question

我有一个值数组，代表折线图上的点：

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

我正在使用 PHP4，但我认为它可以用任何语言回答。

数组仅包含数字、空值和空字符串。

数字表示温度，空值表示仪器不工作，空字符串表示两者都没有（仪器正在工作，只是不测量任何东西）。

点必须（在大多数情况下）连接，因为它是一个折线图。

我有一个$gap对应于每个点的变量，并告诉这个点是否连接到下一个点。如果设置为true，则点不连接（false否则）。例如，temperatures[0]必须将$gap for设置为false，因为线是在temperatures[0]温度 [1](they are both valid temperatures). $gap for温度 [1]and温度 [2]`之间绘制的，因此必须为真，因为后面有空值。等等。

当有 null 时， $gap 是绝对的true。对于数字和空字符串，它取决于：如果后面是空值，则间隙为真；如果后面跟着一个数字，gap 是假的。如果后面跟着空字符串，我们必须检查之后是否出现 null 或 number 并相应地应用前一句。如果后面只有空字符串，gap 为真。这是我的代码运行速度太慢，但产生了正确的结果：

$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;

        }

    }      

}

我怎样才能加快速度？

Answer 1

您的代码会检查折线图中的某处是否存在间隙。因此，一旦发现间隙，就没有理由在外部 for 循环中继续。考虑一个包含 1000 个值的图表，如果前两个值之间存在差距，则继续检查其他 998 个值是没有意义的。因此，我建议的第一件事是在开始时设置 $gap = false 并在 $gap 为真时离开循环。你可以这样做1.) 打破（不那么优雅），2.) 将您的代码提取到一个方法并添加一个返回语句或3.) 在 for 循环中添加条件。我不熟悉 php，但在大多数语言中，可以这样做：&nbsp; &nbsp; &nbsp;$gap = false;&nbsp; &nbsp; &nbsp;$limit = count($temperatures);&nbsp; &nbsp; &nbsp;for ($i = 0; $i <= limit && !$gap; $i++) {&nbsp; &nbsp; &nbsp;[...]所以一旦 $gap 为真，外部的 for 循环就剩下了。

Answer 2

向后迭代，记住最后一个有效值并在看到空字符串时将其放入。那么它是 O(n) 最坏的情况，而不是 O(n^2)。或者，您可以在内循环之后从$y - 1to&nbsp;$x（或反之亦然）开始工作，设置间隙数组的值/输出值，然后跳过您刚刚完成的所有值 (&nbsp;$x = $y)。这也是 O(n)。然后，一旦你尽可能快地获得了算法，你就可以放弃 PHP 并用 Rust 或 C 之类的语言编写它。（我不记得该语言中有任何真正的数组，所以它们总是会减缓。）