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

Темы, не касающиеся фреймворка, но относящиеся к программированию в целом.
Аватара пользователя
PaSiS
Сообщения: 88
Зарегистрирован: 2011.11.15, 18:07
Контактная информация:

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

Сообщение PaSiS »

Всем дооброго времени суток!
Наткнулся тут на задачку по оптимизации PHP кода, хотелось бы узнать варианты сообщества, т.к. свох получилось не много :D

Сам код:

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

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

function func($array)
{
    $size   = count($array) - 1;
    $result = 0;

    for ($i = 0; $i <= $size; $i++) {
        for ($j = 0; $j <= $size; $j++) {
            if ($array[$i] == $array[$j]) {
                $result = max($result, abs($i - $j));
            }
        }
    }

    return $result;
}
 
P.S. Код привел по памяти, но суть та же.
Loveorigami
Сообщения: 977
Зарегистрирован: 2014.08.27, 21:54

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

Сообщение Loveorigami »

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

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

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

    for ($i = 0; $i <= $size; $i++) {
       $result_array[$array[$i]][] = $i; // получаем места одинаковых значений
       /*
       
       [
               [2] => [0, 4],
               [3] => [1, 2],
               [4] => [3],
               [1] => [5, 6],
               [9] => [7]
       ]
       
       */
       
    }
// foreach и находим разницу между макс и мин в массиве
//  пропускаем "невалидные" (т.е. где была всего 1 запись (собственная)
// из примера - это 9 и 4, имеем
       /*
       [
               [2] => [0, 4],
               [3] => [1, 2],
               [1] => [5, 6],
       ]
       */
     
      foreach ($result_array as $Item) {
              if(count($Item)<2)) continue;
              $result = max($result, array_pop($Item) - array_shift($Item));
      }
      
      // на выходе получим 4

    return $result;
}
Последний раз редактировалось Loveorigami 2016.07.08, 14:47, всего редактировалось 4 раза.
zelenin
Сообщения: 10596
Зарегистрирован: 2013.04.20, 11:30

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

Сообщение zelenin »

Loveorigami писал(а):

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

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

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

    for ($i = 0; $i <= $size; $i++) {
       $result_array[$array[$i]][] = $i; // получаем места одинаковых значений
       /*
       
       [
               [2] => [0, 4],
               [3] => [1, 2],
               [4] => [3],
               [1] => [5, 6],
               [9] => [7]
       ]
       
       */
       
    }

     //  из $result_array - удаляем "невалидные" (т.е. где было 1 совпадение) $array[$i] == $array[$j]
     // из примера - это 9 и 4
     // находим max из result_array

    return $result;
} 
не соответствует коду из топика)

у автора хотелось бы уточнить, что оптимизировать - написанный по памяти код, выражающий достаточно странную задачу, или есть какое-то реальное описание задачи?
Loveorigami
Сообщения: 977
Зарегистрирован: 2014.08.27, 21:54

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

Сообщение Loveorigami »

не... я еще дописываю )))

У автора в result записывается максимальное значение разницы позиций в одном массиве при совпадении значений
Последний раз редактировалось Loveorigami 2016.07.08, 14:41, всего редактировалось 1 раз.
Аватара пользователя
PaSiS
Сообщения: 88
Зарегистрирован: 2011.11.15, 18:07
Контактная информация:

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

Сообщение PaSiS »

zelenin писал(а): у автора хотелось бы уточнить, что оптимизировать - написанный по памяти код, выражающий достаточно странную задачу, или есть какое-то реальное описание задачи?
Реального описания нет, это просто "задача". Хотя я и не уверен, может в ней какой-то конкретный алгоритм реализуется...
А оптимизировать требуется, в первую очередь, вермя выполнения. По памяти так же было ограничение, но это на втором месте.
Loveorigami
Сообщения: 977
Зарегистрирован: 2014.08.27, 21:54

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

Сообщение Loveorigami »

По идее, теперь правильно. Осталось протестировать: оптимизировали или наоборот )
Последний раз редактировалось Loveorigami 2016.07.08, 15:05, всего редактировалось 1 раз.
zelenin
Сообщения: 10596
Зарегистрирован: 2013.04.20, 11:30

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

Сообщение zelenin »

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

9960
4.1749351024628
9960
2.727420091629
9960
0.0047531127929688
варианты автора, loveorigami и мой соответственно. ) "дети" хотел добавить) я еще не оптимизировал, а сразу алгоритм написал, хотя есть мыслишка и об оптимизации.
Loveorigami
Сообщения: 977
Зарегистрирован: 2014.08.27, 21:54

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

Сообщение Loveorigami »

Ну, у меня еще был такой вариант (направить перебор с противоположных сторон)

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

function func3($array)
{
    $size   = count($array) - 1;
    $result = 0;

    for ($i = $size; $i >= (int)$size/2; $i--) {
        if($result) break;
        for ($j = 0; $j <= (int)$size/2; $j++) {
            if($result) break;
            if ($array[$i] == $array[$j]) {
                $result = max($result, abs($i - $j));
            }
        }
    }

    return $result;
} 
но я не стал его рассматривать ввиду того, что совпадение может быть в одной из частей

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

$array = [1, 1, 3, 3, 4, 5, 6, 6];  // Массив может содержать от 1 до 100000 целых чисел 
Аватара пользователя
PaSiS
Сообщения: 88
Зарегистрирован: 2011.11.15, 18:07
Контактная информация:

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

Сообщение PaSiS »

