Javaデータ構造の疎行列定義と使用例
本論文の例は、Javaデータ構造の疎行列定義と使用法について述べる。皆さんに参考にしてあげます。具体的には以下の通りです。
まばらな行列の非ゼロ要素の3つの母集団:
本論文で述べたように、皆さんの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プログラムの設計に役に立ちます。