매트릭스 분할 및 정복

Question

정사각형 매트릭스의 내부 캐시 - 무시 무시한 전치에 대한 위키 문서에 설명 된 접근 방식을 구현하고 있습니다.

https://en.wikipedia.org/wiki/In-place_matrix_transposition

알고리즘은 기본적으로 순환 후, 4 개로 분할 매트릭스 대각선을 따라있는 사분면 이항 이상과 이하 것들을 스왑. 실제 전치/교체는 행렬의 크기가 2 * 2 이하인 경우에만 발생합니다. 그렇지 않으면 다시 분할됩니다.

나는 세 가지 기능으로 분할 한

:

이 주어진 크기 N의 절차를 시작한다 :

void SmartTranspose(int A[row][col]) { 
    Transpose(A, 0, 0, N, N); 
} 

다음 :

void Transpose(int A[row][col], int x, int y, int w, int h) { 
    int Temp; 
    if ((w - x) * (h - y) <= 4){ 
     for (int row1 = x ; row1 < w -1 ; row1++) 
      for (int col1 = y + 1 ; col1 < h ; col1++) { 
       Temp = A[row1][col1]; 
       printf("transp: %d %d\n", A[row1][col1], A[col1] [row1]); 
       A[row1][col1] = A[col1][row1]; 
       A[col1][row1] = Temp; 
      } 
    } 
    else { 
     int halfh = h/2; 
     int halfw = w/2; 
     Transpose(A, x, y, halfw , halfh); 
     Transpose(A, x + halfw, y + halfh, w , h); 
     TransposeSwap(A, x + halfw, y, w, halfh, x, y + halfh, halfw , h); 
    } 
} 

그리고 마지막으로 :

void TransposeSwap(int A[row][col], int x, int y, int w, int h,int x1, int y1, int w1, int h1) { 
    int Temp; int row2 = x1; int col2 = y1; 
    if ((w - x) * (h - y) <= 4 && (w1 - x1) * (h1 - y1) <= 4) { 
     for(row1 = x; row1 < w; row1++) 
      for(col1 = y; col1 < h; col1++) 
      { 
       Temp = A[row1][col1] ; 
       A[row1][col1] = A[col1][row1]; 
       A[col1][row1] = Temp; 
      } 
    } 
    else { 
     printf("RECURSE"); 
     int halfh = h/2; 
     int halfw = w/2; 
     int halfh1 = h1/2; 
     int halfw1 = w1/2; 
     TransposeSwap(A, x, y, halfw, halfh, x1, y1, halfw1, halfh1); 
     TransposeSwap(A, x + halfw, y, w, h - halfh, x1, y1 + halfh1, halfw1, h1); 
     TransposeSwap(A, x , y + halfh, halfw, h, x1 + halfw1, y1, w1, halfh1); 
     TransposeSwap(A, x + halfw, y + halfh, w, h, x1 + halfw1, y1 + halfh1, w1, h1); 
    } 
} 

그러나, 나는 나의 논리가 어디서 잘못되었는지 보려고 고심하고있다.

편집 : 출력

Original matrix: 
1948037971 40713922 986050715 74181839 943010147 1060710730 
18590233 268906808 1966315840 1325423973 398061279 2047858287 
513589654 1727398080 2016821685 277200601 1611383116 2000671901 
228038281 1863845528 106517081 1934721636 745170263 1736525254 
224427632 687572994 1249224754 1497415191 537022734 1443375385 
1054092341 337577057 1484089307 2040143056 411758897 279615807 

Transposed matrix: 
1948037971 18590233 513589654 74181839 943010147 1060710730 
40713922 268906808 1727398080 1325423973 398061279 2047858287 
986050715 1966315840 2016821685 277200601 1611383116 2000671901 
228038281 1863845528 106517081 1934721636 745170263 1736525254 
224427632 687572994 1249224754 1497415191 537022734 1443375385 
1054092341 337577057 1484089307 2040143056 411758897 279615807 

의 예는 정확한 출력은 전치 행렬이어야한다.

편집 : 주요 기능 및 선언 :

int row = 40000 , col = 40000; 
static int A[40000][40000]; 
static int N[100] = {0}; 
void SmartTranspose(int A[row][col]); 
void Transpose(int A[row][col], int x, int y, int w, int h); 
void InitializeMatrix(int X[row][col]); 
void PrintMatrix(int X[row][col]); 

double pow(double x, double y); 
int matrix = 0; 
void TransposeSwap(int A[row][col], int x, int y, int w, int h,int x1, int y1, int w1, int h1); 

