Функция мин / макс 1Д массив в Си / Си++


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

Это "лучшие" возможности реализации функции 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;
}


Комментарии
3 ответа

Это не совсем лучшие. Есть некоторые вещи, ИМХО, что мешает его эффективности и полезности.

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

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

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

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;
}

19
ответ дан 3 октября 2011 в 05:10 Источник Поделиться

Вы можете использовать SSE2/SSE3 определяться minps / pminsd или соответствующий набор инструкций для процессора/architectoure, поскольку он поддерживается непосредственно в GCC / компилятор MASM / TASM уже (в случае ассемблера MASM или TASM не поддерживает такой поддержкой SSE2/SSE3 набор инструкций есть .Inc файлы для создания макросов, имитирующие наборы инструкций в интернете для MASM), создать .Файл obj ваших любимых линкер потом связать его, как обычно, и ты любимый IDE. Вы получите от 4х до 16х прирост производительности по сравнению с традиционными "классический алгоритм". Это зависит от размера данных (старые компиляторы угощение в два раза не в IEEE формате, примерно как поплавок в нескольких конфигурациях, на 16х систем, в частности, означает, двойные 32-битные структуры данных, а не 64-битная структура данных, в современных языках это коррелируется с "двойной" и "двойной" структуры данных, соответственно)

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

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

Образец с помощью 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;
}

5
ответ дан 4 октября 2011 в 11:10 Источник Поделиться

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

Ок, вы хотите надежный и быстрый. Если это было необходимо в производстве код, я бы, наверное, написать так:

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;
}

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

Аргумент проверяющих: это допустимо, чтобы вызвать эту функцию с размером от 0? Если так, то у вас также есть ошибка, если вы начинаете с Вэл = массив[0] , когда размер равен 0, потому что вы можете быть значение памяти в зависимости от места проживания указывает. По крайней мере, это логически некорректно рассматривать массив[0] , когда размер равен 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₂ Н) стекового пространства:

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)); }

;-)

3
ответ дан 17 декабря 2011 в 05:12 Источник Поделиться