Функция Min /Max 1D-массива в C /C ++

Из-за ограничений программного обеспечения я не могу использовать стандартные библиотеки, <math.h>, <algorithm>, шаблоны, inline или Boost. Я также использую стандарт C (ISO C99), так что array не является зарезервированным ключевым словом, как в Visual Studio.

Является ли это «наилучшей» возможной реализацией функции min? Это должно быть надежным и быстрым. Есть ли более эффективная реализация на C ++?

double min(double* array, int size){
    // returns the minimum value of array
    static double val = array[0];
    for (int i = 1; i < size; ++i){
        val = val <= array[i] ? val : array[i];
    }
    return val;
}
11 голосов | спросил Elpezmuerto 3 +04002011-10-03T20:33:07+04:00312011bEurope/MoscowMon, 03 Oct 2011 20:33:07 +0400 2011, 20:33:07

3 ответа


19

Это не совсем лучшее. Есть некоторые вещи IMHO, которые препятствуют его производительности и полезности.

Нет смысла объявлять val как статическую переменную. Фактически, вы убили любой шанс, что он будет использоваться в многопоточных программах.

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

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

double min(const double *arr, size_t length) {
    // returns the minimum value of array
    size_t i;
    double minimum = arr[0];
    for (i = 1; i < length; ++i) {
        if (minimum > arr[i]) {
            minimum = arr[i];
        }
    }
    return minimum;
}
ответил Jeff Mercado 3 +04002011-10-03T21:59:19+04:00312011bEurope/MoscowMon, 03 Oct 2011 21:59:19 +0400 2011, 21:59:19
5

