最有效的方式来获得在C多维数组的列 [英] Most efficient way to get columns of a multi dimensional array in C

问题描述

我试图创造C的矩阵数据结构，我有一个结构，有一个二维空指针数组（大小是在堆动态定义），在这个结构中的部分货物（数据）。

I'm trying to create a matrix data structure in C. I have a struct and have a two dimensional void pointer array (size is dynamically defined at the heap) for the cargo part(data) in this struct.

由于列索引，我想在一维数组此列的值。这是很容易这与一个为或while循环。但是，如果行中该矩阵的数量为N，则它会采取O（N）时间为得到一个列向量。我可以像memcpy和如何内存操作做到这一点更有效？否则，我怎么能提高性能（我的数据是pretty结构，我需要这些信息存储在某种矩阵）。

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

推荐答案

如果你想在你的矩阵中的数据复制，你不能做到这一点，在不到O（N）时间无论是一行或一列，除了小N，其中硬件功能可能有帮助。

If you want to copy the data in your matrix, you can't do it in less than O(N) time whether it is a row or a column, except for small N where hardware features might help.

不过，如果你的矩阵是不可变的，你可以使用雾里看花得到具有一个单独的列向量的错觉。

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

以下code是笔直的答案文本框中键入和甚至还没有被编译。使用您自己的风险！

您矩阵型被定义为一个结构从而

Your matrix type is defined as a struct thus:

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 brand new matrix (I've left out all the error handling to make it simpler).

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 no error handling, eg bounds 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 needed)

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;
}

要在另一个矩阵列创建一个新的矩阵：

To create a new matrix from a column in another matrix:

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);
}

如果你想要可变的矩阵，任何时候你修改元素，检查引用计数，如果大于1，修改它（递减的老dataRef引用计数）之前复制DataRef，否则修改​​dataRef到位。

If you want mutable matrices, any time you modify an element, check the refCount and if it is greater than 1, copy the DataRef before modifying it (decrement the refCount on the old dataRef), otherwise modify the dataRef in place.

现在上面使用大量mallocs的，因此可能比幼稚的做法对小矩阵效率较低。但是，可以维护未使用DataRef结构和矩阵结构的列表，而不是他们释放完成后，把它们放在空闲列表上。当分配新的，从空闲列表获取结构，除非它们是空的。通过这种方式，获得该重新$ P $矩阵psents现有矩阵的列将往往需要一定的时间。

Now the above uses lots of mallocs and so might be less efficient than the naive implementation for small matrices. However, you could maintain a list of unused DataRef structs and Matrix structs and instead of freeing them when you are done, put them on the free list. When allocating new ones, get the structs from the free lists unless they are empty. That way, getting a matrix that represents a column of an existing matrix will often take constant time.

这篇关于最有效的方式来获得在C多维数组的列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！