c - 高效的 C 代码，用于查找每个矩阵行中最大数的列索引

Question

我编写了一个 C 代码来查找 nxn 矩阵每一行中最大数(绝对最大值)的列索引。但是，有一个条件!如果当前行中 max number 的列索引与前面的行之一相同，则程序应跳过该索引并找到该行中的下一个 max。

我的代码工作正常，但性能是主要问题。不幸的是，由于依赖关系，到目前为止，我未能成功使用 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

使用位掩码标记使用的列数:

[您也可以使用一个简单的字符或整数指标数组]

---

#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

---

更新(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;
}