How to find a subset of a 2d array by selecting rows and columns in c?

Question

In an (m by n) array stored as double *d (column major), what is the fastest way of selecting a range of rows and or columns:

double *filter(double *mat, int m, int n, int rows[], int cols[]);

invoked as:

double *B;
int rows[]= {1,3,5}; int cols[]={2,4};
B = filter(A, 5, 4, rows, cols);

which is expected to return a 3-by-2 subset of A consisting of elements (1,2), (1,4), (3,2)...

Answer 1

I'm pretty sure that m and n should be the dimension of the new array (i.e. m should be the number of items of rows and n should be the number of items in cols) and not the dimension of the source array as seems to be the case in your example because a) you don't need to know the dimension of the source array if you already know which indices to pick from it (and are presumably allowed to assume that those will be valid) and b) if you don't know the size of rows and columns they are useless as you can't iterate over them.

So under that assumption the algorithm could look like this:

• Allocate memory for an m x n array
• For each i in 0..m, j in 0..n
• • B[i,j] = A[ rows[i], cols[j] ];

Answer 2

c provides no native support for this, so you'll have to find a library that supports it, or define it by hand.

pseudocode:

a=length of rows     // no built in c functionality for this either, 
b=length of cols     // use a sentinel, or pass to the function
nmat = allocate (sizeof(double)*a*b) on the heap
for (i=0; i<a; ++i)
   for (j=0; j<b; ++j)
      // Note the column major storage convention here (bloody FORTRAN!)
      nmat[i + j*b] = mat[ rows[i] + cols[j]*n ];
return nmat
// caller responsible for freeing the allocated memeory

I've commented on the two big problems you face.