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