Как я могу сделать цикл быстрее? - PullRequest
Новая
       23

Как я могу сделать цикл быстрее?

0 голосов
/ 29 июня 2019

У меня есть массив значений, которые представляют точки на линейном графике: 

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

Я использую PHP4, но думаю, что на него можно ответить на любом языке.

Массив содержит только цифры, нули и пустые строки.

Числа обозначают температуры, нулевые означают, что инструменты не работали, а пустые строки не представляют ни того, ни другого (приборы работают, просто ничего не измеряя).

Точки должны (в большинстве случаев) быть связаны, так как это линейный график.

У меня есть переменная $gap, которая соответствует каждой точке и сообщает, связана ли эта точка со следующей точкой. Если установлено значение true, то точки не связаны (в противном случае false). Например, $ gap для temperatures[0] должно быть установлено на false, поскольку линия проводится между temperatures[0] и температурами [1] (they are both valid temperatures). $gap for температура [1] and температура [2] `должна быть истинной, так как есть нулевое следование. И так далее.

При нулевом значении $ разрыв равен true. Для чисел и пустых строк это зависит от: если следует ноль, пробел равен true; если число следует, разрыв является ложным. Если следует пустая строка, мы должны проверить, будет ли впоследствии ноль или число, и соответственно применить предыдущее предложение. Если следуют только пустые строки, пробел равен true. Вот мой код, который работает слишком медленно, но дает правильные результаты: 

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

Как я могу ускорить его?

Ответы [ 2 ]

1 голос
/ 29 июня 2019

Ваш код проверяет, есть ли где-то разрыв в вашей линейной диаграмме или нет.

Так что, как только разрыв найден, нет причин продолжать во внешнем цикле for.Подумайте о графике из 1000 значений, если между первыми двумя значениями есть разрыв, нет смысла продолжать проверять остальные 998 значений.

Таким образом, первое, что я бы порекомендовал, это установить $ gap =ложь в начале и выход из цикла, если $ gap равен true.Вы можете сделать это либо с помощью

1.) Break (не очень элегантно),

2.), Извлечения кода в метод и добавления оператора возврата, либо

3.) добавление условия в цикл for.Я не знаком с php, но в большинстве языков это можно сделать так: 

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

     [...]

Так что, если $ gap равен true, внешний цикл for остается.

0 голосов
/ 29 июня 2019

Перебирайте в обратном порядке, запоминая последнее действительное значение и вставляя его, когда вы видите пустую строку. Тогда это O (n) худший случай, а не O (n ^ 2).

В качестве альтернативы, вы можете работать от $y - 1 до $x (или наоборот) после внутреннего цикла, устанавливая значения массива пробелов / выводя значения, затем пропуская все те, которые вы только что сделали ($x = $y). Это тоже O (n).

Затем, как только вы получите алгоритм настолько быстро, насколько сможете, вы можете отказаться от PHP и записать его в нечто вроде Rust или C. (Я не помню никаких истинных массивов в языке, поэтому они всегда будет медленно.)

...