Javaデータ構造の疎行列定義と使用例


本論文の例は、Javaデータ構造の疎行列定義と使用法について述べる。皆さんに参考にしてあげます。具体的には以下の通りです。
まばらな行列の非ゼロ要素の3つの母集団:

package com.clarck.datastructure.matrix;
/**
 *          
 *
 *              
 *
 * @author clarck
 *
 */
public class Triple implements Comparable<Triple> {
  //   ,  ,    ,      
  int row, colum, value;
  public Triple(int row, int colum, int value) {
    if (row < 0 || colum < 0) {
      throw new IllegalArgumentException("           /      ");
    }
    this.row = row;
    this.colum = colum;
    this.value = value;
  }
  /**
   *       ,       
   *
   * @param elem
   */
  public Triple(Triple elem) {
    this(elem.row, elem.colum, elem.value);
  }
  @Override
  public String toString() {
    return "(" + row + ", " + colum + ", " + value + ")";
  }
  /**
   *          ,        
   */
  public boolean equals(Object obj) {
    if (!(obj instanceof Triple))
      return false;
    Triple elem = (Triple) obj;
    return this.row == elem.row && this.colum == elem.colum
        && this.value == elem.value;
  }
  /**
   *                  ,      ,         
   */
  @Override
  public int compareTo(Triple elem) {
    //        
    if (this.row < elem.row || this.row == elem.row && this.colum < elem.colum)
      return -1;
    //  , equals      
    if (this.row == elem.row && this.colum == elem.colum)
      return 0;
    //        
    return 1;
  }
  /**
   *   , +=     
   * @param term
   */
  public void add(Triple term) {
    if (this.compareTo(term) == 0)
      this.value += term.value;
    else
      throw new IllegalArgumentException("       ,    ");
  }
  /**
   *       
   *
   * @return
   */
  public boolean removable() {
    //    0   
    return this.value == 0;
  }
  /**
   *               
   * @return
   */
  public Triple toSymmetry() {
    return new Triple(this.colum, this.row, this.value);
  }
  /**
   *     ,     +
   * @return
   */
  public Triple plus(Triple term) {
    Triple tmp = new Triple(this);
    tmp.add(term);
    return tmp;
  }
}

三元グループの順番に格納されるまばらな行列の種類:

package com.clarck.datastructure.matrix;
import com.clarck.datastructure.linear.SeqList;
/**
 *          
 *
 *           
 *
 *              
 *
 * @author clarck
 *
 */
