7. 희소 행렬 연산의 Java 구현

in Study on Java


javalogo

Overview

이 포스트에서는 희소 행렬 추상 데이터 타입에서 설명한 희소 행렬 전치 알고리즘을 Java 프로그램으로 구현해 본다.

앞서 설명한대로 3원소 쌍을 2차원 배열로 표현할 수 있지만 2차원 배열로 표현한다면 우선 배열 크기를 임의로 크게 할당해야 하여 많은 공간을 낭비하기 쉽다.

물론 이 문제는 메모리 할당 함수나 배열 크기를 동적으로 할당하는 방법으로 해결할 수 있지만 객체지향 개념을 지원하는 Java와 같은 환경에서는 3원소 쌍을 2차원 배열보다 클래스로 표현하는 것이 더 바람직하다.

그러므로 3원소 쌍을 표현하는 방법으로 클래스를 사용하기로 한다.

희소 행렬 연산의 Java 구현

먼저 3원소 쌍을 객체로 표현하기 위해 Triple 클래스를 다음과 같이 정의한다.

이 Triple 클래스는 3원소 쌍 행(row), 열(col), 값(value)을 위한 세 개의 필드와 생성자를 갖도록 한다.

생성자는 인자 없이 기본값으로 초기화하는 것과 인자로 전달된 값으로 3원소 쌍을 초기화하는 두 개의 생성자를 정의하였다.

public class Triple {
    int row;
    int col;
    int value;

    public Triple() {
        row = 0;
        col = 0;
        value = 0;
    }

    public Triple(int r, int c, int v) {
        row = r;
        col = c;
        value = v;
    }
}

다음에는 이 Triple 타입의 배열을 이용하여 SparseMatrix 클래스를 다음과 같이 정의한다.

public class SparseMatrix {
    int Nrows, Ncols, Nterms, idx;
    Triple[] a;

    public SparseMatrix(int rows, int cols, int terms) {
        // 생성자. 각 변수 초기화
        Nrows = rows; Ncols = cols; Nterms = terms;
        idx = 0;
        a = new Triple[Nterms];
    }

    public void displayMatrix() {
        // 행의 수, 열의 수, 0이 아닌 원소수를 출력
        System.out.println("Number of rows : " + Nrows);
        System.out.println("Number of columns : " + Ncols);
        System.out.println("Number of non-zero terms : " + Nterms);
            // 행렬의 내용을 "[인덱스] 행 열 값"으로 출력
        for(int i = 0; i < Nterms; i++)
            System.out.println("[" + i + "] " + a[i].row + " " + a[i].col + " " + a[i].value);
    }

    public void storeTriple(int r, int c, int v) {
        if(idx >= Nterms) { // Error
            System.out.println("Error : too many terms");
            System.exit(-1);
        }
        a[idx++] = new Triple(r, c, v);
    }

    public SparseMatrix transpose() {
        int i, j;
        int [] RowTerms = new int[Ncols];
        int [] RowBegins = new int[Ncols];
        SparseMatrix b = new SparseMatrix(Ncols, Nrows, Nterms);
        if(Nterms > 0) {
            for(i = 0; i < Ncols; i++) RowTerms[i] = 0;
            for(i = 0; i < Nterms; i++) RowTerms[a[i].col]++;
            RowBegins[0] = 0;
            for(i = 0; i < Ncols; i++) RowBegins[i] = RowBegins[i-1] + RowTerms[i-1];
            for(i = 0; i < Nterms; i++) {
                j = RowBegins[a[i].col]++;
                b.a[j] = new Triple(a[i].col, a[i].row, a[i].value);
            }
        }
        return b;
    }
}   // end SparseMatrix class

Triple 타입의 배열 a[]는 4행에서 선언만 되고 실제로 생성되어지는 것은 a = new Triple[Nterms];에서 Nterms개의 원소를 저장할 수 있는 메모리를 할당할 때이다.

Java에서는 배열을 동적으로 할당한다.

배열 변수를 선언할 때는 Triple[] a;에서와 같이 차수는 명세하지 않지만 배열이 a = new Triple[Nterms];에서와 같이 new 연산자를 통해 생성될 때 그 차수가 결정된다.

따라서 배열 a[]는 1차원 배열로 원소수가 Nterms이다.

Java 배열의 인덱스는 항상 0부터 시작되므로 배열의 마지막 원소는 a[Nterms-1]이 된다.

Java에서 클래스 타입의 배열은 그 배열이 나타내는 클래스의 객체를 가리키는 참조 변수의 그룹과 같기 때문에 a = new Triple[Nterms];에서 만들어진 Triple 클래스 타입의 배열 a[]는 Nterms개의 Triple 객체들에 대한 참조(주소)를 저장하기 위한 참조 변수 집단을 생성한 것과 같다.

