희소행렬의 전치 - Sparse Matrix's Fast Transpose

희소행렬을 표현할 때 Structure를 이용해 현재 행렬에 들어있는 값들만을 row, column 순으로 오름차순으로 정렬해 Array로 표현하는 방법이 있다.

 

이렇게 나타낸 행렬을 덧셈 곱셈등의 연산에도 활용할 수 있는데, 전치행렬을 구하는 연산도 적용할 수 있다.

다양한 전치행렬을 만드는 알고리즘 중, Fast Transpose가 단번에 잘 이해가 되지 않아서 정리해보았다.

 

( matrix array는 (row, column ,value) structure를 순서대로 담아놓은 Array임 )

 

이해가 잘 안된 부분은 StartingPosition이였다. 한 번 이해하고 나니 크게 어렵지 않게 코드를 작성할 수 있었다.

 

다른 (느린) 전치과정과 달리 Fast Transpose는 옮겨담는 matrix array에 index 0부터 차례대로 담지 않고, 자기가 찾아가야할 자리에 쏙 넣어주는 것이 특징이라고 생각된다. 이를 위해 넣어진 값이 StartingPosition이다. 굳이 비유하자면, 7명의 사람이 1층에 3명, 2층에 2명, 3층에 2명으로 순서대로 배정받았을 때, 1~5번 사람이 모두 자기 자리를 찾아가지 않더라도 (앞의 원소가 비어있어도) 6번 사람은 3층으로 찾아갈 수 있도록 (앞의 인원 수가 3+2 = 5이므로 3층을 찾아감. 자기 index에 저장될 수 있도록) 하는것이 StartingPosition이라 생각한다..

 

StartingPosition을 매기는 기준은 3번째 column을 기준으로, 1,2번 column에 속해있던 원소의 개수 + 1 에 해당한다. 이를 통해 앞에 나와야 할 원소의 개수를 미리 파악하여 1,2번째 column의 원소가 아직 옮겨지지 않았어도 3번 column의 원소를 반환하는 matrix에 옮겨담을 수 있게 하는것이 알고리즘의 핵심이다. 원소 개수를 미리 파악하는것이 두 번째 for 문에 해당한다. (모든 원소에 대해 자신의 column에 대한 count에 +1, for문이 끝나면 rowTerms에 변환후 긱 row에 속한 원소의 수가 나온다.)

 

matrix array에서 row가 작을수록 ( 위쪽에 있을 수록 ) index가 작은 성질(정렬되었으므로)이 전치된 후에도 유지되기 위해서, Origin matrix array의 column이 작을수록 index가 작도록 배정해주어야 한다.

 

코드를 설명하자면,

첫 번째, 두 번째 for문은 각 column에 속한 원소의 개수를 count하여 rowTerms에 넣는 코드이다.

 

세 번째 for문은 StartingPosition을 정해주는 코드이다. ( 1층에는 1번부터, 2층에는 4번부터, 3층에는 6번부터  이런 식의 값. )

 

네 번째 for문에서 처음부터 원소 순서대로 b matrix array에 옮겨담는데, column을 보고 몇 번째 index로 넣어줄지 결정한다.

같은 columnd을 가진 원소들은 row에 대해 처음부터 오름차순으로 정렬되어있기에 같은 column이라도 큰 row가 뒤에 나오기 때문에 따로 row에 대한 체크는 할 필요가 없다. ( 3층은 6번에 항상 7번보다 앞에 오기 때문에, 7번이 뒷자리로, 6번이 앞자리로에 대한 생각 없이 온 순서대로 배정하면 된다 )

단, startingPosition의 값을 index로 가지는 array가 찼으므로, startingPosition을 한 칸 뒤로 밀어준다 ( ++ )

 

typedef struct {
    int row;
    int column;
    int value;
}matrix;

void fastTranspose(matrix* a, matrix* b) {
    b[0].row = a[0].column;
    b[0].column = a[0].row;
    b[0].value = a[0].value;
    
    int rowTerms[10];
    int startingPosition[10];
    
    for(int i = 0; i < a[0].column; i++) {
        rowTerms[i] = 0;
    }
    for(int i = 1; i <= a[0].value; i++) {
        rowTerms[a[i].column]++;
    }
    
    startingPosition[0] = 1;
    
    for(int i = 1; i <= a[0].column; i++) {
        startingPosition[i] = startingPosition[i-1] + rowTerms[i-1];
    }
    
    for(int i = 1; i <= a[0].value; i++) {
        int j = startingPosition[a[i].column]++;
        b[j].row = a[i].column;
        b[j].column = a[i].row;
        b[j].value = a[i].value;
    }
}