Помогите оптимизировать этот фрагмент среднего расчета

Question

Возможно ли ускорить этот фрагмент?

firstSample и lastSample - это часть массива, которая мне интересна в этой итерации. Именно когда этот интервал достигает> 3000, я получаю заметное замедление. Массив _average может содержать от 6 до 60 миллионов значений типа int.

minY и maxY - это результат, который я использую после завершения этого вычисления.

int minY = Int32.MaxValue;
int maxY = Int32.MinValue;
int Y = 0;
int sample = firstSample + 1;

while (sample <= lastSample)
{
       Y = _average[sample];
       minY = Math.Min(Y, minY);
       maxY = Math.Max(Y, maxY);
       sample++;
}

Answer 1

Выражение _average [sample] является огромным узким местом, поскольку оно содержит неявную проверку границ на каждой итерации. Используйте указатель на массив "_average" (и ключевое слово unsafe). Затем избегайте вызова каких-либо функций, поэтому избавьтесь от вызовов Math.Min / Max и сделайте это самостоятельно.

Без какого-либо компилятора в моих руках, я думаю, вот как это должно выглядеть:

unsafe
{
    fixed ( int* paverage = _average )   
    {
        int* p = paverage + firstSample + 1;
        for ( int sample = firstSample+1 ; sample <= lastSample ; sample++ )   
        {
            if ( *p < minY )
                minY = *p;
            if ( *p > maxY )
                maxY = *p;
            p++;
        }
    }   
}

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

Answer 2

Вы написали следующее в комментарии:

Я не сортирую. Только найти максимальный и минимальный интервал. И интервал движется каждые 20 мс

Кажется, что вы действительно хотите минимум движения и максимум движения .

Я полагаю, что это можно сделать более эффективно, чем повторно исследовать весь интервал каждый раз, предполагая, что интервал перемещается только в одном направлении и что между последующими интервалами имеется значительное перекрытие.

Один из способов - сохранить специальную очередь, где каждый новый элемент копирует свое значение в каждый элемент в очереди, который больше (для движущегося минимума), например ::

(5 8 4 7 7 0 7 0 4 4 3 4 0 9 7 9 5 4 2 0)  ; this is the array
(4 4 4 4)  ; the interval is 4 elements long, and initialized to the minimum
           ; of the first 4 elements
  (4 4 4 7)  ; next step, note that the current minimum is always the first element
    (4 7 7 0)  ; now something happens, as 0 is smaller than the value before
    (4 7 0 0)  ; there are still smaller values ...
    (4 0 0 0)  ; and still ...
    (0 0 0 0)  ; done for this iteration
      (0 0 0 7)
        (0 0 0 0)  ; the 0 again overwrites the fatties before
          (0 0 0 4)
            (0 0 4 4)
              (0 3 3 3)  ; the 3 is smaller than the 4s before,
                         ; note that overwriting can be cut short as soon as a
                         ; value not bigger than the new is found
                (3 3 3 4)
                  (0 0 0 0)  ; and so on...

Если вы перемещаетесь более чем на 1 элемент каждый раз, вы можете сначала вычислить минимум всех новых значений и использовать его для обратной перезаписи.

Наихудший случай для этого алгоритма - когда массив сортируется по убыванию, тогда это O (нм), где m - длина интервала, а n - длина массива. Наилучший случай, когда он отсортирован по убыванию, тогда это O (n). Для среднего случая я предполагаю O (n log (m)).

Answer 3

Небезопасный код позволит вам использовать указатели для индексации массива, поскольку JIT-компилятор не сможет удалить проверку границ в данном конкретном случае. Посмотрите здесь как это сделать.

Вы также можете попытаться встроить Мин / Макс коллы самостоятельно, но есть хороший шанс, что JIT уже делает это для вас.

Наконец, довольно просто распараллелить это с Parallel Extensions .NET 4 (вы можете использовать CTP для .NET 3.5). Просто убедитесь, что вы не записываете значения min / max из нескольких потоков одновременно. Однако не блокируйте его, я бы имел минимальное / максимальное значение для каждого потока и сделал бы окончательное сравнение между минимальными / максимальными значениями каждого потока / задачи, когда все потоки выполнены.

Answer 4

Вы можете избавиться от повторяющихся сравнений в ситуациях, когда вы найдете новый мин. Если вы установили оба значения min / max на первое значение, то, если вы найдете новый min, нет причин проверять, является ли он также новым max. Это в основном код @ Skeet с инициализацией и дополнительным оператором 'else'.

int firstIndex = firstSample + 1;
if (firstIndex <= lastSample)
{
    minY = _average[firstIndex];
    maxY = minY;

    for (int sample = firstIndex + 1; sample <= lastSample; sample++)
    {
        int y = _average[sample];
        if (y < minY)
        {
            minY = y;
        }
        else if (y > maxY)
        {
            maxY = y;
        }
    }
}

Answer 5

Используйте цикл for, как говорили другие, но установите его так, чтобы сравнение было нулевым. Это более быстрое сравнение в большинстве реализаций.

Answer 6

Вы можете попробовать цикл for, как предлагали другие.

Для этого потребуется профилирование, но вы также можете попробовать исключить вызовы методов и ветвления:

   Y = _average[sample];
   minY = minY + ((Y-minY) & (Y-minY)>>31);
   maxY = maxX - ((X-maxX) & (X-maxX)>>31);
   sample++;

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

Answer 7

Во-первых, я бы переписал его как простой цикл for и не использовал бы локальную переменную в Паскале, включая переменную с большей областью действия, чем необходимо:

int minY = int.MaxValue;
int maxY = int.MinValue;

for (int sample = firstSample + 1; sample <= lastSample; sample++)
{
    int y = _average[sample];
    minY = Math.Min(y, minY);
    maxY = Math.Max(y, maxY);
}

Это просто для того, чтобы сделать его более привычным и привычным. JIT знает о зацикливании массивов в определенных ситуациях, но я не знаю, поможет ли это в этом случае - он может просто проверить firstSample >= -1 && lastSample < _average.length, а затем исключить проверки границ, но я не знаю если это так. Теперь сэмплы, которые уже находятся в текущем минимальном / максимальном диапазоне, не нуждаются в побочных эффектах, поэтому давайте избавимся от назначений в этом случае:

for (int sample = firstSample + 1; sample <= lastSample; sample++)
{
    int y = _average[sample];
    if (y < minY)
    {
        minY = y;
    }
    if (y > maxY)
    {
        maxY = y;
    }
}

Я не знаю, поможет это или нет - и я подозреваю, что это не поможет, но, возможно, стоит попробовать ...

(Как сказал другой ответ, это очень простая операция для параллелизации - она ​​должна повысить скорость почти линейно с подсчетом процессоров, то есть 2 процессора ~ = в два раза быстрее и т. Д., За исключением пропусков кэша и т.

Answer 8

Я собираюсь высунуть свою шею и сказать Нет, я не думаю, что есть какой-либо способ сделать это значительно быстрее (если только не помогут встраивание вызовов Мин и Макс, но я ожидаю, что оптимизатор позаботится о что).

Но, тем не менее, если вы делаете это несколько раз для одних и тех же данных, сортировка данных (или фрагментов данных, с которыми вы имеете дело каждый раз) может ускорить весь процесс.

Сортировать медленнее, чем найти минимум, но сортировать быстрее, чем найти минимум тысячу раз.

(Простите, если я учу вас сосать яйца здесь. 8 -)

Answer 9

Вы можете использовать FOR быстрее, чем while, или использовать Parallel, если у вас 3.5+ framework