실제 이 객체 3원소 쌍은 a[idx++] = new Triple(r, c, v);에서 new를 통해 만들어져 주소가 a[idx]인 곳에 저장된다.

SparseMatrix 클래스의 메소드 기능

  • SparseMatrix(int rows, int cols, int terms);
    • 생성자로서 Nrows와 Ncols를 각각 rows, cols로 초기화 하고 이 a[]의 인덱스로 사용할 idx를 초기화 한다.
      Nterms 크기의 Triple 타입 배열 a[]를 new를 이용하여 생성한다.
  • void displayMatrix();
    • 행렬의 내용을 화면에 표시해준다.
  • void storeTriple(int r, int c, int v);
    • a[idx++] = new Triple(r, c, v); : 생성자가 할당한 Triple 타입 배열 a[]에 실제 객체의 주소를 저장한다
    • 인자로 전달받은 r, c, v값으로 Triple의 생성자를 통해 Triple 객체를 생성하고 그 참조(주소)는 a[]에 저장한다.
      이때 a = new Triple[Nterms];에서 할당한 a[]는 단순히 Triple 객체에 대한 참조를 젖아하는 포인터 배열이기 대문에 그것이 실제로 가리켜야할 객체는 new를 통해 생성해 주어야 한다.
  • SparseMatrix transpose();
    • 주어진 희소 행렬을 전치시켜 희소 행렬 b[]를 만들어 반환한다.
        for(i = 0; i < Ncols; i++) RowTerms[i] = 0;
  for(i = 0; i < Nterms; i++) RowTerms[a[i].col]++;
  RowBegins[0] = 0;
  for(i = 0; i < Ncols; i++) RowBegins[i] = RowBegins[i-1] + RowTerms[i-1];
    • 위 코드는 전치 행렬 b[]에서 행의 크기 RowTerms와 행의 출발점 RowBegins를 계산하고 설정한다.
        b.a[j] = new Triple(a[i].col, a[i].row, a[i].value);
    • 이 부분은 실제로 주어진 희소 행렬에서부터 b[]로 3원소 쌍을 이동시키는 것인데, 이것을 풀어쓰면 다음과 같다.
        b.a[j] = new Triple();
  b.a[j].row = a[i].col;
  b.a[j].col = a[i].row;
  b.a[j].value = a[i].value;

행렬 전치 프로그램

다음 프로그램은 지금까지 설명한 SparseMatrix 클래스를 이용하여 7\(\times\)6 행렬 a를 전치시킨다.

public class SparseTrans {
    public static void main(String arg[]) {
        SparseMatrix b;
        SparseMatrix a = new SparseMatrix(7, 6, 8); // 7행 6열, 0이 아닌 원소 수가 8인 SparseMatrix 객체를 생성

        a.storeTriple(0, 0, 76);    //행렬 입력
        a.storeTriple(0, 4, 13);
        a.storeTriple(2, 5, 3);
        a.storeTriple(3, 1, 25);
        a.storeTriple(4, 0, -19);
        a.storeTriple(4, 3, 56);
        a.storeTriple(5, 5, 13);
        a.storeTriple(6, 2, 3);

        a.displayMatrix();          // 희소 행렬 a[] 출력
        b = a.transpose();          // 행렬 a[]에 대해 transpose() 메소드를 사용하여 결과를 b[]에 저장
        b.displayMatrix();          // 전치된 희소행렬 b[] 출력
    }   // end main()
}   // end SparseTrans class

실행이 완료되면 다음과 같은 결과가 출력된다.

Number of rows : 7
Number of columns : 6
Number of non-zero term : 8
[0] 0 0 46
[1] 0 4 13
[2] 2 5 3
[3] 3 1 25
[4] 4 0 -19
[5] 4 3 56
[6] 5 5 13
[7] 6 2 3

Number of rows : 6
Number of columns : 7
Number of non-zero term : 8
[0] 0 0 76
[1] 0 4 -19
[2] 1 3 25
[3] 2 6 3
[4] 3 4 56
[5] 4 0 13
[6] 5 2 3
[7] 5 5 13

정리

transpose() 메소드에는 각각 Ncols, Nterms, Ncols-1, Nterms번 실행되는 4개의 루프가 있다.

루프를 한 번 왕복하는 데는 상수 시간이 걸리므로 이 알고리즘의 복잡도는 위에서 언급한대로 \(O\)(Ncols+Nterms)가 된다.

참고 문서

  • 이석호. (2004). 자료 구조와 JAVA. 정익사.



© 2019. by RaP0d

Powered by aiden