如何使循环更快？

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，但在大多数语言中，可以这样做：

     $gap = false;

     $limit = count($temperatures);

     for ($i = 0; $i <= limit && !$gap; $i++) {

     [...]

所以一旦 $gap 为真，外部的 for 循环就剩下了。

Answer 2

向后迭代，记住最后一个有效值并在看到空字符串时将其放入。那么它是 O(n) 最坏的情况，而不是 O(n^2)。

或者，您可以在内循环之后从$y - 1to $x（或反之亦然）开始工作，设置间隙数组的值/输出值，然后跳过您刚刚完成的所有值 ( $x = $y)。这也是 O(n)。

然后，一旦你尽可能快地获得了算法，你就可以放弃 PHP 并用 Rust 或 C 之类的语言编写它。（我不记得该语言中有任何真正的数组，所以它们总是会减缓。）