我怎样才能使循环更快？

Question

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

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

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

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

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

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

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

当存在 null 时，$gap 绝对是 true。对于数字和空字符串，它取决于：如果后面是 null，则 gap 为真；如果后面是数字，则 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

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

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

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

Answer 2

您的代码会检查折线图中某处是否存在间隙。

所以一旦发现空隙，就没有理由在外面继续for-loop。想想一张包含 1000 个值的图表，如果前两个值之间存在差距，则继续检查其他 998 个值是没有意义的。

因此，我建议的第一件事是在开始时设置 $gap = false 并在 $gap 为真时离开循环。您可以使用

1.) break（不太优雅），

2.) 将代码提取到方法中并添加 return-statement 或

3.) 在for-loop中添加条件。我不熟悉 php 但在大多数语言中都可以这样做：

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

     [...]

所以一旦 $gap 为真，就剩下外面的 for-loop 了。

我怎样才能使循环更快？

How can I make a loop faster?

php

arrays

performance

loops

line