zelenin писал(а):и мой соответственно. )
Приведете свой вариант решения?) Очень интересно решение с такой оптимизацией!
zelenin
Сообщения: 10596
Зарегистрирован: 2013.04.20, 11:30

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

Сообщение zelenin »

оптимизация дает копейки, а читабельность кода падает сильно.
Итоговый результат на массиве из 10000 элементов:

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

9971
4.13021 сек (вариант PaSiS)
9971
2.71742 сек (вариант Loveorigami - быстрее на 52%)
9971
0.00467 сек (вариант zelenin - быстрее на 88248%)
Есть еще желающие поучаствовать?
zelenin
Сообщения: 10596
Зарегистрирован: 2013.04.20, 11:30

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

Сообщение zelenin »

PaSiS писал(а):
zelenin писал(а):и мой соответственно. )
Приведете свой вариант решения?) Очень интересно решение с такой оптимизацией!
обязательно приведу, если не будет желающих)
Loveorigami
Сообщения: 977
Зарегистрирован: 2014.08.27, 21:54

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

Сообщение Loveorigami »

есть еще такой вариант ))

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

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

    for ($i = 0; $i <= $size; $i++) {
        if(isset($result_array['min'][$array[$i]])){
            $result_array['max'][$array[$i]] = $i - $result_array['min'][$array[$i]];
        } else {
            $result_array['min'][$array[$i]] = $i;
        }
    }
    
    //echo '<pre>';
    //print_r($result_array);
    /*
    Array
(
    [min] => Array
        (
            [2] => 0
            [3] => 1
            [4] => 3
            [1] => 5
            [9] => 7
        )

    [max] => Array
        (
            [3] => 1
            [2] => 4
            [1] => 1
        )

)
  
    */
    
    return max($result_array['max']); // 4
}
 
Аватара пользователя
samdark
Администратор
Сообщения: 9489
Зарегистрирован: 2009.04.02, 13:46
Откуда: Воронеж
Контактная информация:

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

Сообщение samdark »

А как генерируется массив данных для сравнения?
zelenin
Сообщения: 10596
Зарегистрирован: 2013.04.20, 11:30

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

Сообщение zelenin »

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

$array = [];

for ($i = 0; $i< 10000; $i++) {
    $array[] = mt_rand(1, 1000);
} 
zelenin
Сообщения: 10596
Зарегистрирован: 2013.04.20, 11:30

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

Сообщение zelenin »

последний вариант от Loveorigami быстрее моего в 3-4 раза на массиве из 10т. Протестирую на 100т.
zelenin
Сообщения: 10596
Зарегистрирован: 2013.04.20, 11:30

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

Сообщение zelenin »

для 10т (удалил явно медленные варианты):
---
9959
0.00539 сек (вариант zelenin #2 для большого объема данных)
---
9959
0.00437 сек (вариант zelenin #1)
---
9959
0.00153 сек (вариант Loveorigami #2)
---
для 100т:
---
99954
0.04784 сек (вариант zelenin #2 для большого объема данных)
---
99954
0.16849 сек (вариант zelenin #1)
---
99954
0.0154 сек (вариант Loveorigami #2)
---
для 1млн:
---
999955
0.47201 сек (вариант zelenin #2 для большого объема данных)
---
999955
12.75842 сек (вариант zelenin #1)
---
999955
0.15211 сек (вариант Loveorigami #2)
---
Loveorigami
Сообщения: 977
Зарегистрирован: 2014.08.27, 21:54

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

Сообщение Loveorigami »

в моем случае можно max массив не формировать. и сэкономить на одной операции. Тоже даст небольшой прирост (у меня вышло в 2-3 раза)

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

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

    for ($i = 0; $i <= $size; $i++) {
        if(isset($result_array['min'][$array[$i]])){
            $max = $i - $result_array['min'][$array[$i]];
            if($result < $max ) $result = $max;
        } else {
            $result_array['min'][$array[$i]] = $i;
        }
    }
    
    //echo '<pre>';
    //print_r($result_array);
    
    return $result;
} 
zelenin
Сообщения: 10596
Зарегистрирован: 2013.04.20, 11:30

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

Сообщение zelenin »

для 1 млн:
---
999959
0.47318 сек (вариант zelenin #2 для большого объема данных)
---
999959
0.16005 сек (вариант Loveorigami #2)
---
999959
0.12724 сек (вариант Loveorigami #2 оптимизированный)
---
999959
0.0927 сек (вариант Loveorigami #2 оптимизированный zelenin)
---
zelenin
Сообщения: 10596
Зарегистрирован: 2013.04.20, 11:30

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

Сообщение zelenin »

---
999925
0.57384 сек (вариант zelenin #2 для большого объема данных)
---
999925
0.17678 сек (вариант Loveorigami #2)
---
999925
0.12483 сек (вариант Loveorigami #2 оптимизированный)
---
999925
0.06404 сек (вариант Loveorigami #2 оптимизированный zelenin)
---
еще оптимизировал, но уже знанием особенностей языка. Алгоритмически, думаю, уже не оптимизировать.

Loveorigami, оптимизируй свой алгоритм до моего результата.)
Loveorigami
Сообщения: 977
Зарегистрирован: 2014.08.27, 21:54

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

Сообщение Loveorigami »

ну еще у меня можно убрать ассоциацию у массива (осталась от прототипа)

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

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;
        }
    }
    
    //echo '<pre>';
    //print_r($result_array);
    
    return $result;
} 
тоже дало небольшое ускорение
Ответить