Эффективный код C для поиска индекса столбца максимального числа в каждой строке матрицы

Question

Я написал код C, чтобы найти индекс столбца максимального числа (абсолютного максимума) в каждой строке матрицы nxn. Однако есть условие! Если индекс столбца максимального числа в текущей строке совпадает с одним из предыдущих строк, программа должна пропустить этот индекс и найти следующий максимум в этой строке.

Мой код работает нормально, но главное - производительность. К сожалению, мне пока не удалось распараллелить код с использованием OpenMP из-за зависимостей. Я действительно ценю, если вы можете помочь улучшить производительность моего кода. Заранее спасибо.

Вот код:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
#include <limits.h>

int main ( unsigned long int argc, char *argv[] )
{

    int n = 3;      
    //double A[9] = {1,2,3,4,5,6,7,8,9}; //output: ind_col[1,..,3] = 2,1,0  max_val[1,..,3] = 3,5,7
    double A[9] = {1,3,2,4,6,5,7,8,9}; //output: ind_col[1,..,3] = 1,2,0    max_val[1,..,3] = 3,5,7

    /* ind_col is 1xn array that contains the column index of abs. max number for each row */
    int *ind_col = NULL; 
    ind_col = (int*) calloc(n,sizeof(int)); 


    /* max_val is 1xn array that contains the abs. max number for each row */
    double *max_val = NULL;  
    max_val = (double*) calloc(n,sizeof(double)); 

    int i,j,k,rep = 0;      

    for(i=0; i<n; i++){       
        for(j=0; j<n; j++) {         

            if ( (fabs(A[i*n+j]) < max_val[i]) ) continue;  // if a new max is found, do...                      

            for(k=0; k<i; k++) if (ind_col[k] == j) rep = 1; // check if the same column index was not previously used

            if (rep != 1) {    // if this is a new column index save it              
                max_val[i] = fabs(A[i*n+j]);              
                ind_col[i] = j;
            }

            rep = 0;
        }   
    }       

    for(i=0; i<n; i++) printf("ind_col[%i] = %i , val = %f\n", i, ind_col[i], A[i*n+ind_col[i]]);}            

}

Answer 1

Это окончательный код.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
#include <limits.h>



unsigned *Find_Pivot(double *A,unsigned n)
{

unsigned *ind_col ;
unsigned *mark;
unsigned irow,jcol;

ind_col = calloc(n,sizeof *ind_col);
mark = calloc(n, sizeof *mark);

for(jcol=0; jcol<n; jcol++) { ind_col[jcol] = n; } // sentinel
for(jcol=0; jcol<n; jcol++) { mark[jcol] = n; } // sentinel

double max = 0;
double zabs = 0;

for(irow=0; irow<n; irow++){   
  max = 0;
  for(jcol=0; jcol<n; jcol++) {         
    zabs = fabs(A[irow*n+jcol]) ;
    if (zabs < max) continue;  // no new max is found
    if (mark[jcol] < irow)  continue;// check if the same column index was used by a previous row

    if (jcol > 0) {          //undo previous submax        
        unsigned ocol = ind_col[irow] ;
        if (ocol <jcol) mark[ocol] = n; // reset sentinel ...                           
    }

    mark[jcol] = irow; // mark our row index in here ...    
    max = zabs;
    ind_col[irow] = jcol;
  }
}

free(mark);
return ind_col;

}



int main ( unsigned long int argc, char *argv[] )
{


unsigned *ind_col;

int n = 3;
double A[9] = {6,3,2,9,8,8,10,8,9};


ind_col = Find_Pivot(A, n);

int i;
for (i=0;i < n;i++) printf("%i:=%i\n", i, ind_col[i]);

return 0;


}

Answer 2

Используйте битовую маску, чтобы отметить номера используемых столбцов:

[вы также можете использовать простой индикаторный массив символов или целых]

---

#define ZBITS (CHAR_BIT*sizeof zzz[0])

#define ZTEST(z) (zzz[z/ZBITS] & (1u<< (z%ZBITS)))
#define ZSET(z) zzz[z/ZBITS] |= (1u<< (z%ZBITS))

// size of A is nxn

/* ind_col is 1xn array that contains the column index of abs. max number for each row */
int *ind_col ; 
ind_col = calloc(n,sizeof *ind_col);    


/* max_val is 1xn array that contains the abs. max number for each row */
double *max_val ;  
unsigned *zzz;

max_val = calloc(n,sizeof  *max_val);
zzz = calloc(1+n/ZBITS, sizeof *zzz);               

int i,j;

for(i=0; i<n; i++){ 
  for(j=0; j<n; j++) { 
    double zabs;

    zabs = fabs(A[i*n+j]) ;
    if ( zabs < max_val[i]) continue;  // no new max is found
    if (ZTEST(j)) continue; // check if the same column index was previously used

    ZSET(j); // close the door ...
    max_val[i] = zabs;             
    ind_col[i] = j;
    }

  }

free(zzz);

#undef ZBITS
#undef ZTEST
#undef ZSET

---

UPDATE (2):

улучшена? версия с использованием массива mark для исключения:

---

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

unsigned *ihaveaname(double *A,unsigned n)
{

unsigned *ind_col ;
double *max_val ;
unsigned *mark;
unsigned irow,jcol;

ind_col = calloc(n,sizeof *ind_col);
max_val = calloc(n,sizeof  *max_val);
mark = calloc(n, sizeof *mark);

for(jcol=0; jcol<n; jcol++) { ind_col[jcol] = n; } // sentinel
for(jcol=0; jcol<n; jcol++) { mark[jcol] = n; } // sentinel
for(jcol=0; jcol<n; jcol++) { max_val[jcol] = 0.0; }

for(irow=0; irow<n; irow++){
  for(jcol=0; jcol<n; jcol++) {
    double zabs;

    zabs = fabs(A[irow*n+jcol]) ;
    if (zabs < max_val[irow]) continue;  // no new max is found
    if (mark[jcol] < irow) { // check if the same column index was used by a previous row
                // fprintf(stderr,"[Skip col%u row%u]", jcol,irow);
                continue;
                }
    if (jcol > 0) { //undo previous submax
                unsigned ocol;
                ocol = ind_col[irow] ;
                if (ocol <jcol) {
                        mark[ocol] = n; // reset sentinel ...
                        // fprintf(stderr,"[Undo ocol%u]", ocol);
                        }
                }

    // fprintf(stderr,"[Mark col%u <- row%u]", jcol,irow);
    mark[jcol] = irow; // mark our row index in here ...

    max_val[irow] = zabs;
    ind_col[irow] = jcol;
    }

    // fprintf(stderr,"Max[%u] = %f\n", irow,max_val[irow]);
  }
free(mark);
free(max_val);
return ind_col;
}

int main(void)
{
unsigned uu, *uuu;

double array[9]={
        1,2,3,
        2,3,1,
        3,1,2};

uuu = ihaveaname(array, 3);

for (uu=0;uu < 3;uu++){
        printf("%u:=%u\n", uu, uuu[uu]);
        }
return 0;
}