c - 如何在 C 语言中转置二维矩阵？

Question

我正在尝试就地转置 2D 矩阵 (10x10):

for (a = 0; a < 10; a++) {
    for (b = 0; b < 10; b++) {
        tmp = matrix[a][b];
        matrix[b][a] = matrix[a][b];
        matrix[a][b] = tmp;
    }
}

如果我可以将内部 for 语句的起始值 'b' 增加 1，它就可以正常工作。

但是，当循环一次时，变量的值设置为0。这是很自然的。

有没有办法在循环运行后增加内部 for 循环的起始值 'b'？

我真的很想解决这个问题。

你能用全局变量或任何其他方法来解决这个问题吗？

Answer 1

您的交换代码不正确:您应该先覆盖保存的值。

此外，当b == a时，必须停止内层循环，否则会交换两次值，导致转置失败。

这是更正后的版本:

/* swap values on either side of the first diagonal */
for (a = 1; a < 10; a++) {
    /* stop the inner loop when b == a */
    for (b = 0; b < a; b++) {
        int tmp = matrix[a][b];
        matrix[a][b] = matrix[b][a];
        matrix[b][a] = tmp;
    }
}

这个简单的算法不是大型矩阵的最佳缓存，尤其是对于 2 大小的幂。已经为 in place matrix transpostion 开发了更精细的算法.

例如，这里是 1024x1024 矩阵的基准，将朴素算法与高级递归方法进行比较:

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

#define SIZE 1024

static int mat[SIZE][SIZE];

void initialize_matrix(int matrix[SIZE][SIZE]) {
    int a, b, x = 0;
    for (a = 0; a < SIZE; a++) {
        for (b = 0; b < SIZE; b++) {
            mat[a][b] = x++;
        }
    }
}

int check_transpose_matrix(int matrix[SIZE][SIZE]) {
    int a, b, x = 0;
    for (a = 0; a < SIZE; a++) {
        for (b = 0; b < SIZE; b++) {
            if (mat[b][a] != x++)
                return 1;
        }
    }
    return 0;
}

void naive_transpose(int matrix[SIZE][SIZE]) {
    /* swap values on either side of the first diagonal */
    for (int a = 1; a < SIZE; a++) {
        /* stop the inner loop when b == a */
        for (int b = 0; b < a; b++) {
            int tmp = matrix[a][b];
            matrix[a][b] = matrix[b][a];
            matrix[b][a] = tmp;
        }
    }
}

#define THRESHOLD  4

void transpose_tile(int row, int col, int size, int matrix[SIZE][SIZE]) {
    if (size > THRESHOLD) {
        transpose_tile(row, col, size / 2, matrix);
        transpose_tile(row, col + size / 2, size / 2, matrix);
        transpose_tile(row + size / 2, col, size / 2, matrix);
        transpose_tile(row + size / 2, col + size / 2, size / 2, matrix);
    } else {
        for (int a = 0; a < size; a++) {
            for (int b = 0; b < size; b++) {
                int tmp = matrix[row + a][col + b];
                matrix[row + a][col + b] = matrix[col + b][row + a];
                matrix[col + b][row + a] = tmp;
            }
        }
    }
}

void transpose_tile_diag(int pos, int size, int matrix[SIZE][SIZE]) {
    if (size > THRESHOLD) {
        transpose_tile_diag(pos, size / 2, matrix);
        transpose_tile(pos, pos + size / 2, size / 2, matrix);
        transpose_tile_diag(pos + size / 2, size / 2, matrix);
    } else {
        /* swap values on either side of the first diagonal */
        for (int a = 1; a < size; a++) {
            /* stop the inner loop when b == a */
            for (int b = 0; b < a; b++) {
                int tmp = matrix[pos + a][pos + b];
                matrix[pos + a][pos + b] = matrix[pos + b][pos + a];
                matrix[pos + b][pos + a] = tmp;
            }
        }
    }
}

void advanced_transpose(int matrix[SIZE][SIZE]) {
    transpose_tile_diag(0, SIZE, matrix);
}

int main(int argc, char *argv[]) {
    clock_t t_min;

    initialize_matrix(mat);
    naive_transpose(mat);
    if (check_transpose_matrix(mat)) {
        printf("naive_transpose failed!\n");
        return 1;
    }
    /* benchmark naive algorithm */
    t_min = 0;
    for (int i = 0; i < 100; i++) {
        clock_t t = clock();
        naive_transpose(mat);
        t = clock() - t;
        if (i == 0 || t_min > t)
            t_min = t;
    }
    printf("naive: %.3fms\n", t_min * 1000.0 / CLOCKS_PER_SEC);

    initialize_matrix(mat);
    advanced_transpose(mat);
    if (check_transpose_matrix(mat)) {
        printf("advanced_transpose failed!\n");
        return 1;
    }
    /* benchmark advanced algorithm */
    t_min = 0;
    for (int i = 0; i < 100; i++) {
        clock_t t = clock();
        advanced_transpose(mat);
        t = clock() - t;
        if (i == 0 || t_min > t)
            t_min = t;
    }
    printf("advanced: %.3fms\n", t_min * 1000.0 / CLOCKS_PER_SEC);

    return 0;
}

我 5 岁的 macbook 上的输出:

naive: 7.299ms
advanced: 1.157ms