C语言 为“矩形2d阵列”动态分配连续内存，无需使用VLA

jaxagkaj  于 2022-12-02  发布在  其他
关注(0)|答案(5)|浏览(139)

这是一个有很多答案的问题，但没有一个做具体的事情。
我试着查看所有这些帖子-123456789-每次的解决方案要么是使用VLA，要么是使用固定维度的普通数组，要么是使用指针到指针。
我要分配的是：

  • 动态（在运行时使用变量集）
  • 矩形（“二维数组”）（我不需要锯齿形的数组。而且我想无论如何都不可能做到。）
  • 连续内存（在#8和其他一些帖子中，人们说指针到指针是坏的，因为堆填充和碎片）
  • 没有vla（我听说他们是魔鬼，并始终避免他们，不要与人谁建议使用他们在任何情况下）。

所以，如果有一篇文章我跳过了，或者没有读得足够透彻，符合这些要求，请给我指出来。
否则，我会请你教育我这一点，告诉我这是否可能，如果可能，如何做到这一点。

c

5条答案

按热度按时间
qyuhtwio

qyuhtwio1#

您可以将连续的2D数组动态配置为

int (*arr)[cols] = malloc( rows * sizeof (int [cols]) );

然后访问元素arr[i][j]。
如果您的编译器不支持VLA，则cols必须是常量表达式。

