1

假设我有一个任意大小的整数值数组，它指定要分配的数组的每个维度（级别）的元素数，我如何在不诉诸递归的情况下分配数组？最好不要递归来避免堆栈溢出。

因此，例如，如何完成这样的功能：

template <typename Type>
void* allocMulti (int numDim, int* numElementsPerDim)
{
    // 'Type' if one-dimensional, should be 'void*' otherwise
    void* multiArray = new Type[numElementsPerDim[0]];
    // ...
    return multiArray;
}

我正在寻找一种通用算法，它可以涵盖没有直接内存访问的语言。

4

2 回答 2

1

如果数组实际上是一个矩阵（例如长度 AxB 而不是不同长度的数组列表），那么您可以分配一个长度为 A*B 的数组而不是长度为 A 的数组，其中每个位置都是指向数组的指针长度为 B。

这也可以提高性能，因为内存是连续的（更少的分页）。

您必须使用 a[y * B + x] 而不是 a[y][x] 访问每个单元格（假设 dim(a,0) = A 和 dim(a,1) = B.

我的 C++ 可能有点生疏，但是，我相信这种方法可能会奏效：

T* AllocateMatrix(int dims, int[] dimLengths)
{
    // Assert dims >= 1
    int length = dims[0];

    for (int d = 1; d < dims; d++)
        length *= dims[d];

    return new T[length];
}

*T AccessMatrix(T* matrix, int dims, int[] dimLengths, int[] pos)
{
    // Assert dims >= 1
    int p = pos[0];

    for (int d = 1; d < dims; d++)
    {
        p = p * dimLengths[d] + pos[d];
    }

    return &matrix[p];
}
于 2013-10-17T15:48:12.190 回答
0

这是一种方法：将数据值分配为一个块，然后将所有行(int *)作为一个块，然后将 的行(int **)作为一个块，等等。

a) 将所有数据值分配为一个块。如果nDim数组中有维度elementsPerDim，则有prod = product(elementsPerDim, nDim)数据值（您可以轻松计算），因此您需要分配：

int prod = product(elementsPerDim, nDim);
int * intblock = calloc(prod, sizeof(int));

b) 分配所有(int*). 它们的数量等于除最后一个维度之外的所有维度的乘积，因此您可以简单地product()使用 length 调用您的函数nDim-1。所以有product(elementsPerDim, nDim-1)这样的值，每个 size sizeof (int*)。让我们分配它们：

int npointers = product(elementsPerDim, nDim-1);
int ** ptrblock = calloc(npointers, sizeof (int *));

现在您必须初始化它们以指向上一步中的块。每个指针都有一个不重叠的elementsPerDim[nDim-2]整数块，如下所示：

int rowlength = elementsPerDim[nDim-2];
for (int i=0; i < npointers; i++)
    ptrblock[i] = & intblock[i * rowlength];   /* a.k.a. intblock + i*rowlength */

c) 向后迭代步骤 b，直到用完尺寸。即，使用此循环执行步骤 (b)：

void ** prev_block = (void **) ptrblock;
void ** curblock;

for (int d = nDim-2; d > 0; d--) {
    int npointers = product(elementsPerDim, d);
    curblock = calloc(npointers, sizeof (void **));

    int rowlength = elementsPerDim[d-1];
    for (int i=0; i < npointers; i++)
        curblock[i] = & prev_block[i * rowlength];

    prev_block = curblock;  /* get ready for the next round */
}

完成后，curblock将是一个指针数组，指向二级指针块，依此类推，直到整数块。您可以使用普通数组表示法来取消引用它们： ptrblock[3][2][15]等。

我可能在某处得到了一个索引，但这应该是算法。您会注意到这是在 C 中，并且使用void **而不是堆叠取消引用的数量。您确实说过您对算法感兴趣，而不是对高尔夫类型感兴趣......（只要所有指针在您的机器上具有相同的大小，它就应该工作。）

于 2013-10-17T15:58:54.200 回答