자바 스파 스 매트릭스 생성

Question

나는 현재 SparseMatrixNode 사용하는 스파 스 매트릭스 프로그램을 만드는거야 :

이

public SparseMatrixNode(int row, int col, int value, SparseMatrixNode down, SparseMatrixNode across) 
    { 
     this.row = row; 
     this.col = col; 
     this.value = value; 
     this.down = down; 
     this.across = across; 
    } 

내 프로그램 템플릿 희소 행렬과 같이 작성

public SparseMatrix() 
    { 
    noofrows=noofcols=0;  
    // create the top-left entry point cell 
    root=new SparseMatrixNode(0, 0, 0, new SparseMatrixNode(0, 0, 0, null, null), new SparseMatrixNode(0, 0, 0, null, null)); 
    }  


    public void Create(int noofrows, int noofcols) 
    { 
     this.noofrows=noofrows; 
     this.noofcols=noofcols; 
     root=new SparseMatrixNode(0, 0, 0, new SparseMatrixNode(noofrows+1, 0, 0, null, null), new SparseMatrixNode(0, noofcols+1, 0, null, null)); 
    } 

그리고 이것은 내 SetValue는입니다 함수는 3 개의 정수 값을 받아 현재 값을 바꾸거나 새 노드를 만들어 Sparse 행렬에 삽입합니다.

public void SetValue(int row, int col, int value) 
    {  
     if (value == 0) 
     { 
      return; 
     } 
     else 
     { 
      SparseMatrixNode checkNode = FindNode(row, col); 
      if (checkNode.value != 0) 
      { 
       checkNode.setValue(value); 
      } 
      //SparseMatrixNode dummyRow = root.FindRow(row); 
      if (root.down.row == 5) 
      { 
       root.down = new SparseMatrixNode(row, 0, 0, null, new SparseMatrixNode(row, col, value, null, null)); 
       root.across = new SparseMatrixNode(0, col, 0, new SparseMatrixNode(row, col, value, null, null), null); 
      }   
     } 

그러나 나는 4x4 그리드와 SetValue를 호출을 기반으로 내 코드를 테스트 할 때 (1, 2, 5), 단순히 공의의 그리드를 출력합니다. 나는 내 코드를 단계별로 실행하고 왜 새로운 노드를 입력하지 않는지 알아 냈다. 그러나 몇 시간 동안 갇혀 있었고 누군가가 상황에 대해 밝힐 수 있는지 궁금해하고 있었습니까?

내 질문은 : 왜 내 SetValue 함수를 새 노드를 만들고 "더미"가로 및 세로 속성 (행 0 열 0) 연결하지 않는 이유는 무엇입니까?

Answer 1

Find 메서드와 인쇄를 담당하는 코드를 표시하지 않으면 무엇이 잘못되는지 알기 어렵습니다.

그러나 접근 방식은 나에게 복잡하게 보입니다. 나는 위치에 값의 Map을 사용하는 것이 더 쉽다는 것을 발견했다. (이것은 키의 사전 표현이라고 불린다). 수행 할 작업에 따라 Sparse 행렬에 대해보다 효율적인 저장 형식이있을 수 있습니다. 몇 가지 표준 예제는 here입니다.

다음은 사전 키 접근 방식의 작동 예제입니다.

import java.util.*; 

class Position { 
    private Integer row, col; 

    public Position(int row, int col) 
    { 
     this.row = row; 
     this.col = col; 
    } 

    @Override 
    public boolean equals(Object o) { 
     if (!(o instanceof Position)) 
      return false; 
     Position other = (Position)o; 
     return row == other.row && col == other.col; 
    } 

    @Override 
    public int hashCode() { 
     return 31 * row.hashCode() + col.hashCode(); 
    } 

    @Override 
    public String toString() { 
     return String.format("(%d, %d)", row, col); 
    } 

} 

public class SparseMatrix { 

    private Map<Position, Integer> nnzs = new HashMap<>(); 
    private int maxRows, maxCols; 

    public SparseMatrix(int maxRows, int maxCols) { 
     this.maxRows = maxRows; 
     this.maxCols = maxCols; 
    } 

    public void SetValue(int row, int col, int value) {  
     if (row > maxRows || col > maxCols) 
      throw new RuntimeException("Position out of bounds"); 
     nnzs.put(new Position(row, col), value); 
    } 

    public static void main(String[] args) { 
     SparseMatrix sp = new SparseMatrix(10, 10); 
     sp.SetValue(1, 2, 5); 
     System.out.println(sp.nnzs); 
     sp.SetValue(1, 2, 7); 
     sp.SetValue(1, 10, 8); 
     System.out.println(sp.nnzs); 
    } 
} 

출력 :

javac SparseMatrix.java && java SparseMatrix 
{(1, 2)=5} 
{(1, 2)=7, (1, 10)=8}