Вы можете использовать minps /pminsd SSE2 /SSE3 или соответствующий набор инструкций для вашего процессора /архитектора, поскольку он поддерживается непосредственно в GCC /MASM /TASM (если MASM или TASM не поддерживаются, такой набор инструкций SSE2 /SSE3 также существует файлы .inc для создания макросов, имитирующих наборы инструкций в Интернете для MASM), создайте файл .OBJ вашим любимым компоновщиком, затем свяжите его как обычно и используйте в своей любимой среде IDE. Вы получите от 4x до 16x прирост производительности по сравнению с традиционным «классическим» алгоритмом. Это зависит от размера данных (старые компиляторы рассматривают double не в формате IEEE, например, float в нескольких конфигурациях, в 16-кратных системах, в частности, двойное означает 32-битную структуру данных, а не 64-битную структуру данных, в современных языках она коррелирует с «двойной "и" long double ", соответственно)

Идея проста: если у вас есть k элементов, [k = 4n + p, 4> p => 0], заполните ее с помощью np элементов или просто загрузите последние 4 удвоения, переустановите на 0 последних p элементов, так что вы может быстро оценить n кандидатов. оценивайте кандидатов в n раз по сравнению с аккумулятором, вы получите минимум.

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

Пример использования SSE для вычисления пиковых значений массива float:

#include <xmmintrin.h>

double min(double* array, int size) { 
    // returns the minimum value of array 
    int i; 
    double val = array[0]; 
    for (i = 1; i < size; ++i) { 
        if (val > array[i]) { 
            val = array[i]; 
        } 
    } 
    return val; 
} 

#define ARRAY_SIZE 16

float m_fArray[ARRAY_SIZE];

void x86_sse_find_peaks(float *buf, unsigned nframes, float *min, float *max)
{
    __m128 current_max, current_min, work;

    // Load max and min values into all four slots of the XMM registers
    current_min = _mm_set1_ps(*min);
    current_max = _mm_set1_ps(*max);

    // Work input until "buf" reaches 16 byte alignment
    while ( ((unsigned long)buf) % 16 != 0 && nframes > 0) {

        // Load the next float into the work buffer
        work = _mm_set1_ps(*buf);

        current_min = _mm_min_ps(current_min, work);
        current_max = _mm_max_ps(current_max, work);

        buf++;
        nframes--;
    }

    // use 64 byte prefetch for quadruple quads
    while (nframes >= 16) {
        //__builtin_prefetch(buf+64,0,0); // for GCC 4.3.2+

        work = _mm_load_ps(buf);
        current_min = _mm_min_ps(current_min, work);
        current_max = _mm_max_ps(current_max, work);
        buf+=4;
        work = _mm_load_ps(buf);
        current_min = _mm_min_ps(current_min, work);
        current_max = _mm_max_ps(current_max, work);
        buf+=4;
        work = _mm_load_ps(buf);
        current_min = _mm_min_ps(current_min, work);
        current_max = _mm_max_ps(current_max, work);
        buf+=4;
        work = _mm_load_ps(buf);
        current_min = _mm_min_ps(current_min, work);
        current_max = _mm_max_ps(current_max, work);
        buf+=4;
        nframes-=16;
    }

    // work through aligned buffers
    while (nframes >= 4) {

        work = _mm_load_ps(buf);

        current_min = _mm_min_ps(current_min, work);
        current_max = _mm_max_ps(current_max, work);

        buf+=4;
        nframes-=4;
    }

    // work through the rest < 4 samples
    while ( nframes > 0) {

        // Load the next float into the work buffer
        work = _mm_set1_ps(*buf);

        current_min = _mm_min_ps(current_min, work);
        current_max = _mm_max_ps(current_max, work);

        buf++;
        nframes--;
    }

    // Find min & max value in current_max through shuffle tricks

    work = current_min;
    work = _mm_shuffle_ps(work, work, _MM_SHUFFLE(2, 3, 0, 1));
    work = _mm_min_ps (work, current_min);
    current_min = work;
    work = _mm_shuffle_ps(work, work, _MM_SHUFFLE(1, 0, 3, 2));
    work = _mm_min_ps (work, current_min);

    _mm_store_ss(min, work);

    work = current_max;
    work = _mm_shuffle_ps(work, work, _MM_SHUFFLE(2, 3, 0, 1));
    work = _mm_max_ps (work, current_max);
    current_max = work;
    work = _mm_shuffle_ps(work, work, _MM_SHUFFLE(1, 0, 3, 2));
    work = _mm_max_ps (work, current_max);

    _mm_store_ss(max, work);
}

int _tmain(int argc, _TCHAR* argv[])
{
    float   min = FLT_MAX;
    float   max = FLT_MIN;

    m_fArray[0] = 0;
    m_fArray[1] = 1;
    m_fArray[2] = 2;
    m_fArray[3] = 3;
    m_fArray[4] = 4;
    m_fArray[5] = 3;
    m_fArray[6] = 2;
    m_fArray[7] = 1;
    m_fArray[8] = -1;
    m_fArray[9] = -2;
    m_fArray[10] = -3;
    m_fArray[11] = -4;
    m_fArray[12] = -5;
    m_fArray[13] = -6;
    m_fArray[14] = -7;
    m_fArray[15] = -8;

    x86_sse_find_peaks(m_fArray, ARRAY_SIZE, &min, &max);

    printf("value = %.2f, max = %.2f\n", min, max); // output is: value = -8.00, max = 4.00
    return 0;
}
ответил Artur Mustafin 4 +04002011-10-04T15:50:30+04:00312011bEurope/MoscowTue, 04 Oct 2011 15:50:30 +0400 2011, 15:50:30
3

Рекомендуемая форма для надежности:

Хорошо, вы хотите крепко и быстро. Если бы это было необходимо в производственном коде, я бы, вероятно, написал его вот так:

double min(double array[], int size)
{
    assert(array != NULL);
    assert(size >= 0);

    if ((array == NULL) || (size <= 0))
       return NAN;

    double val = -DBL_MAX;
    for (int i = 0; i < size; i++)
        if (val < array[i])
            val = array[i];
    return val;
}

Looping: Я заметил, что вы оптимизировали свой цикл, чтобы начать сначала с val = array[0] и i = 1 вместо i = 0. Это может спасти системные циклы 20 лет назад, но в наши дни доступ к памяти является самым большим узким местом, и вы застряли с таким же количеством обращений к памяти в array[], независимо от того, как вы пишете цикл, поэтому я постараюсь быть как можно более неразумным и просто придерживаться более традиционного цикла.

Проверка аргумента: Можно ли вызвать эту функцию с помощью size из 0? Если да, то у вас также есть ошибка, если вы начинаете с val = array[0], когда size равно 0, потому что вы можете читать недопустимую память в зависимости от того, где указывается array. По крайней мере, логически некорректно рассматривать array[0], когда size равен 0.

Альтернативная формулировка (не рекомендуется):

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

double min(double a[], int n)
{
    if ((a == NULL) || (n <= 0))
    {
        return NAN;
    }
    else if (n == 1)
    {
        return array[0];
    }
    else
    {
        double x = a[0], y = min(&a[1], n-1);
        return x < y? x : y;
    }
}

Или рекурсивный двоичный поиск с использованием только пространства стека O (log₂ n):

inline double min2(double x, double y)
{
    return x < y? x : y;
}

double min(double a[], int n)
{
    return (a == NULL) || (n <= 0)? NAN
         : (n == 1)? a[0]
         : min2(min(a, n/2), min(a+n/2, n-n/2));
}

Или, во избежание проверки ошибок и в соответствии с принципом максимального ограничения:

inline double min2(double x, double y) { return x<y? x:y; }
double min(double a[], int n) { return n==1? a[0] : min2(min(a,n/2),min(a+n/2,n-n/2)); }

; -)

ответил Todd Lehman 17 SatEurope/Moscow2011-12-17T21:53:38+04:00Europe/Moscow12bEurope/MoscowSat, 17 Dec 2011 21:53:38 +0400 2011, 21:53:38

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132