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

Question

[ImVeryStupid]

Есть массив целых. Задача:

Представить все значения как диапазоны: значение .. (значение + 50)
Взять первое значение (диапазон)
отсечь все пересекающиеся с ним диапазоны ниже
взять второе
отсечь пересекающиеся
следующий
и так далее

Сохранение порядка обязательно.

Код:

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

for ($i = 0; $i <= count($arr)-1; $i++) {
    $value = $arr[$i];
    $arr = array_values(array_filter($arr, function($v) use ($value,$step) {
        return ($value+$step < $v or $v+$step < $value or $v == $value);
    }));
}

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

100к чисел этим кодом обрабатывать сутки.
Перебирать без функций "вручную"?
Или что ещё можно сделать?

Comments

[ImVeryStupid]

tommy-vercetti, c#?

[dollar]

Можете более понятно изложить суть? Или конкретный пример из реального мира, где это может пригодиться. Так всем будет проще.

[ImVeryStupid]

dollar, конкретный пример:
Есть 30 2-х часовых отснятых на одну стационарную камеру выступлений на сцене.
Стоит задача выделил из каждого видео 2 динамичные минуты.
VLC плеер считает и записывает кол-во изменений в соседних кадрах.
Итак. Есть массив из 216 000 чисел (216000 / 30 кадров / 60 сек / 60 мин = 2 часа видео)
каждое число = кол-во изменений в соседних кадрах

Суммирую кол-во изменений в каждой секунде сдвигая по кадру:
сумма 0-30
сумма 1-31
сумма 2-32
сумма 3-33
..

отсекаю маленькие суммы, остальное сортирую по сумме по убыванию, получаю массив из вопроса
По сути: значения в нём - это номера кадров, отсортированные по сумме изменений в след. секунде
Теперь среди пересекающихся секунд нужно оставить самые динамичные

[dollar]

ImVeryStupid, а какая вариантивность значений? От 0 до 375? Или больше?

[ImVeryStupid]

dollar, массив в вопросе - это пример
вообще приблизительно от 1 до 100к

[dollar]

А значения не могут повторяться?

[ImVeryStupid]

dollar, не могут

Answer 1

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

Comments

[ImVeryStupid]

100к обработало сразу же, разбираюсь

[Дима Соколов]

Скоро будет JIT в PHP и С++ станет не нужен.

[h0w4rd]

Дима Соколов, ага, уже вижу как драйвера для устройств на АЭС пишут на PHP, ха-ха. И тащат за собой этот интерпретатор и с десяток мегабайт зависимостей. И прям вижу как PHP переписали на PHP, ведь С++ не будет нужен. Смешно.

Answer 2

[jcmvbkbc]

Скопировать исходный массив A в массив B, дополнить каждый элемент индексом в исходном массиве, отсортировать по значению элементов. Завести массив C такого же размера как исходный, заполнить его нулями.
Сделать текущим первый элемент А.

Начало цикла.
Отметить в C текущий элемент. Найти в массиве B текущий элемент элемент. Просмотреть соседние элементы B и отметить в С как отсечённые все те, диапазоны которых пересекаются с текущим. Найти следующий не отмеченный элемент С, сделать его текущим, перейти к началу цикла, если все элементы C отмечены -- закончить.

Количество действий зависит от количества пересекающихся отрезков, оно будет больше O(N log N) но меньше N^2.

Answer 3

[Сергей Тихонов]

Стоит задача выделил из каждого видео 2 динамичные минуты.
VLC плеер считает и записывает кол-во изменений в соседних кадрах.

Вариант 1: нужен один двухминутный отрезок
Cамыми динамичными будут 120 секунд видео, имеющие максимальную сумму изменений. Соответственно, берем окно шириной 120 секунд, и проходом по всему массиву считаем сумму чисел (на каждой итерации +1 новое и -1 старое значение). По дороге отмечаем таймстепм максимума.
Вариант 2: нужно top-120 самых динамичных секунд
Линейным проходом по всему массиву поддерживаем этот топ в актуальном состоянии (вставка в отсортированный список, отрезание самого меньшего значения), по окончании прохода - пересортируем топ по таймстемпам секунд.

Comments

[ImVeryStupid]

проходом по всему массиву поддерживаем этот топ в актуальном состоянии

звучит круто

Answer 4

[Stalker_RED]

найти максимальное значение
если их несколько одинаковых - посчитать сколько. это все за один проход.

записать в результат их в виде диапазонов. все.

Comments

[jcmvbkbc]

Сохранение порядка обязательно.

[Stalker_RED]

jcmvbkbc, какой еще порядок у нескольких ОДИНАКОВЫХ чисел? Ну и есть шанс, что на выходе будет вообще одно число.

Тут скрее проблема в том, что автор неправильно составил вопрос, что видно из его комментариев.
Вероятно ему нужна выборка скольки-то ввысоких значений из списка с привязкой ко времени или номерам кадров. Но он пока он это не может сформулировать - это решение подходит.

[jcmvbkbc]

какой еще порядок у нескольких ОДИНАКОВЫХ чисел

Stalker_RED, ну посмотри же в приведённый пример?

[Stalker_RED]

jcmvbkbc, ну так там останется только 375..425 а остальные придется отсеять. Не?

[jcmvbkbc]

ну так там останется только 375..425 а остальные придется отсеять. Не?

не. автор говорит:

[100, 175, 25, 300, 375]

Answer 5

[ThunderCat]

Стоит задача выделил из каждого видео 2 динамичные минуты. ...
Суммирую кол-во изменений в каждой секунде сдвигая по кадру:
сумма 0-30...

может сумма 0 - 120*30 и далее?
или вам нарезка из секундных кусков нужна?
или 2 минуты подряд?

Comments

[ImVeryStupid]

нарезка..

Answer 6

[SagePtr]

Жадное решение за 120*(n+30) итераций:
1) Пробегаем по массиву окном в 30 кадров, находим максимальную сумму, запоминаем (кладём в массив результата).
2) Полученным 30 кадрам присваиваем отрицательный вес (например, равный -30 * (макс.значение в массиве), дабы точно не попал в следующую выборку).
3) Повторяем п 1-2 120 раз, пока не получим 120 не пересекающихся диапазонов (если отрицательное значение в пункте 2 выбрано правильно), отсортированных по убыванию веса. Естественно, если мы храним их как пару (время, вес), то можем потом обратно отсортировать по времени.