normalize 2d c array column или row

Мой вопрос прост: что является наиболее эффективным способом нормализации 2d-двоичного массива в c, так что его столбец (или его строка) суммируется с 1. Ниже приведен простой пример, иллюстрирующий Что я хочу сделать. Это нормально, чтобы изменить массив, чтобы либо нормализовать его строку, либо ее столбец, если это имеет значение. Я также открыт для использования библиотеки внешних линейных алгебр. Просто не уверен, с чего начать. Спасибо за любую помощь заранее!normalize 2d c array column или row

void normalize(double** array, int nrow) { 
    int i; 
    double sum = 0; 
    for(i = 0; i < nrow; i++) { 
     sum += array[i][0]; 
    } 
    for(i = 0; i < nrow; i++) { 
     array[i][0] /= sum; 
    } 
}

Кстати, это часть скрытого алгоритма динамического программирования модели Маркова, и это называется много раз. Поэтому я хочу сделать эту часть максимально эффективной.

источник

2013-07-23 qkhhly

наиболее эффективным по какой мере? Что не так с приведенным примером? Если я не смогу доказать, что мой ответ каким-то образом является самым эффективным возможным из когда-либо (вы даже не даете платформу и архитектуру, поэтому я не знаю, как кто-то может знать, что для вас наиболее эффективно), вы не хотите Это? – xaxxon

Ну, мне просто интересно, есть ли лучший способ сделать это, как измеряется временем, прошедшим. Код будет работать на linux и intel xeon. – qkhhly

хранить хэш любой возможной комбинации и искать нормализованное значение. Разумеется, для этого требуется почти бесконечное количество памяти. Я имею в виду, что, возможно, есть некоторые инструкции SIMD, которые вы можете использовать, но стоит ли так далеко (также, для чего требуется знание WHICH xeon platform)? Какова ваша цель? Почему, по-вашему, вам нужно что-то быстрее? Профилировали ли вы свой код? – xaxxon

Я не знаю, насколько ваш образец кода соответствует вашему приложению, но если вы перебираете такие строки, вы почти наверняка сталкиваетесь с проблемами кеша. Если я закодирую ваши циклы в строчном порядке и порядке столбцов, я вижу резкие различия в производительности.

С nrow=1000000 и ncol=1000, если я использую array[i][0], я получаю время работы около 1,9 с. Если я использую array[0][i], тогда он падает до 0,05 с.

Если вы можете перенести свои данные таким образом, вы должны увидеть большой прирост производительности.

#ifdef COL_MAJOR  

    array = (double **)malloc(nrow * sizeof(double *)); 
    for(i=0; i<nrow; i++) { 
     array[i] = (double *)malloc(ncol * sizeof(double)); 
     array[i][0] = i; 
    } 

    for(i=0; i<nrow; i++) { 
     sum += array[i][0]; 
    } 
    for(i=0; i<nrow; i++) { 
     array[i][0] /= sum; 
    } 

#else 

    array = (double **)malloc(ncol * sizeof(double *)); 
    for(i=0; i<ncol; i++) { 
     array[i] = (double *)malloc(nrow * sizeof(double)); 
    } 
    for(i=0; i<nrow; i++) { 
     array[0][i] = i; 
    } 

    for(i=0; i<nrow; i++) { 
     sum += array[0][i]; 
    } 
    for(i=0; i<nrow; i++) { 
     array[0][i] /= sum; 
    } 

#endif 

printf("%f\n", sum);

 
$ gcc -DCOL_MAJOR -O2 -o normed normed.c 
$ time ./normed 
499999500000.000000 

real 0m1.904s 
user 0m0.325s 
sys 0m1.575s 
$ time ./normed 
499999500000.000000 

real 0m1.874s 
user 0m0.304s 
sys 0m1.567s 
$ time ./normed 
499999500000.000000 

real 0m1.873s 
user 0m0.296s 
sys 0m1.573s 
$ gcc -O2 -o normed normed.c 
$ time ./normed 
499999500000.000000 

real 0m0.051s 
user 0m0.017s 
sys 0m0.024s 
$ time ./normed 
499999500000.000000 

real 0m0.050s 
user 0m0.017s 
sys 0m0.023s 
$ time ./normed 
499999500000.000000 

real 0m0.051s 
user 0m0.014s 
sys 0m0.022s 
$

источник

2013-07-23 04:49:38 Nigel

Я догадался, что будет разница между нормализацией строк и нормализацией столбцов, но спасибо за бенчмарк! – qkhhly

normalize 2d c array column или row

ответ

Смежные вопросы