Most efficient way to get multidimensional array columns in C

Question

I am trying to create a matrix data structure in C. I have a structure and there is a two-dimensional vector pointer array (the size is dynamically determined on the heap) for part of the load (data) in this structure.

Given the column index, I want to get the values ​​of this column in a one-dimensional array. This is easy with a single loop for or while. But if the number of rows in this matrix is ​​N, then it takes O (N) time to get the column vector. Can I do this more efficiently with memory operations like memcpy and how? Otherwise, how can I improve performance (my data is pretty structured, and I need to save this in some kind of matrix).

Answer 1

If you want to copy data into your matrix, you cannot do it in less than O (N) time, be it a row or column, with the exception of a small N, where hardware functions can be used.

However, if your matrices are immutable, you can use smoke and mirrors to create the illusion of having a separate column vector.

The code below is entered directly into the response text box and does not even compile. Use at your own risk!

The type of matrix is ​​defined as a structure in this way:

typedef struct 
{
    unsigned int refCount;  // how many Matrixes are referencing this data ref
    size_t lineWidth;       // number of doubles between element at row = n, col = 0 and row = n +1, col = 0 
    double* data;           // the actual data
} DataRef;

typedef struct
{
    size_t rows;            // num rows in matrix
    size_t cols;            // num cols in matrix
    size_t dataOffset;      // offset in doubles from the start of data of element at row = 0, col = 0
    DataRef* data;
} Matrix;

To create a completely new matrix (I skipped all error handling to simplify it).

Matrix* matrix_create(size_t rows, size_t cols, const double* values)
{
    Matrix* ret = calloc(1, sizeof *ret);
    ret->rows = rows;
    ret->cols = cols;
    ret->dataOffset = 0;
    ret->data = calloc(1, sizeof *dataRef);
    ret->data->lineWidth = cols;
    ret->data->data = allocateAndCopy(rows * cols, values); // mallocs a new block of doubles big enough for the values
    ret->data->refCount = 1;
    return ret;
}

To access an element (again, there is no error handling, such as border errors)

double matrix_elementAt(Matrix* matrix, size_t row, size_t col)
{
    size_t offset = matrix->dataOffset + row * matrix->data->lineWidth + col;
    return *(matrix->data->data + offset);
}

To create a new matrix from a rectangular region of another matrix (again, error handling is required)

Matrix* matrix_createFromRegion(Matrix* old, size_t startRow, size_t startCol, size_t rows, size_t cols)
{
    Matrix* ret = calloc(1, sizeof *ret);
    ret->rows = rows;
    ret->cols = cols;
    ret->dataOffset = old->dataOffset + startRow * old->dataLineWidth + startCol;
    ret->data = old->data;
    ret->data->refCount++;
    return ret;
}

:

Matrix* vector = matrix_createFromRegion(aMatrix, 0, colYouWant, matrix_numRows(aMatrix), 1);

void matrix_free(Matrix* aMatrix)
{
    if (aMatrix->data->refCount == 1)
    {
        free(aMatrix->data->data);
        free(aMatrix->data);
    }
    else
    {
        aMatrix->data->refCount--;
    }
    free(aMatrix);
}

, , , refCount , 1, DataRef ( refCount dataRef), dataRef .

mallocs , . , DataRef Matrix , , , . , , . , , , .

Answer 2

N, , , O (N). ; , N.

, , O (N).

, x[3][5] x+((3*num_cols)+5)*size_of_element 2D- . , , .

, - . . : , .

Answer 3

Borealid, O (N). , , , . memcpy .

Answer 4

:

• Do not use multidimensional arrays. They are inflexible pre-C99 (cannot change all sizes) and exclude the performance of efficient operations such as the following. Instead, just use a one-dimensional array and do the indexing arithmetic yourself.

• Now you can set the pointer srcto the first element of the column ( src = &matrix[row*ncols+col];) and copy the column with:for (i=0; i<nrows; i++, src+=ncols) dest[i] = *src;