Можете не суммонить меня, пока на Тостере не сделают полноценный доступ к удалённому вопросу всем, кто успел его просмотреть.

Достижения

Все достижения (60)

Наибольший вклад в теги

Все теги (356)

Лучшие ответы пользователя

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

    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-кратное увеличение скорости.
    Ответ написан

Лучшие вопросы пользователя

Все вопросы (293)