Ответы, понравившиеся пользователю Михаил

Оптимизировать код или как выделить всю вычислительную мощность пк на его выполнение?

dollar @dollar

Делай добро и бросай его в воду.

Первое, что бросается в глаза - это многократное копирование массива. Представьте, что при сортировке мы бы после каждых двух-трех перестановок делали бы полный дубликат массива. Это же ужас! И это слабое место, постоянное перевыделение памяти больших размеров.

Второе, что тоже важно - это сложность O(N*N). В вашем случае это критично, потому что много элементов в исходном массиве.

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

И маленькая оптимизационная хитрость - поиск интервала происходит по индексу, то есть O(1). Нужно немного поразмыслить, чтобы до этого догадаться, но в целом всё просто.

Код

<?php
$arr = [100,125,75,175,25,300,275,325,375];
$step = 50;

$b = []; //-1 - deny, 0 - not set, 1 - has interval
$int = []; //intervals if necessary 
$step2 = intdiv($step,2);
$arr = array_values(array_filter($arr, function($v) use ($step2,&$b,&$int) {
    $i = intdiv($v,$step2);
    $mod = $v % $step2;
    $res = true;
    if (isset($b[$i])) {
        if ($b[$i] === -1) $res = false;
        elseif ($mod < $int[$i][0] or $mod > $int[$i][1]) $res = false;
    }
    $b[$i] = -1;
    $b[$i+1] = -1;
    $b[$i-1] = -1;
    if (!isset($b[$i+2])) {
        $b[$i+2] = 1;
        $int[$i+2] = [$mod,$step2];
    } elseif ($b[$i+2] === 1) {
        if ($int[$i+2][0] < $mod) {
            $int[$i+2][0] = $mod;
            if ($int[$i+2][0] >= $int[$i+2][1]) $b[$i+2] = -1;
        }
    }
    if (!isset($b[$i-2])) {
        $b[$i-2] = 1;
        $int[$i-2] = [0,$mod];
    } elseif ($b[$i-2] === 1) {
        if ($int[$i-2][1] > $mod) {
            $int[$i-2][1] = $mod;
            if ($int[$i-2][0] >= $int[$i-2][1]) $b[$i-2] = -1;
        }
    }
    return $res;
}));

var_dump($arr); // [100, 175, 25, 300, 375]
?>

Переписав алгоритм на С++, получите дополнительно 50-кратное увеличение скорости.

Войдите на сайт