Как я могу транспонировать 2D-матрицу на месте в C? - PullRequest
Новая
       39

Как я могу транспонировать 2D-матрицу на месте в C?

0 голосов
/ 28 сентября 2018

Я пытаюсь переставить 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;
    }
}

Если я смогу увеличить начальное значение 'b' внутреннего оператора for на 1, он работает нормально.

Однако, когда вращается один цикл, значение переменной устанавливается на 0.Это очень естественно.

Есть ли способ увеличить начальное значение 'b' внутреннего for цикла после выполнения цикла?

Я действительно хочу решить эту проблему.

Можете ли вы использовать глобальные переменные или любой другой способ решения этой проблемы?

1 Ответ

0 голосов
/ 29 сентября 2018

Ваш код подкачки неверен: сначала вы должны перезаписать сохраненное значение.

Кроме того, вы должны остановить внутренний цикл при 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 размеров.Более сложные алгоритмы были разработаны для вместо транспонирования матрицы .

Например, вот эталонный тест для матриц 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
...