int main(){ 

srand(time(NULL)); 

double sizes = 0; 
int count = 0; 


for(sizes = 20; sizes < 30; sizes++) 
{ 
    N[count] = floor(pow(2, (sizes/9))); 
printf("N  %d\n", N[count]); 
    count++; } 


for (matrix = 0; matrix <= count -1 ; matrix++){ 


InitializeMatrix(A);  
printf("N %d\n",N[matrix]); 
printf("\nOriginal matrix: \n"); 




SmartTranspose(A); 

printf("E\n"); 

printf("\nTransposed matrix: \n"); 
PrintMatrix(A); 

}  
return 0; 
} 

전체 코드에 대한 링크 : https://jpst.it/QaBq

Answer 1

것은 다음 작업 알고리즘을 보여 내 시도이다. 행렬이 정사각형이기 때문에 필자는 몇 가지 함수 매개 변수를 제거했습니다. 또한 각 재귀 수준에서 알고리즘의 진행 상황을 표시하는 디버깅 코드를 남겨 두었습니다.

대각선이 주 대각선에있는 모든 부분 행렬을 전치 할 수 있습니다. 나는 100x100 배열의 0,0 코너에있는 9x9 매트릭스로 테스트했다.

#include <stdio.h> 

int dbglvl; 

void TransposeSwap(int dim, int A[dim][dim], int rs, int cs, int re, int ce) { 
    int Temp; 

    for (Temp = 0; Temp < dbglvl; Temp++) { 
     putchar('>'); 
    } 
    printf("TransposeSwap(dim=%d, rs=%d, cs=%d, re=%d, ce=%d)\n", dim, rs, cs, re, ce); 
    if (re - rs <= 2 && ce - cs <= 2) { 
     for (int r = rs; r < re; r++) 
      for (int c = cs; c < ce; c++) 
      { 
       printf("transp %d %d: %d %d\n", r, c, A[r][c], A[c][r]); 
       Temp = A[r][c] ; 
       A[r][c] = A[c][r]; 
       A[c][r] = Temp; 
      } 
    } 
    else { 
     int rm = (rs + re)/2; 
     int cm = (cs + ce)/2; 
     dbglvl++; 
     TransposeSwap(dim, A, rs, cs, rm, cm); 
     TransposeSwap(dim, A, rm, cs, re, cm); 
     TransposeSwap(dim, A, rs, cm, rm, ce); 
     TransposeSwap(dim, A, rm, cm, re, ce); 
     dbglvl--; 
    } 
    for (Temp = 0; Temp < dbglvl; Temp++) { 
     putchar('<'); 
    } 
    printf("TransposeSwap\n"); 
} 

void Transpose(int dim, int A[dim][dim], int s, int e) { 
    int Temp; 

    for (Temp = 0; Temp < dbglvl; Temp++) { 
     putchar('>'); 
    } 
    printf("Transpose(dim=%d, s=%d, e=%d)\n", dim, s, e); 
    if (e - s <= 2) { 
     for (int r = s; r < e - 1 ; r++) 
      for (int c = s + 1 ; c < e ; c++) { 
       printf("transp %d %d: %d %d\n", r, c, A[r][c], A[c][r]); 
       Temp = A[r][c]; 
       A[r][c] = A[c][r]; 
       A[c][r] = Temp; 
      } 
    } 
    else { 
     int m = (s + e)/2; 
     dbglvl++; 
     Transpose(dim, A, s, m); 
     Transpose(dim, A, m, e); 
     TransposeSwap(dim, A, m, s, e, m); 
     dbglvl--; 
    } 
    for (Temp = 0; Temp < dbglvl; Temp++) { 
     putchar('<'); 
    } 
    printf("Transpose\n"); 
} 

void Dump(int dim, int A[dim][dim], int rs, int cs, int re, int ce) { 
    int r, c; 

    for (r = rs; r < re; r++) { 
     for (c = cs; c < ce; c++) { 
      printf("%d ", A[r][c]); 
     } 
     putchar('\n'); 
    } 
} 

#define N 100 

int test[N][N] = { 
    { 11, 12, 13, 14, 15, 16, 17, 18, 19 }, 
    { 21, 22, 23, 24, 25, 26, 27, 28, 29 }, 
    { 31, 32, 33, 34, 35, 36, 37, 38, 39 }, 
    { 41, 42, 43, 44, 45, 46, 47, 48, 49 }, 
    { 51, 52, 53, 54, 55, 56, 57, 58, 59 }, 
    { 61, 62, 63, 64, 65, 66, 67, 68, 69 }, 
    { 71, 72, 73, 74, 75, 76, 77, 78, 79 }, 
    { 81, 82, 83, 84, 85, 86, 87, 88, 89 }, 
    { 91, 92, 93, 94, 95, 96, 97, 98, 99 }, 
}; 

int main(void) { 
    puts("Original:"); 
    Dump(N, test, 0, 0, 9, 9); 
    putchar('\n'); 
    dbglvl = 1; 
    Transpose(N, test, 0, 9); 
    putchar('\n'); 
    puts("Transposed:"); 
    Dump(N, test, 0, 0, 9, 9); 
    return 0; 
}