Нахождение максимума по n-му измерению в C

Question

Я работаю над проблемой, в которой время выполнения критично. У меня есть еще одна функция C, которая создает трехмерные сетки значений с серией временных меток. Я хочу найти max_value в каждой трехмерной сетке на каждой временной метке. Кроме того, я отслеживаю среднее значение (sum / ncell) каждой сетки и возвращаю максимальное, нормализованное по среднему значению.

Я не разбираюсь в C, поэтому я хотел проверить, есть ли что-нибудь Мне не хватает фактического кода или использования OpenMP. Думаю, мой вопрос:

Каков наиболее эффективный способ найти максимальные значения n-мерного массива, разрезанного по n-му измерению?

Я понимаю, что лучшее, на что вы можете надеяться (поскольку сетки неупорядочены) равно O (n). Моя оценка такова, что тогда эта проблема составляет O (mxn), m = измерение времени, n = измерение сетки, и я думаю, что моя реализация достигает этого. Обычно значения для этих размеров, возможно, составляют от m = 5000 до 20000, n = 200 * 200 * 60.

В настоящее время я синхронизирую свою функцию-оболочку Python (которая включает инициализацию numpy.ndarray s, которая получить значения max, normMax и maxIndex:

• m = 2400
• n = 54000
• нитей = 8

Для которые я усредняю ​​~ 0,33 секунды, чтобы найти максимальные значения.

Если это актуально, это на моем ноутбуке с:

• Intel (R) Core (TM) i7-7700HQ ЦП с частотой 2,80 ГГц (кэш 6 МБ)
• 32 ГБ ОЗУ

Код:

void find_max(double *mapPt, double *maxPt, double *normMaxPt,
              int64_t *indexPt, int32_t nsamp, int32_t ncell,
              int64_t threads)
{
    double  maxValue, currentValue, sum;
    int32_t cell, maxIndex, timeSample;

    #pragma omp parallel for num_threads(threads)
    for (timeSample=0; timeSample<nsamp; timeSample++)
    {
        maxValue = 0.0;
        maxIndex = 0;
        sum = 0.0;
        for (cell=0; cell<ncell; cell++)
        {
            currentValue = mapPt[cell * nsamp + timeSample];
            sum += currentValue;
            if (currentValue > maxValue)
            {
                maxValue = currentValue;
                maxIndex = cell;
            }
        }
        maxPt[timeSample] = maxValue;
        normMaxPt[timeSample] = maxValue * ncell / sum;
        indexPt[timeSample] = maxIndex;
    }
}

Я компилирую с g cc 7.4.0, с важные флаги, вероятно, -Ofast и -lm.

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

Answer 1

Одно из предложений, которое я мог увидеть, - иметь double *timesame_mapcells = &mapPt[timeSample]; в начале каждого потока.

Тогда вы можете просто индексировать с помощью cell * nsamp, так что на одно добавление меньше за доступ. Но компилятор, возможно, был достаточно умен, чтобы оптимизировать это. сложение timeSample каждый раз + умножение nsamp. Опять же, это просто предложение, которое вы можете попробовать. Я не знаю, окажет ли это заметное влияние на производительность. (Но мне любопытно узнать, так ли это, если вы поставите ему go)