Оптимизация PHP кода

[samdark]

Да, там надо ещё проверить, что индекс до половины дошёл... но из за дополнительного условия смысла в проверке особо нет.

[Loveorigami]

О, хотел свой выложить... Переписал через foreach

[samdark]

Подозреваю, что дальше уже некуда... отлично поупражнялись.

[zelenin]

да, супер. Улучшили первоначальный алгоритм примерно в 1 млн раз)

[Loveorigami]

Кстати "о птичках"
foreach у меня все-таки медленнее почему то работает.

Код: Выделить всё

$array = [];
for ($i = 0; $i< 1000000; $i++) {
    $array[] = mt_rand(1, 1000);
} 

$time_start = microtime(true);
echo func5($array);
$time_end = microtime(true);
$time = $time_end - $time_start;
echo " $time s.\n<br>";


$time_start3 = microtime(true);
echo func6($array);
$time_end3 = microtime(true);
$time3 = $time_end3 - $time_start3;
echo " $time3 s.\n<br>";


function func5($array)
{
    $size   = count($array) - 1;
    $result = 0;
    $result_array = [];

    for ($i = 0; $i <= $size; $i++) {
        if(isset($result_array[$array[$i]])){
            $max = $i - $result_array[$array[$i]];
            if($result < $max ) $result = $max;
        } else {
            $result_array[$array[$i]] = $i;
        }
        
    }
    
    return $result;
} 

function func6($array)
{
    $result = 0;
    $result_array = [];


    foreach($array as $key => $value) {
        if(isset($result_array[$value])){            
            $max = $key - $result_array[$value];
            if($result < $max ) $result = $max;
        } else {
            $result_array[$value] = $key;
        }
    }
    
    //echo '<pre>';
    //print_r($result_array);
    
    return $result;
} 

//
999938 0.33801913261414 s.
999938 0.47102689743042 s. 

версия php 5.5
win7 x64

[zelenin]

не тести в браузере)

999958 0.076744794845581 s.
999958 0.065219163894653 s.

php 7, ubuntu

[samdark]

Измерять надо в разных php-файликах с внешним набором данных...

[PaSiS]

Интересное получилось соревнование)
Спасибо всем за варианты!

Не думал что простой вопрос перейдет в такое обсуждение)

[Loveorigami]

не тести в браузере)

999958 0.076744794845581 s.
999958 0.065219163894653 s.

php 7, ubuntu

Я и в консоли phpStorm-a тестил... Просто странно - менял местами замеры. Сначала for-foreach, потом foreach-for...
Всегда один и тот же результат. For меньше foreach.

Я так и подозревал, что zelenin на 7 мерял (о 7 писали, что быстродействие улучшено), а если на 5,5 запустить тесты, интересно, такой же результат получим ? )))

[Loveorigami]

синий - for
красный - foreach

[Loveorigami]

По отдельности тоже. foreach 0,003 не показал ни разу. от 0,005 до 0,006

Из старых обсуждений на эту тему
http://best-web-creation.com/articles/v ... ov?lang=ru

Foreach быстрее, а у меня наоборот )...
Ну ладно, в принципе уже микро нюансы.

Осталось увидеть первые решения zelenin-a для коллекции ).

[zelenin]

самый первый вариант:

Код: Выделить всё

$storage = new ArrayObject;
$result = 0;
foreach($array as $key => $value) {
    $storage[$value][] = $key; // накапливаем ключи. При миллионе значений тут будет около 1000 ключей
    
    $diff = max($storage[$value]) - min($storage[$value]);
    
    $result = $result > $diff ? $result : $diff;
}

оптимизированный для большого кол-ва данных:

Код: Выделить всё

$storage = new ArrayObject;
$result = 0;
foreach($array as $key => $value) {
    $storage[$value][] = $key;

    $max = max($storage[$value]);
    $min = min($storage[$value]);

    $diff = $max - $min;

    $storage[$value] = [$max, $min]; // оставляем вместо 1000 ключей только макс и мин

    $result = $result > $diff ? $result : $diff;
}

стал оставлять в ячейке только максимум и минимум

для инфо: вместо foreach попробовал array_walk - просело процентов на 20.

UPD: это был вариант в лоб. После этого я уверился в своей победе и об изменении алгоритма больше не думал. А после варианта Loveorigami другой алгоритм уже придумать было нельзя, т.к. задача достаточно специфична, и так или иначе решить ее оптимально можно было только одним способом, что как раз показал SamDark, параллельно придя к тому же способу. Но оптимизация алгоритма все таки дала прирост в 3-4 раза, что очень круто.

[Loveorigami]

А слона-то мы не заметили - не обратили внимание, что в задаче речь шла о целых числах.

Код: Выделить всё

$array = [2, 3, 3, 4, 2, 1, 1, 9];  // Массив может содержать от 1 до 100000 целых чисел   

т.е. в массиве могут присутствовать и отрицательные числа.

[zelenin]

не думаю что от этого что-то изменится

[samdark]

Ровным счётом ничего не поменяется. Можно хоть строки там держать.

[Loveorigami]

Ровным счётом ничего не поменяется. Можно хоть строки там держать.

Строки - да, для отрицательных же нельзя будет использовать такой алгоритм

Код: Выделить всё

foreach($array as $key => $value) {
    $storage[$value][] = $key;
    ...
    }
     

У меня навскидку было две идеи
Использовать в качестве storage 2 массива

Код: Выделить всё

foreach($array as $key => $value) {
if($value>0){
    $storage_plus[$value][] = $key;
    ...
    } else {
         $storage_minus[abs($value)][] = $key;
         ...
    }
}
     

или же использовать двухмерный массив

Код: Выделить всё

foreach($array as $key => $value) {
if($value>0){
    $storage[$value][0][] = $key;
    ...
    } else {
         $storage[0][abs($value)][] = $key;
         ...
    }
}

и т.д.
     

Какой из них был бы быстрее?

[zelenin]

Строки - да, для отрицательных же нельзя будет использовать такой алгоритм

Код: Выделить всё

foreach($array as $key => $value) {
    $storage[$value][] = $key;
    ...
    }

поясни. не вижу подвоха.

[Loveorigami]

протупил...
Ключи же могут быть и отрицательными.

[samdark]

Ну да. Всё нормально...