赞(0）分享  回复(0）举报  2022-12-02
dnph8jn4

dnph8jn42#

初步评估

  • 没有vla（我听说他们是魔鬼，并始终避免他们，不要与人谁建议使用他们在任何情况下。

如果你想让你的代码与微软的C编译器一起工作，VLA是一个问题，因为微软一直拒绝实现VLA支持，即使C99是当前的语言标准，其中VLA支持是强制性的。一般来说，我会建议如果可以的话，完全避免使用微软的C编译器，但我不会建议避免使用那些给你不同建议的人。
当你声明一个VLA类型的自动对象而不管理最大维时，VLA也是一个潜在的问题。尤其是当维来自用户输入时。这会产生程序崩溃的风险，除非首先避免这种情况，否则很难在开发时测试或减轻这种风险。
但称VLA为“魔鬼”充其量是过于戏剧化的，我建议，任何实际告诉你“不要与建议在任何场景中使用它们的人交谈”的人一定不相信你能理解所涉及的问题或亲自评估它们。特别是，指向VLA的指针是一种很好的方式来解决你除了“没有VLA”之外的所有观点，并且除了缺乏（主要是）微软的支持之外，它们没有特别的技术问题。对这些的支持将在C2 X中再次成为强制性的，C2 X是下一个C语言规范，尽管对一些其他形式的VLA使用的支持将仍然是可选的。

您的要求

如果数组类型的任何维度不是由整数常量表达式给出的，那么根据定义，该类型是可变长度数组类型。如果数组类型的任何维度（除了第一个维度）不是由整数常量表达式给出的，那么不使用VLA就不能表达相应的指针类型。
因此，如果你想要一个连续分配的多维数组（数组的数组），并且在运行时为它选择除第一个维度之外的任何维度，那么必须涉及一个VLA类型。动态分配这样的对象效果很好，除了缺少某些编译器的支持（这是一个不可忽视的考虑因素）之外，几乎没有什么缺点。它看起来像这样：

void do_something(size_t rows, size_t columns) {
    int (*my_array)[columns];  // pointer to VLA

    my_array = malloc(rows * sizeof(*my_array));

    // ... access elements as my_array[row][col] ...
}

您应该在问题中提到的一些问答中看到过类似的内容。

如果这是不可接受的，那么你需要选择给予哪些其他要求。我建议“多维”部分。相反，分配（有效地）一个一维数组，并通过在访问时执行适当的索引计算来像使用二维数组一样使用它。因为它与编译器为多维数组自动设置的内容非常接近。您可以通过创建一个宏来帮助计算，

#define ELEMENT_2D(a, dim2, row, col) ((a)[(row) * (dim2) + (col)])

void do_something(size_t rows, size_t columns) {
    int *my_array;

    my_array = malloc(rows * columns * sizeof(*my_array));

    // ... access elements as ELEMENT_2D(my_array, columns, row, col) ..
}

或者，你可以给予连续分配而使用指针数组。这是那些不了解数组、指针和/或动态分配的人通常会做的事情，尽管有一些应用，特别是对于指向字符串的指针数组，这种形式的缺点主要是相对于连续分配的应用程序类型，其中人们想要一个对象，他们认为是一个2D数组。

赞(0）分享  回复(0）举报  2022-12-02
kx7yvsdv

kx7yvsdv3#

通常分配指针数组，然后将内存分配给每个指针。
分配一个大的连续内存块。分配一个指针数组，并从连续内存块中分配地址。

#include <stdio.h>
#include <stdlib.h>

int **contiguous ( int rows, int cols, int **memory, int **pointers) {
    int *temp = NULL;
    int **ptrtemp = NULL;
    // allocate a large block of memory
    if ( NULL == ( temp = realloc ( *memory, sizeof **memory * rows * cols))) {
        fprintf ( stderr, "problem memory malloc\n");
        return pointers;
    }

    *memory = temp;
    // allocate pointers
    if ( NULL == ( ptrtemp = realloc ( pointers, sizeof *pointers * rows))) {
        fprintf ( stderr, "problem memory malloc\n");
        return pointers;
    }

    pointers = ptrtemp;

    for ( int rw = 0; rw < rows; ++rw) {
        pointers[rw] = &(*memory)[rw * cols]; // assign addresses to pointers
    }

    // assign some values
    for ( int rw = 0; rw < rows; ++rw) {
        for ( int cl = 0; cl < cols; ++cl) {
            pointers[rw][cl] = rw * cols + cl;
        }
    }
    return pointers;
}

int main ( void) {
    int *memory = NULL;
    int **ptrs = NULL;
    int rows = 20;
    int cols = 17;

    if ( ( ptrs = contiguous ( rows, cols, &memory, ptrs))) {
        for ( int rw = 0; rw < rows; ++rw) {
            for ( int cl = 0; cl < cols; ++cl) {
                printf ( "%3d ", ptrs[rw][cl]);
            }
            printf ( "\n");
        }

        free ( memory);
        free ( ptrs);
    }
    return 0;
}
赞(0）分享  回复(0）举报  2022-12-02
xwbd5t1u

xwbd5t1u4#

假设您需要一个大小为W x H的二维数组，其中包含int s（其中H是行数，W是列数）。
然后，您可以执行以下操作：
分配方式：

int * a = malloc(W * H * sizeof(int));

位置（i，j）处的访问元素：

int val = a[j * W + i];
a[j * W + i] = val;

整个数组将占用一个连续的内存块，并且可以动态分配（没有VLA）。作为一个连续的内存块比指针数组具有优势，因为[潜在地]更少的缓存未命中。
在这样的数组中，术语“stride”指的是一行到另一行之间的偏移量。如果你需要使用填充，例如，确保所有行都从某个对齐的地址开始，你可以使用大于W的stride。

赞(0）分享  回复(0）举报  2022-12-02
7y4bm7vi

7y4bm7vi5#

我做了一个基准间：

  • 指针数组的经典指针指向单独malloc的内存
  • 一个指针指向连续内存，使用a[x * COLS + y]访问
  • 两者的混合-指向指向已分配malloc的连续内存的指针数组的指针
    TL;DR：

第二个看起来比其他的快2-12%，其他的在性能上是类似的。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ROWS    100
#define COLS    100
#define LOOPS   100
#define NORMAL  0
#define SINGLE  1
#define HYBRID  2

int **x_normal;                                             /* global vars to make it more equal */
int *y_single;
int *z_hybrid_memory;
int **z_hybrid_pointers;
int copy_array[ROWS][COLS];

void x_normal_write(int magic) {                            /* magic number to prevent compiler from optimizing it */
    int i, ii;
    for (i = 0; i < ROWS; i++) {
        for (ii = 0; ii < COLS; ii++) {
            x_normal[i][ii] = (i * COLS + ii + magic);
        }
    }
}

void y_single_write(int magic) {
    int i, ii;
    for (i = 0; i < ROWS; i++) {
        for (ii = 0; ii < COLS; ii++) {
            y_single[i * COLS + ii] = (i * COLS + ii + magic);
        }
    }
}

void z_hybrid_write(int magic) {
    int i, ii;
    for (i = 0; i < ROWS; i++) {
        for (ii = 0; ii < COLS; ii++) {
            z_hybrid_pointers[i][ii] = (i * COLS + ii + magic);
        }
    }
}

void x_normal_copy(void) {
    int i, ii;
    for (i = 0; i < ROWS; i++) {
        for (ii = 0; ii < COLS; ii++) {
            copy_array[i][ii] = x_normal[i][ii];
        }
    }
}

void y_single_copy(void) {
    int i, ii;
    for (i = 0; i < ROWS; i++) {
        for (ii = 0; ii < COLS; ii++) {
            copy_array[i][ii] = y_single[i * COLS + ii];
        }
    }
}

void z_hybrid_copy(void) {
    int i, ii;
    for (i = 0; i < ROWS; i++) {
        for (ii = 0; ii < COLS; ii++) {
            copy_array[i][ii] = z_hybrid_pointers[i][ii];
        }
    }
}

int main() {
    int i;
    clock_t start, end;
    double times_read[3][LOOPS];
    double times_write[3][LOOPS];

    /* MALLOC X_NORMAL 1/2 */
    x_normal = malloc(ROWS * sizeof(int*));                 /* rows */
    for (i = 0; i < ROWS; i+=2) {                           /* malloc every other row to ensure memory isn't contignuous */
        x_normal[i] = malloc(COLS * sizeof(int));           /* columns for each row (1/2) */
    }
    
    /* MALLOC Y_SINGLE */
    y_single = malloc(ROWS * COLS * sizeof(int));           /* all in one contignuous memory */

    /* MALLOC Z_HYBRID */
    z_hybrid_memory = malloc(ROWS * COLS * sizeof(int));    /* memory part - with a big chunk of contignuous memory */
    z_hybrid_pointers = malloc(ROWS * sizeof(int*));        /* pointer part - like in normal */
    for (i = 0; i < ROWS; i++) {                            /* assign addresses to pointers from "memory", spaced out by COLS */
        z_hybrid_pointers[i] = &z_hybrid_memory[(i * COLS)]; 
    }

    /* MALLOC X_NORMAL 2/2 */
    for (i = 1; i < ROWS; i+=2) {                           /* malloc every other row to ensure memory isn't contignuous */
        x_normal[i] = malloc(COLS * sizeof(int));           /* columns for each row (2/2) */
    }

    /* TEST */
    for (i = 0; i < LOOPS; i++) {
        /* NORMAL WRITE */
        start = clock();
        x_normal_write(i);
        end = clock();
        times_write[NORMAL][i] = (double)(end - start);

        /* SINGLE WRITE */
        start = clock();
        y_single_write(i);
        end = clock();
        times_write[SINGLE][i] = (double)(end - start);

        /* HYBRID WRITE */
        start = clock();
        z_hybrid_write(i);
        end = clock();
        times_write[HYBRID][i] = (double)(end - start);

        /* NORMAL READ */
        start = clock();
        x_normal_copy();
        end = clock();
        times_read[NORMAL][i] = (double)(end - start);

        /* SINGLE READ */
        start = clock();
        y_single_copy();
        end = clock();
        times_read[SINGLE][i] = (double)(end - start);

        /* HYBRID READ */
        start = clock();
        z_hybrid_copy();
        end = clock();
        times_read[HYBRID][i] = (double)(end - start);
    }

    /* REPORT FINDINGS */
    printf("CLOCKS NEEDED FOR:\n\nREAD\tNORMAL\tSINGLE\tHYBRID\tWRITE\tNORMAL\tSINGLE\tHYBRID\n\n");
    for (i = 0; i < LOOPS; i++) {
        printf(
            "\t%.1f\t%.1f\t%.1f\t\t%.1f\t%.1f\t%.1f\n", 
            times_read[NORMAL][i], times_read[SINGLE][i], times_read[HYBRID][i],
            times_write[NORMAL][i], times_write[SINGLE][i], times_write[HYBRID][i]
        );
        /* USE [0] to get totals */
        times_read[NORMAL][0] += times_read[NORMAL][i];
        times_read[SINGLE][0] += times_read[SINGLE][i];
        times_read[HYBRID][0] += times_read[HYBRID][i];
        times_write[NORMAL][0] += times_write[NORMAL][i];
        times_write[SINGLE][0] += times_write[SINGLE][i];
        times_write[HYBRID][0] += times_write[HYBRID][i];
    }
    printf("TOTAL:\n\t%.1f\t%.1f\t%.1f\t\t%.1f\t%.1f\t%.1f\n",
        times_read[NORMAL][0], times_read[SINGLE][0], times_read[HYBRID][0],
        times_write[NORMAL][0], times_write[SINGLE][0], times_write[HYBRID][0]
    );
    printf("AVERAGE:\n\t%.1f\t%.1f\t%.1f\t\t%.1f\t%.1f\t%.1f\n",
        (times_read[NORMAL][0] / LOOPS), (times_read[SINGLE][0] / LOOPS), (times_read[HYBRID][0] / LOOPS),
        (times_write[NORMAL][0] / LOOPS), (times_write[SINGLE][0] / LOOPS), (times_write[HYBRID][0] / LOOPS)
    );

    return 0;
}

虽然这可能不是最好的方法，因为结果可能会被随机的东西污染--比如复制函数的源数组和目标数组的接近度（尽管读和写的数字是一致的。也许有人可以在这方面进行扩展）。

赞(0）分享  回复(0）举报  2022-12-02
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com