public class SeqSparseMatrix {
  //     、  
  private int rows, columns;
  //           
  private SeqList<Triple> list;
  /**
   *   rows ,colums    
   *
   * @param rows
   * @param columns
   */
  public SeqSparseMatrix(int rows, int columns) {
    if (rows <= 0 || columns <= 0)
      throw new IllegalArgumentException("           ");
    this.rows = rows;
    this.columns = columns;
    //       ,  SeqList()    
    this.list = new SeqList<Triple>();
  }
  public SeqSparseMatrix(int rows, int columns, Triple[] elems) {
    this(rows, columns);
    //               
    for (int i = 0; i < elems.length; i++)
      this.set(elems[i]);
  }
  /**
   *      i  j   ,            ,O(n)
   *
   * @param i
   * @param j
   * @return
   */
  public int get(int i, int j) {
    if (i < 0 || i >= rows || j < 0 || j >= columns)
      throw new IndexOutOfBoundsException("            ");
    Triple item = new Triple(i, j, 0);
    int k = 0;
    Triple elem = this.list.get(k);
    //       list     item  
    while (k < this.list.length() && item.compareTo(elem) >= 0) {
      //           , elem.row == i && elem.column == j
      if (item.compareTo(elem) == 0)
        return elem.value;
      //    (i, j),       
      k++;
      elem = this.list.get(k);
    }
    return 0;
  }
  /**
   *           
   *
   * @param elem
   */
  public void set(Triple elem) {
    this.set(elem.row, elem.colum, elem.value);
  }
  /**
   *      row  column      value,          list              , O(n)
   *
   * @param row
   * @param column
   * @param value
   */
  public void set(int row, int column, int value) {
    //      0  
    if (value == 0)
      return;
    if (row >= this.rows || column >= this.columns)
      throw new IllegalArgumentException("           ");
    Triple elem = new Triple(row, column, value);
    int i = 0;
    //              elem  ,      
    while (i < this.list.length()) {
      Triple item = this.list.get(i);
      //  elem  ,          
      if (elem.compareTo(item) == 0) {
        //       i    elem
        this.list.set(i, elem);
        return;
      }
      // elem       
      if (elem.compareTo(item) >= 0)
        i++;
      else
        break;
    }
    this.list.insert(i, elem);
  }
  @Override
  public String toString() {
    String str = "      :" + this.list.toString() + "
"; str += " " + this.getClass().getSimpleName() + "(" + rows + " * " + columns + "):
"; int k = 0; // k , k null Triple elem = this.list.get(k++); for (int i = 0; i < this.rows; i++) { for (int j = 0; j < this.columns; j++) if (elem != null && i == elem.row && j == elem.colum) { str += String.format("%4d", elem.value); elem = this.list.get(k++); } else { str += String.format("%4d", 0); } str += "
"; } return str; } /** * smat , smatc=this+smat, , * * @param smat * @return */ public SeqSparseMatrix plus(SeqSparseMatrix smat) { if (this.rows != smat.rows || this.columns != smat.columns) throw new IllegalArgumentException(" , "); // rows*columns SeqSparseMatrix smatc = new SeqSparseMatrix(this.rows, this.columns); int i = 0, j = 0; // while (i < this.list.length() && j < smat.list.length()) { Triple elema = this.list.get(i); Triple elemb = smat.list.get(j); // , if (elema.compareTo(elemb) == 0) { // , if (elema.value + elemb.value != 0) smatc.list.append(new Triple(elema.row, elema.colum, elema.value + elemb.value)); i++; j++; } else if (elema.compareTo(elemb) < 0) { // smatc // elema Triple smatc.list.append(new Triple(elema)); i++; } else { smatc.list.append(new Triple(elemb)); j++; } } // smatc while (i < this.list.length()) smatc.list.append(new Triple(this.list.get(i++))); // smat smatc while (j < smatc.list.length()) { Triple elem = smat.list.get(j++); if (elem != null) { smatc.list.append(new Triple(elem)); } } return smatc; } /** * smat ,this+=smat, , * * @param smat */ public void add(SeqSparseMatrix smat) { if (this.rows != smat.rows || this.columns != smat.columns) throw new IllegalArgumentException(" , "); int i = 0, j = 0; // mat ( ) while (i < this.list.length() && j < smat.list.length()) { Triple elema = this.list.get(i); Triple elemb = smat.list.get(j); // , if (elema.compareTo(elemb) == 0) { // 0, if (elema.value + elemb.value != 0) this.list.set(i++, new Triple(elema.row, elema.colum, elema.value + elemb.value)); else this.list.remove(i); j++; } else if (elema.compareTo(elemb) < 0) { // elemb i++; } else { // elemb this.list i this.list.insert(i++, new Triple(elemb)); j++; } } // mat while (j < smat.list.length()) { this.list.append(new Triple(smat.list.get(j++))); } } // public SeqSparseMatrix(SeqSparseMatrix smat) { this(smat.rows, smat.columns); // , this.list = new SeqList<Triple>(); // smat for (int i = 0; i < smat.list.length(); i++) this.list.append(new Triple(smat.list.get(i))); } /** * */ public boolean equals(Object obj) { if (this == obj) return true; if (!(obj instanceof SeqSparseMatrix)) return false; SeqSparseMatrix smat = (SeqSparseMatrix) obj; return this.rows == smat.rows && this.columns == smat.columns && this.list.equals(smat.list); } /** * * @return */ public SeqSparseMatrix transpose() { // , SeqSparseMatrix trans = new SeqSparseMatrix(columns, rows); for (int i = 0; i < this.list.length(); i++) { // trans.set(this.list.get(i).toSymmetry()); } return trans; } }
テストクラス:

package com.clarck.datastructure.matrix;
/**
 *          
 *
 *           
 *
 *                    
 *
 * @author clarck
 *
 */
public class SeqSparseMatrix_test {
  public static void main(String args[]) {
    Triple[] elemsa = { new Triple(0, 2, 11), new Triple(0, 4, 17),
        new Triple(1, 1, 20), new Triple(3, 0, 19),
        new Triple(3, 5, 28), new Triple(4, 4, 50) };
    SeqSparseMatrix smata = new SeqSparseMatrix(5, 6, elemsa);
    System.out.print("A " + smata.toString());
    Triple[] elemsb = { new Triple(0, 2, -11), new Triple(0, 4, -17),
        new Triple(2, 3, 51), new Triple(3, 0, 10),
        new Triple(4, 5, 99), new Triple(1, 1, 0) };
    SeqSparseMatrix smatb = new SeqSparseMatrix(5,6,elemsb);
    System.out.print("B " + smatb.toString());
    SeqSparseMatrix smatc = smata.plus(smatb);
    System.out.print("C=A+B"+smatc.toString());
    System.out.println();
    smata.add(smatb);
    System.out.print("A+=B" + smata.toString());
    System.out.println("C.equals(A)?" + smatc.equals(smata));
    SeqSparseMatrix smatd = new SeqSparseMatrix(smatb);
    smatb.set(0,2,1);
    System.out.print("B " + smatb.toString());
    System.out.print("D " + smatd.toString());
    System.out.println("A  " + smata.transpose().toString());
  }
}

実行結果:

A       :((0, 2, 11), (0, 4, 17), (1, 1, 20), (3, 0, 19), (3, 5, 28), (4, 4, 50))
    SeqSparseMatrix(5 * 6):
  0  0 11  0 17  0
  0 20  0  0  0  0
  0  0  0  0  0  0
 19  0  0  0  0 28
  0  0  0  0 50  0
B       :((0, 2, -11), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99))
    SeqSparseMatrix(5 * 6):
  0  0 -11  0 -17  0
  0  0  0  0  0  0
  0  0  0 51  0  0
 10  0  0  0  0  0
  0  0  0  0  0 99
C=A+B      :((1, 1, 20), (2, 3, 51), (3, 0, 29), (3, 5, 28), (4, 4, 50), (4, 5, 99))
    SeqSparseMatrix(5 * 6):
  0  0  0  0  0  0
  0 20  0  0  0  0
  0  0  0 51  0  0
 29  0  0  0  0 28
  0  0  0  0 50 99
A+=B      :((1, 1, 20), (2, 3, 51), (3, 0, 29), (3, 5, 28), (4, 4, 50), (4, 5, 99))
    SeqSparseMatrix(5 * 6):
  0  0  0  0  0  0
  0 20  0  0  0  0
  0  0  0 51  0  0
 29  0  0  0  0 28
  0  0  0  0 50 99
C.equals(A)?true
B       :((0, 2, 1), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99))
    SeqSparseMatrix(5 * 6):
  0  0  1  0 -17  0
  0  0  0  0  0  0
  0  0  0 51  0  0
 10  0  0  0  0  0
  0  0  0  0  0 99
D       :((0, 2, -11), (0, 4, -17), (2, 3, 51), (3, 0, 10), (4, 5, 99))
    SeqSparseMatrix(5 * 6):
  0  0 -11  0 -17  0
  0  0  0  0  0  0
  0  0  0 51  0  0
 10  0  0  0  0  0
  0  0  0  0  0 99
A        :((0, 3, 29), (1, 1, 20), (3, 2, 51), (4, 4, 50), (5, 3, 28), (5, 4, 99))
    SeqSparseMatrix(6 * 5):
  0  0  0 29  0
  0 20  0  0  0
  0  0  0  0  0
  0  0 51  0  0
  0  0  0  0 50
  0  0  0 28 99

javaアルゴリズムに関する詳細について興味がある読者は、当駅のテーマを見ることができます。「Javaデータ構造とアルゴリズム教程」、「Java操作DOMノード技術のまとめ」、「Javaファイルとディレクトリの操作テクニックのまとめ」、「Javaキャッシュ操作テクニックのまとめ
本論文で述べたように、皆さんのjavaプログラムの設計に役に立ちます。