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

[zelenin]

это одна моя моя оптимизация) еще давай

[samdark]

У меня оригинал отрабатывает за 9.68s на 10 тыс., мой вариант за 0.72s.

[zelenin]

судя по всему медленный. Давайте код, протестирую со всеми алгоритмами.

[samdark]

Вариант топорный, без оптимизаций под язык вообще:

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

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

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

    return $result;
}
 

Ну и, кстати, пора бы уже словами задачу сформулировать: "Написать функцию, которая посчитает максимальное расстояние между двумя одинаковыми значениями в массиве".

[zelenin]

вариант оч. медленный - уже крутится 3+ минуты, в то время как остальные отработали за < 1 сек на 1 млн. Не буду дожидаться конца. Думаю, на два for можно сразу не закладываться.

[samdark]

Ну да, O(n^2).

[samdark]

Вот быстрый с маппингом:

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

function func3($array)
{
    $size = count($array);
    $maxDistance = 0;

    $firstPosMap = [];

    for ($i = 0; $i < $size; $i++) {
        $firstPos = array_key_exists($array[$i], $firstPosMap) ? $firstPosMap[$array[$i]] : null;
        if ($firstPos === null) {
            $firstPosMap[$array[$i]] = $i;
        } else {
            $maxDistance = max($maxDistance, $i - $firstPos);
        }
    }

    return $maxDistance;
}
 

[samdark]

0.28s на миллионе.

[zelenin]

---
999958
0.56387 сек (вариант zelenin #2 для большого объема данных)
---
999958
0.17867 сек (вариант Loveorigami #2)
---
999958
0.12832 сек (вариант Loveorigami #2 оптимизированный)
---
999958
0.06459 сек (вариант Loveorigami #2 оптимизированный zelenin)
---
999958
0.16599 сек (вариант Sam Dark #1)
---

[samdark]

А массив для тестов один и тот же? По хорошему, надо в файлик через var_export слить и его запускать...

[samdark]

И ещё... запускаются тесты, надеюсь, из разных файликов, а не все из одного?

[zelenin]

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

[Loveorigami]

пробовал у себя по разному:
- менял направление с конца
- менял if...else... местами (!isset)
- переменные называл одной буквой

заметного прироста не получил... т.е. вообще не получил. даже дольше получается... )))

p.s.
- с array_key_exists вместо isset заметно дольше.

[samdark]

Вот так вроде почуть побыстрее, но не на порядок, конечно:

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

function func3($array)
{
    $maxDistance = 0;
    $firstPosMap = [];

    foreach ($array as $i => $value) {
        if (isset($firstPosMap[$value])) {
            $maxDistance = max($maxDistance, $i - $firstPosMap[$value]);
        } else {
            $firstPosMap[$value] = $i;
        }
    }

    return $maxDistance;
}
 

[zelenin]

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

---
999643
0.55356 сек (вариант zelenin #2 для большого объема данных)
---
999643
0.1743 сек (вариант Loveorigami #2)
---
999643
0.12382 сек (вариант Loveorigami #2 оптимизированный)
---
999643
0.06538 сек (вариант Loveorigami #2 оптимизированный zelenin)
---
999643
0.11568 сек (вариант Sam Dark #1)
---
 

foreach - еще одна оптимизация

[samdark]

И ещё немного микрооптимизаций:

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

function func3($array)
{
    $maxDistance = 0;
    $firstPosMap = [];

    foreach ($array as $i => $value) {
        if (isset($firstPosMap[$value])) {
            if ($maxDistance < ($i - $firstPosMap[$value])) {
                $maxDistance = $i - $firstPosMap[$value];
            }
        } else {
            $firstPosMap[$value] = $i;
        }
    }

    return $maxDistance;
}
 

[zelenin]

---
999930
0.53447 сек (вариант zelenin #2 для большого объема данных)
---
999930
0.17654 сек (вариант Loveorigami #2)
---
999930
0.12446 сек (вариант Loveorigami #2 оптимизированный)
---
999930
0.06846 сек (вариант Loveorigami #2 оптимизированный zelenin)
---
999930
0.06189 сек (вариант Sam Dark #1)
---

[samdark]

И ещё. Добавил условие для досрочного выхода.

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

function func3($array)
{
    $maxDistance = 0;
    $firstPosMap = [];

    foreach ($array as $i => $value) {
        if ($maxDistance >= count($array) / 2) {
            break;
        }
        if (isset($firstPosMap[$value])) {
            if ($maxDistance < ($i - $firstPosMap[$value])) {
                $maxDistance = $i - $firstPosMap[$value];
            }
        } else {
            $firstPosMap[$value] = $i;
        }
    }

    return $maxDistance;
}

[zelenin]

на самом деле последний вариант практически один в один мой оптимизированный вариант Loveorigami:

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

$result = 0;
$storage = [];

foreach($array as $key => $value) {
    if(isset($storage[$value])){
        $max = $key - $storage[$value];
        if($result < $max ) {
            $result = $max;
        }
    } else {
        $storage[$value] = $key;
    }
} 

разница в выносе переменной $max. Предположу, что интерпретатор в варианте SamDark кэширует $i - $firstPosMap[$value] в некую структуру, являющуюся более легкой, чем явно выделенная переменная $max. Либо же двухкратный подсчет действительно быстрее, чем выделение памяти под переменную.

[zelenin]

И ещё. Добавил условие для досрочного выхода.

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

function func3($array)
{
    $maxDistance = 0;
    $firstPosMap = [];

    foreach ($array as $i => $value) {
        if ($maxDistance >= count($array) / 2) {
            break;
        }
        if (isset($firstPosMap[$value])) {
            if ($maxDistance < ($i - $firstPosMap[$value])) {
                $maxDistance = $i - $firstPosMap[$value];
            }
        } else {
            $firstPosMap[$value] = $i;
        }
    }

    return $maxDistance;
}

неверный вариант - условие некорректное.