如何交换二维数组的行

Question

我第一次遇到这种情况，我想知道是否有任何“最佳方法”或至少是一个好的做法。

如何交换二维数组的行？
例如：

FROM   -->   TO
1 1 1        2 2 2
2 2 2        1 1 1
3 3 3        3 3 3

使用memcpy?
将两行的元素一一交换感谢老好人for?
有一个指向 int 的动态分配指针数组（而不是二维数组）并交换指针？
其他方式？

Answer 1

IMO memcpy 是最好的方法通用函数：

void *swapRows(void *array, size_t rows, size_t columns, size_t row1, size_t row2, size_t elemsize)
{
    size_t rowsize = columns * elemsize;
    unsigned char *carray = array;
    if(row1 != row2 && row1 < rows && row2 < rows)
    {
        void *tempRow = malloc(rowsize);
        if(tempRow && array)
        {
            size_t row1offset = row1 * elemsize * columns;
            size_t row2offset = row2 * elemsize * columns;
            memcpy(tempRow, carray + row1offset, rowsize);
            memcpy(carray + row1offset, carray + row2offset, rowsize);
            memcpy(carray + row2offset, tempRow, rowsize);
        }
        free(temprow)
    }
    return array;
}

和一些原始基准

void __attribute__((noinline)) *swapRows(volatile void *array, size_t rows, size_t columns, size_t row1, size_t row2, size_t elemsize)
{
    size_t rowsize = columns * elemsize;
    unsigned char *carray = (void *)array;
    if(row1 != row2 && row1 < rows && row2 < rows)
    {
        void *tempRow = malloc(rowsize);
        if(tempRow && array)
        {
            size_t row1offset = row1 * elemsize * columns;
            size_t row2offset = row2 * elemsize * columns;
            memcpy(tempRow, carray + row1offset, rowsize);
            memcpy(carray + row1offset, carray + row2offset, rowsize);
            memcpy(carray + row2offset, tempRow, rowsize);
        }
        free(tempRow);
    }
    return array;
}

#define SWAPROWS(type, array, rows, columns, r1, r2) \
    do {\
            for(size_t c = 0; c < columns; c++)\
            {   \
                type tmp = array[r1][c];\
                array[r1][c] = array[r2][c];\
                array[r2][c] = tmp; \
            }\
    }while(0)

int main(void)
{
    clock_t start, end;
    volatile int array[5][2000];
    double time_spent;

    for (size_t row = 0; row < 5; row++)
        for(size_t c = 0; c < 2000; c++)
            array[row][c] = row;
    start = clock();    
    for(int i = 0; i < 1000; i++)
        SWAPROWS(int, array, 5, 2000, 2, 3);
    end = clock();  
    time_spent = (double)(end - start) / CLOCKS_PER_SEC;   
    printf("%f\n", time_spent);
    start = clock();    
    for(int i = 0; i < 1000; i++)
        swapRows(array, 5, 2000, 2, 3, sizeof(int));
    end = clock();  
    time_spent = (double)(end - start) / CLOCKS_PER_SEC;   
    printf("%f\n", time_spent);
}

https://godbolt.org/z/3nc1br

结果

Program returned: 0
Program stdout

0.001735
0.000388

Answer 2

Using memcpy?

如果数据是行优先的，这意味着每一行都是一个连续的内存块，那么这可能是一个很好的工具。一个完全通用的解决方案需要行大小的一些上限，以避免分配巨大的临时行并扰乱 L1 缓存（16 kB 可能是合理的最大复制块大小）。

Swapping the elements of the two rows one by one thanks to the good old for?

这对于出于其他原因必须按列优先顺序存储的小行或数据非常有用。

Having an array of dynamically allocated pointers to int (instead of the 2D array) and swap the pointers?

当然值得进行基准测试，但除非行交换是您的主要用例之一，否则这可能会降低其他操作的性能，从而适得其反。

还有一种选择：

以行优先顺序连续存储数据，但不是移动行，而是保留一个单独的行索引数组，其中实际存储每一行。在您的示例中，这将是 [1, 0, 2]。这将使行移动像指针解决方案一样高效，同时不会减慢其他操作，如分配、释放、求和等。

Answer 3

我们真的想就地交换或生成一个元素转置的新数组吗？

如果您尝试就地交换，那么数组是方形的吗？现在它变得非常有趣！我忽略了这一点，但是有一些有趣的算法可以有效地获取实际使用第二个聚合维度查看的一维数组，并将其就地转置到相同的一维数组存储中。

但是如果你只是做方阵或者复制，那么：

如果值是简单的整数，那么 memcpy 就太过分了——您还不如简单地通过一个临时值来分配这些值。没有 memcpy 可以有效流式传输的长序列。

如果元素大于整数，那么使数组成为指针数组会使转置代码变得容易，当你只是复制指针时，但你可能会在代码中的其他地方支付额外费用来管理所指向的数据到，以及每次访问数据时额外的取消引用。转置可能不是您代码中最慢的部分！

如何交换二维数组的行

How to swap rows of 2D array

c

swap

multidimensional-array