私は Java で書かれたプロジェクトに取り組んでいます。このプロジェクトでは、非常に大きな 2 次元疎配列を構築する必要があります。それが違いを生む場合、非常にまばらです。とにかく、このアプリケーションの最も重要な側面は、時間の効率性です (メモリの負荷を想定しますが、標準の 2 次元配列を使用できるほど無制限ではありません。重要な範囲は両方の次元で数十億です)。 ）。
配列内の無数のセルのうち、オブジェクトを含む数十万のセルがあります。セルの内容を非常に迅速に変更できる必要があります。
とにかく:この目的のために特に優れたライブラリを知っている人はいますか? Berkeley、LGPL、または同様のライセンスである必要があります (製品を完全にオープンソースにすることはできないため、GPL は使用できません)。または、自作のスパース配列オブジェクトを作成する非常に簡単な方法があれば、それも問題ありません。
MTJを検討していますが、品質についての意見は聞いていません。
ハッシュマップで構築されたスパース配列は、頻繁に読み取られるデータに対して非常に非効率的です。最も効率的な実装では、セグメントが分散されている単一のベクトルへのアクセスを許可する Trie を使用します。
Trie は、要素が格納されている有効な位置を取得するため、または基になるストアに存在しないかどうかを知るために、読み取り専用の TWO 配列のインデックス付けのみを実行することによって、要素がテーブルに存在するかどうかを計算できます。
また、スパース配列のデフォルト値のバッキング ストア内のデフォルト位置を提供することもできます。これにより、返されたインデックスに対してテストを行う必要がなくなります。Trie は、考えられるすべてのソース インデックスが少なくともデフォルトにマップされることを保証するためです。バッキング ストア内の位置 (頻繁にゼロ、空の文字列、または null オブジェクトを格納する場所)。
複数の操作の最後にバッキングストアのサイズを最適化するオプションの「compact()」操作を使用して、高速更新可能なトライをサポートする実装が存在します。トライは、複雑なハッシュ関数を必要とせず、読み取りの衝突を処理する必要がないため、ハッシュマップよりもはるかに高速です (ハッシュマップを使用すると、読み取りと書き込みの両方で衝突が発生します。これには、ループをスキップして次の候補位置、および有効なソース インデックスを比較するためのそれぞれのテスト...)
さらに、Java ハッシュマップはオブジェクトのインデックスしか作成できず、ハッシュされたソース インデックスごとに Integer オブジェクトを作成する (このオブジェクトの作成は、書き込みだけでなく読み取りごとに必要になります) と、ガベージ コレクターに負荷がかかるため、メモリ操作の点でコストがかかります。 .
JRE が IntegerTrieMap<Object> を遅い HashMap<Integer, Object> のデフォルト実装として、または LongTrieMap<Object> をさらに遅い HashMap<Long, Object> のデフォルト実装として含めることを本当に望んでいました...しかし、これはまだそうではありません。
トライとは何ですか？
座標をベクトル内の整数位置にマッピングできるのは、(行列の座標の全範囲よりも小さい範囲の) 整数の小さな配列です。
たとえば、数個の非ゼロ値のみを含む 1024*1024 マトリックスが必要だとします。その行列を 1024*1024 要素 (100 万以上) を含む配列に格納する代わりに、サイズ 16*16 の部分範囲に分割するだけで、64*64 の部分範囲が必要になります。
その場合、Trie インデックスには 64*64 の整数 (4096) だけが含まれ、少なくとも 16*16 のデータ要素 (デフォルトのゼロ、またはスパース行列で見つかった最も一般的な部分範囲を含む) が存在します。
また、値を格納するために使用されるベクトルには、互いに等しい部分範囲のコピーが 1 つだけ含まれます (それらのほとんどはゼロでいっぱいで、同じ部分範囲で表されます)。
したがって、 のような構文を使用する代わりにmatrix[i][j]、次のような構文を使用します。
trie.values[trie.subrangePositions[(i & ~15) + (j >> 4)] +
((i & 15) << 4) + (j & 15)]
これは、trie オブジェクトのアクセス メソッドを使用してより便利に処理されます。
以下は、コメント化されたクラスに組み込まれた例です (単純化されているため、正常にコンパイルされることを願っています。修正するエラーがある場合は通知してください)。
/**
* Implement a sparse matrix. Currently limited to a static size
* (<code>SIZE_I</code>, <code>SIZE_I</code>).
*/
public class DoubleTrie {
/* Matrix logical options */
public static final int SIZE_I = 1024;
public static final int SIZE_J = 1024;
public static final double DEFAULT_VALUE = 0.0;
/* Internal splitting options */
private static final int SUBRANGEBITS_I = 4;
private static final int SUBRANGEBITS_J = 4;
/* Internal derived splitting constants */
private static final int SUBRANGE_I =
1 << SUBRANGEBITS_I;
private static final int SUBRANGE_J =
1 << SUBRANGEBITS_J;
private static final int SUBRANGEMASK_I =
SUBRANGE_I - 1;
private static final int SUBRANGEMASK_J =
SUBRANGE_J - 1;
private static final int SUBRANGE_POSITIONS =
SUBRANGE_I * SUBRANGE_J;
/* Internal derived default values for constructors */
private static final int SUBRANGES_I =
(SIZE_I + SUBRANGE_I - 1) / SUBRANGE_I;
private static final int SUBRANGES_J =
(SIZE_J + SUBRANGE_J - 1) / SUBRANGE_J;
private static final int SUBRANGES =
SUBRANGES_I * SUBRANGES_J;
private static final int DEFAULT_POSITIONS[] =
new int[SUBRANGES](0);
private static final double DEFAULT_VALUES[] =
new double[SUBRANGE_POSITIONS](DEFAULT_VALUE);
/* Internal fast computations of the splitting subrange and offset. */
private static final int subrangeOf(
final int i, final int j) {
return (i >> SUBRANGEBITS_I) * SUBRANGE_J +
(j >> SUBRANGEBITS_J);
}
private static final int positionOffsetOf(
final int i, final int j) {
return (i & SUBRANGEMASK_I) * MAX_J +
(j & SUBRANGEMASK_J);
}
/**
* Utility missing in java.lang.System for arrays of comparable
* component types, including all native types like double here.
*/
public static final int arraycompare(
final double[] values1, final int position1,
final double[] values2, final int position2,
final int length) {
if (position1 >= 0 && position2 >= 0 && length >= 0) {
while (length-- > 0) {
double value1, value2;
if ((value1 = values1[position1 + length]) !=
(value2 = values2[position2 + length])) {
/* Note: NaN values are different from everything including
* all Nan values; they are are also neigher lower than nor
* greater than everything including NaN. Note that the two
* infinite values, as well as denormal values, are exactly
* ordered and comparable with <, <=, ==, >=, >=, !=. Note
* that in comments below, infinite is considered "defined".
*/
if (value1 < value2)
return -1; /* defined < defined. */
if (value1 > value2)
return 1; /* defined > defined. */
if (value1 == value2)
return 0; /* defined == defined. */
/* One or both are NaN. */
if (value1 == value1) /* Is not a NaN? */
return -1; /* defined < NaN. */
if (value2 == value2) /* Is not a NaN? */
return 1; /* NaN > defined. */
/* Otherwise, both are NaN: check their precise bits in
* range 0x7FF0000000000001L..0x7FFFFFFFFFFFFFFFL
* including the canonical 0x7FF8000000000000L, or in
* range 0xFFF0000000000001L..0xFFFFFFFFFFFFFFFFL.
* Needed for sort stability only (NaNs are otherwise
* unordered).
*/
long raw1, raw2;
if ((raw1 = Double.doubleToRawLongBits(value1)) !=
(raw2 = Double.doubleToRawLongBits(value2)))
return raw1 < raw2 ? -1 : 1;
/* Otherwise the NaN are strictly equal, continue. */
}
}
return 0;
}
throw new ArrayIndexOutOfBoundsException(
"The positions and length can't be negative");
}
/**
* Utility shortcut for comparing ranges in the same array.
*/
public static final int arraycompare(
final double[] values,
final int position1, final int position2,
final int length) {
return arraycompare(values, position1, values, position2, length);
}
/**
* Utility missing in java.lang.System for arrays of equalizable
* component types, including all native types like double here.
*/
public static final boolean arrayequals(
final double[] values1, final int position1,
final double[] values2, final int position2,
final int length) {
return arraycompare(values1, position1, values2, position2, length) ==
0;
}
/**
* Utility shortcut for identifying ranges in the same array.
*/
public static final boolean arrayequals(
final double[] values,
final int position1, final int position2,
final int length) {
return arrayequals(values, position1, values, position2, length);
}
/**
* Utility shortcut for copying ranges in the same array.
*/
public static final void arraycopy(
final double[] values,
final int srcPosition, final int dstPosition,
final int length) {
arraycopy(values, srcPosition, values, dstPosition, length);
}
/**
* Utility shortcut for resizing an array, preserving values at start.
*/
public static final double[] arraysetlength(
double[] values,
final int newLength) {
final int oldLength =
values.length < newLength ? values.length : newLength;
System.arraycopy(values, 0, values = new double[newLength], 0,
oldLength);
return values;
}
/* Internal instance members. */
private double values[];
private int subrangePositions[];
private bool isSharedValues;
private bool isSharedSubrangePositions;
/* Internal method. */
private final reset(
final double[] values,
final int[] subrangePositions) {
this.isSharedValues =
(this.values = values) == DEFAULT_VALUES;
this.isSharedsubrangePositions =
(this.subrangePositions = subrangePositions) ==
DEFAULT_POSITIONS;
}
/**
* Reset the matrix to fill it with the same initial value.
*
* @param initialValue The value to set in all cell positions.
*/
public reset(final double initialValue = DEFAULT_VALUE) {
reset(
(initialValue == DEFAULT_VALUE) ? DEFAULT_VALUES :
new double[SUBRANGE_POSITIONS](initialValue),
DEFAULT_POSITIONS);
}
/**
* Default constructor, using single default value.
*
* @param initialValue Alternate default value to initialize all
* positions in the matrix.
*/
public DoubleTrie(final double initialValue = DEFAULT_VALUE) {
this.reset(initialValue);
}
/**
* This is a useful preinitialized instance containing the
* DEFAULT_VALUE in all cells.
*/
public static DoubleTrie DEFAULT_INSTANCE = new DoubleTrie();
/**
* Copy constructor. Note that the source trie may be immutable
* or not; but this constructor will create a new mutable trie
* even if the new trie initially shares some storage with its
* source when that source also uses shared storage.
*/
public DoubleTrie(final DoubleTrie source) {
this.values = (this.isSharedValues =
source.isSharedValues) ?
source.values :
source.values.clone();
this.subrangePositions = (this.isSharedSubrangePositions =
source.isSharedSubrangePositions) ?
source.subrangePositions :
source.subrangePositions.clone());
}
/**
* Fast indexed getter.
*
* @param i Row of position to set in the matrix.
* @param j Column of position to set in the matrix.
* @return The value stored in matrix at that position.
*/
public double getAt(final int i, final int j) {
return values[subrangePositions[subrangeOf(i, j)] +
positionOffsetOf(i, j)];
}
/**
* Fast indexed setter.
*
* @param i Row of position to set in the sparsed matrix.
* @param j Column of position to set in the sparsed matrix.
* @param value The value to set at this position.
* @return The passed value.
* Note: this does not compact the sparsed matric after setting.
* @see compact(void)
*/
public double setAt(final int i, final int i, final double value) {
final int subrange = subrangeOf(i, j);
final int positionOffset = positionOffsetOf(i, j);
// Fast check to see if the assignment will change something.
int subrangePosition, valuePosition;
if (Double.compare(
values[valuePosition =
(subrangePosition = subrangePositions[subrange]) +
positionOffset],
value) != 0) {
/* So we'll need to perform an effective assignment in values.
* Check if the current subrange to assign is shared of not.
* Note that we also include the DEFAULT_VALUES which may be
* shared by several other (not tested) trie instances,
* including those instanciated by the copy contructor. */
if (isSharedValues) {
values = values.clone();
isSharedValues = false;
}
/* Scan all other subranges to check if the position in values
* to assign is shared by another subrange. */
for (int otherSubrange = subrangePositions.length;
--otherSubrange >= 0; ) {
if (otherSubrange != subrange)
continue; /* Ignore the target subrange. */
/* Note: the following test of range is safe with future
* interleaving of common subranges (TODO in compact()),
* even though, for now, subranges are sharing positions
* only between their common start and end position, so we
* could as well only perform the simpler test <code>
* (otherSubrangePosition == subrangePosition)</code>,
* instead of testing the two bounds of the positions
* interval of the other subrange. */
int otherSubrangePosition;
if ((otherSubrangePosition =
subrangePositions[otherSubrange]) >=
valuePosition &&
otherSubrangePosition + SUBRANGE_POSITIONS <
valuePosition) {
/* The target position is shared by some other
* subrange, we need to make it unique by cloning the
* subrange to a larger values vector, copying all the
* current subrange values at end of the new vector,
* before assigning the new value. This will require
* changing the position of the current subrange, but
* before doing that, we first need to check if the
* subrangePositions array itself is also shared
* between instances (including the DEFAULT_POSITIONS
* that should be preserved, and possible arrays
* shared by an external factory contructor whose
* source trie was declared immutable in a derived
* class). */
if (isSharedSubrangePositions) {
subrangePositions = subrangePositions.clone();
isSharedSubrangePositions = false;
}
/* TODO: no attempt is made to allocate less than a
* fully independant subrange, using possible
* interleaving: this would require scanning all
* other existing values to find a match for the
* modified subrange of values; but this could
* potentially leave positions (in the current subrange
* of values) unreferenced by any subrange, after the
* change of position for the current subrange. This
* scanning could be prohibitively long for each
* assignement, and for now it's assumed that compact()
* will be used later, after those assignements. */
values = setlengh(
values,
(subrangePositions[subrange] =
subrangePositions = values.length) +
SUBRANGE_POSITIONS);
valuePosition = subrangePositions + positionOffset;
break;
}
}
/* Now perform the effective assignment of the value. */
values[valuePosition] = value;
}
}
return value;
}
/**
* Compact the storage of common subranges.
* TODO: This is a simple implementation without interleaving, which
* would offer a better data compression. However, interleaving with its
* O(N²) complexity where N is the total length of values, should
* be attempted only after this basic compression whose complexity is
* O(n²) with n being SUBRANGE_POSITIIONS times smaller than N.
*/
public void compact() {
final int oldValuesLength = values.length;
int newValuesLength = 0;
for (int oldPosition = 0;
oldPosition < oldValuesLength;
oldPosition += SUBRANGE_POSITIONS) {
int oldPosition = positions[subrange];
bool commonSubrange = false;
/* Scan values for possible common subranges. */
for (int newPosition = newValuesLength;
(newPosition -= SUBRANGE_POSITIONS) >= 0; )
if (arrayequals(values, newPosition, oldPosition,
SUBRANGE_POSITIONS)) {
commonSubrange = true;
/* Update the subrangePositions|] with all matching
* positions from oldPosition to newPosition. There may
* be several index to change, if the trie has already
* been compacted() before, and later reassigned. */
for (subrange = subrangePositions.length;
--subrange >= 0; )
if (subrangePositions[subrange] == oldPosition)
subrangePositions[subrange] = newPosition;
break;
}
if (!commonSubrange) {
/* Move down the non-common values, if some previous
* subranges have been compressed when they were common.
*/
if (!commonSubrange && oldPosition != newValuesLength) {
arraycopy(values, oldPosition, newValuesLength,
SUBRANGE_POSITIONS);
/* Advance compressed values to preserve these new ones. */
newValuesLength += SUBRANGE_POSITIONS;
}
}
}
/* Check the number of compressed values. */
if (newValuesLength < oldValuesLength) {
values = values.arraysetlength(newValuesLength);
isSharedValues = false;
}
}
}
注: このコードは単一の行列サイズを処理するため、完全ではありません。また、コンパクターは共通の部分範囲のみをインターリーブせずに検出するように制限されています。
また、コードは、行列のサイズに応じて、行列を部分範囲 (x または y 座標) に分割するために使用する最適な幅または高さを決定しません。同じ静的サブレンジ サイズの 16 (両方の座標に対して) を使用するだけですが、他の小さな 2 のべき乗 (ただし、2 のべき乗でない場合は、int indexOf(int, int)およびint offsetOf(int, int)内部メソッドの速度が低下します) を便利に使用でき、両方の座標に対して独立しています。マトリックスの最大幅または高さまで。理想的には、compact()メソッドは最適なサイズを決定できる必要があります。
これらの分割部分範囲のサイズが異なる可能性がある場合は、 static の代わりにこれらの部分範囲サイズのインスタンス メンバーを追加しSUBRANGE_POSITIONS、静的メソッドint subrangeOf(int i, int j)とint positionOffsetOf(int i, int j)非静的にする必要があります。および初期化配列DEFAULT_POSITIONSであり、別のDEFAULT_VALUES方法で削除または再定義する必要があります。
インターリーブをサポートしたい場合は、基本的に、既存の値をほぼ同じサイズの 2 つに分割することから始めます (両方とも最小サブ範囲サイズの倍数であり、最初のサブセットは 2 番目のサブセットよりも 1 つ多くのサブ範囲を持つ可能性があります)。一致するインターリーブを見つけるために、連続するすべての位置で大きい方をスキャンします。次に、これらの値を一致させようとします。次に、サブセットを半分 (これも最小サブ範囲サイズの倍数) に分割して再帰的にループし、これらのサブセットに一致するように再度スキャンします (これにより、サブセットの数が 2 倍になります: subrangePositions インデックスのサイズは、値の既存のサイズと比較して値の価値があり、それが効果的な圧縮を提供するかどうかを確認します (そうでない場合は、そこで停止します: インターリーブ圧縮プロセスから直接、最適なサブレンジ サイズを見つけました)。その場合; 圧縮中、部分範囲のサイズは変更可能です。
ただし、このコードは、ゼロ以外の値を割り当ててdata、追加の (ゼロ以外の) サブ範囲に配列を再割り当てする方法と、重複がある場合にこのデータのストレージを (メソッドcompact()を使用して割り当てが実行された後に) 最適化する方法を示しています。データ内で統合され、配列setAt(int i, int j, double value)内の同じ位置で再インデックス付けされるサブレンジ。subrangePositions
とにかく、トライのすべての原則がそこに実装されています。
配列の double-indexed 配列 (それぞれが個別に割り当てられます) の代わりに、単一のベクトルを使用して行列を表現する方が、常に高速です (そして、メモリがよりコンパクトになり、局所性が向上します)。方法に改善が見られますdouble getAt(int, int)！
多くのスペースを節約できますが、値を割り当てるときに、新しいサブ範囲を再割り当てするのに時間がかかる場合があります。このため、サブ範囲が小さすぎないようにしてください。そうしないと、マトリックスを設定するために再割り当てが頻繁に発生します。
共通の部分範囲を検出することにより、初期の大きな行列をよりコンパクトな行列に自動的に変換できます。典型的な実装には、compact()上記のようなメソッドが含まれます。ただし、get() アクセスが非常に高速で set() が非常に高速な場合、圧縮する一般的な部分範囲が多数ある場合 (たとえば、ランダムに満たされた大きな非スパース行列をそれ自体で減算する場合)、compact() は非常に遅くなる可能性があります。 、またはそれをゼロで乗算します。その場合、新しいものをインスタンス化して古いものを削除することにより、トライをリセットする方が簡単ではるかに高速です)。
共通部分範囲はデータ内の共通ストレージを使用するため、この共有データは読み取り専用である必要があります。マトリックスの残りの部分を変更せずに 1 つの値を変更する必要がある場合は、subrangePositionsインデックス内で 1 回だけ参照されるようにする必要があります。それ以外の場合は、新しいサブ範囲をベクターの任意の場所 (便利なように末尾) に割り当ててから、この新しいサブ範囲の位置をインデックスvaluesに格納する必要があります。subrangePositions
一般的な Colt ライブラリは、それ自体は非常に優れていますが、スパース マトリックスで作業する場合にはそれほど優れていないことに注意してください。特に最も頻繁な getAt() 操作では、スペースと時間を節約する優れた最適化。
ここで説明されている試行の setAt() 操作でさえ、多くの時間を節約します (ここでは方法が実装されています。つまり、設定後の自動圧縮なしで、要求と推定時間に基づいて実装できますが、圧縮によってまだ多くのストレージスペースが節約されます)時間の代償): 時間の節約はサブ範囲内のセルの数に比例し、スペースの節約はサブ範囲ごとのセルの数に反比例します。サブ範囲あたりのセル数が 2D マトリックスのセルの総数の平方根になるようなサブ範囲サイズを使用する場合は、適切な妥協が必要です (3D マトリックスを操作する場合は立方根になります)。
Colt 疎行列の実装で使用されるハッシュ技術には、多くのストレージ オーバーヘッドが追加され、衝突の可能性があるためアクセス時間が遅くなるという不都合があります。試行はすべての衝突を回避でき、最悪の場合に線形 O(n) 時間を O(1) 時間に短縮することを保証できます。ここで、(n) は可能な衝突の数です (スパース行列の場合、マトリックス内のデフォルト値以外のセルの数まで、つまり、マトリックスのサイズの合計数にハッシング充填係数に比例する係数を掛けた数まで (非スパース (完全なマトリックス) の場合)。
Colt で使用される RC (行圧縮) 技術は Tries に近いですが、これには別の代償が伴います。ここで使用される圧縮技術は、最も頻繁な読み取り専用の get() 操作のアクセス時間が非常に遅く、非常に遅いです。 setAt() 操作の圧縮。さらに、使用される圧縮は、直交性が保持されているトライのこのプレゼンテーションとは異なり、直交していません。試行は、ストライディング、転置 (整数巡回モジュラー操作に基づくストライディング操作と見なされる)、サブレンジング (およびソート ビューを含む一般的なサブセレクション) などの関連するビュー操作に対しても、この直交性を維持します。
将来、Colt が更新され、Tries を使用した別の実装 (つまり、HashSparseMatrix と RCSparseMatrix だけでなく、TrieSparseMatrix) が実装されることを願っています。アイデアはこの記事にあります。
Trove の実装 (int->int マップに基づく) も、Colt の HashedSparseMatrix に似たハッシュ技術に基づいています。つまり、同じ不便さがあります。試行はかなり高速になり、適度な追加スペースが消費されます (ただし、このスペースは、結果のマトリックス/トライで最終的なコンパクト()イオン操作を使用して、遅延時間で最適化され、Trove および Colt よりもさらに優れたものになる可能性があります)。
注: この Trie 実装は、特定のネイティブ型 (ここでは double) にバインドされています。これは任意です。ボックス化型を使用した一般的な実装には大きなスペース オーバーヘッドがある (そしてアクセス時間がはるかに遅い) ためです。ここでは、一般的な Vector ではなく、double のネイティブな 1 次元配列を使用しています。しかし、Tries に対してもジェネリック実装を派生させることは確かに可能です... 残念ながら、Java では、複数の実装 (ジェネリック Object 型またはそれぞれのネイティブ型)、型ファクトリを介してこれらすべての操作を提供します。言語は、ネイティブ実装を自動的にインスタンス化し、ファクトリを自動的に構築できる必要があります (現時点では、Java 7 でもそうではなく、.
Java Matrix Libraries をテストするための次のフレームワークは、これらの良いリストも提供します! https://lessthanoptimal.github.io/Java-Matrix-Benchmark/
テスト済みライブラリ:
* Colt
* Commons Math
* Efficient Java Matrix Library (EJML)
* Jama
* jblas
* JScience (Older benchmarks only)
* Matrix Toolkit Java (MTJ)
* OjAlgo
* Parallel Colt
* Universal Java Matrix Package (UJMP)
これは単純なようです。
row*maxcolums+column をインデックスとして使用して、データのバイナリ ツリーを使用できます。
アイテムを見つけるには、row*maxcolums+column を計算し、それを探してツリーをバイナリ検索します。そこにない場合は、null を返すことができます (それは О(log n) であり、n はオブジェクトを含むセルの数です)。
la4j (Linear Algebra for Java) ライブラリを参照してください。スパース行列のCRS (圧縮行ストレージ)とCCS (圧縮列ストレージ)内部表現をサポートしています。したがって、これらはスパース データの最も効率的で高速な内部構造です。
la4jでスパース行列を使用する簡単な例を次に示します。
Matrix a = new CRSMatrix(new double[][]{ // 'a' - CRS sparse matrix
{ 1.0, 0.0, 3.0 },
{ 0.0, 5.0, 0.0 },
{ 7.0, 0.0. 9.0 }
});
Matrix b = a.transpose(); // 'b' - CRS sparse matrix
Matrix c = b.multiply(a, Matrices.CCS_FACTORY); // 'c' = 'b' * 'a';
// 'c' - CCS sparse matrix
おそらく最速のランタイムソリューションではありませんが、私が思いついた最速のソリューションはうまくいくようです。Index クラスを作成し、次のように SortedMap のキーとして使用します。
SortedMap<Index, Object> entries = new TreeMap<Index, Object>();
entries.put(new Index(1, 4), "1-4");
entries.put(new Index(5555555555l, 767777777777l), "5555555555l-767777777777l");
System.out.println(entries.size());
System.out.println(entries.get(new Index(1, 4)));
System.out.println(entries.get(new Index(5555555555l, 767777777777l)));
私の Index クラスは次のようになります (Eclipse コード ジェネレーターの助けを借りて)。
public static class Index implements Comparable<Index>
{
private long x;
private long y;
public Index(long x, long y)
{
super();
this.x = x;
this.y = y;
}
public int compareTo(Index index)
{
long ix = index.x;
if (ix == x)
{
long iy = index.y;
if (iy == y)
{
return 0;
}
else if (iy < y)
{
return -1;
}
else
{
return 1;
}
}
else if (ix < x)
{
return -1;
}
else
{
return 1;
}
}
public int hashCode()
{
final int PRIME = 31;
int result = 1;
result = PRIME * result + (int) (x ^ (x >>> 32));
result = PRIME * result + (int) (y ^ (y >>> 32));
return result;
}
public boolean equals(Object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Index other = (Index) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
public long getX()
{
return x;
}
public long getY()
{
return y;
}
}
ネストされたマップを使用することもできますが、マトリックス計算を行う必要がある場合は、最適なオプションではない可能性があります
Map<Integer, Map<integer, Object>> matrix;
おそらく、オブジェクトの代わりに実際のデータにタプルを使用して、抽出後に簡単に操作できるようにします。
class Tuple<T extends yourDataObject> {
public final int x;
public final int y;
public final T object;
}
class Matrix {
private final Map<Integer, Map<interger, Tupple>> data = new...;
void add(int x, int y, Object object) {
data.get(x).put(new Tupple(x,y,object);
}
}
//etc
簡潔にするためにnullチェックなどは省略
HashMap のロック。StringBuilder (+ または String.format ではない) を使用して、インデックスを (文字列として) セパレーター (たとえば、「/」) で連結し、それをキーとして使用します。それよりも高速でメモリ効率の良いものはありません。スパース行列はすっごく20世紀です。:-)