자바의 희소 행렬 / 배열
저는 Java로 작성된 프로젝트에서 작업 중입니다.이 프로젝트는 매우 큰 2D 희소 배열을 구축해야합니다. 차이가 있다면 매우 드뭅니다. 어쨌든 :이 응용 프로그램의 가장 중요한 측면은 시간 측면에서 효율성입니다 (표준 2D 어레이를 사용할 수있을만큼 거의 무제한은 아니지만 메모리로드를 가정합니다. 주요 범위는 두 차원 모두에서 수십억입니다. ).
배열의 kajillion 셀 중 개체를 포함하는 수십만 개의 셀이 있습니다. 셀 내용을 매우 빠르게 수정할 수 있어야합니다.
어쨌든 :이 목적을 위해 특별히 좋은 라이브러리를 아는 사람이 있습니까? Berkeley, LGPL 또는 유사한 라이선스 여야합니다 (제품이 완전히 오픈 소스 일 수 없으므로 GPL 없음). 또는 홈브류 희소 배열 객체를 만드는 아주 간단한 방법이 있다면 그것도 괜찮을 것입니다.
MTJ를 고려 하고 있지만 품질에 대한 의견을 듣지 못했습니다.
해시 맵으로 구축 된 희소 배열은 자주 읽는 데이터에 대해 매우 비효율적입니다. 가장 효율적인 구현은 세그먼트가 분산 된 단일 벡터에 대한 액세스를 허용하는 Trie를 사용합니다.
Trie는 요소가 저장된 유효 위치를 가져 오거나 기본 저장소에 없는지 여부를 알기 위해 읽기 전용 TWO 배열 인덱싱 만 수행하여 요소가 테이블에 존재하는지 계산할 수 있습니다.
또한 희소 배열의 기본값에 대한 백업 저장소의 기본 위치를 제공 할 수 있으므로 반환 된 인덱스에 대한 테스트가 필요하지 않습니다. Trie는 가능한 모든 소스 인덱스가 최소한 기본값에 매핑되도록 보장하기 때문입니다. 백업 저장소의 위치 (0, 빈 문자열 또는 null 개체를 자주 저장하는 위치).
여러 작업이 끝날 때 백업 저장소의 크기를 최적화하는 "compact ()"작업과 함께 빠른 업데이트 시도를 지원하는 구현이 있습니다. 시도는 복잡한 해싱 함수가 필요하지 않고 읽기 충돌을 처리 할 필요가 없기 때문에 해시 맵보다 훨씬 빠릅니다 (해시 맵을 사용하면 읽기와 쓰기 모두에 충돌이 발생합니다. 다음 후보 위치 및 효과적인 소스 인덱스를 비교하기 위해 각각에 대한 테스트 ...)
또한 Java Hashmap은 객체에 대해서만 색인을 생성 할 수 있으며, 각 해시 된 소스 색인에 대해 Integer 객체를 생성하는 것은 가비지 수집기에 스트레스를주기 때문에 메모리 작업 측면에서 비용이 많이 듭니다. .
나는 JRE가 느린 HashMap <Integer, Object> 또는 LongTrieMap <Object>의 기본 구현으로 IntegerTrieMap <Object>를 더 느린 HashMap <Long, Object>의 기본 구현으로 포함하기를 정말로 바랐습니다. 여전히 그렇지 않습니다.
Trie가 무엇인지 궁금 할 수 있습니다.
이것은 좌표를 벡터의 정수 위치로 매핑 할 수있는 작은 정수 배열 (행렬의 전체 좌표 범위보다 작은 범위에 있음)입니다.
예를 들어 0이 아닌 값을 몇 개만 포함하는 1024 * 1024 행렬을 원한다고 가정합니다. 해당 행렬을 1024 * 1024 요소 (100 만 개 이상)를 포함하는 배열에 저장하는 대신 16 * 16 크기의 하위 범위로 분할 할 수 있으며 이러한 하위 범위는 64 * 64 만 필요합니다.
이 경우 Trie 인덱스에는 64 * 64 정수 (4096) 만 포함되며 최소 16 * 16 데이터 요소 (기본 0 또는 희소 행렬에서 발견되는 가장 일반적인 하위 범위 포함)가 있습니다.
그리고 값을 저장하는 데 사용되는 벡터는 서로 동일한 하위 범위에 대해 1 개의 사본 만 포함합니다 (대부분 0으로 가득 차 있으며 동일한 하위 범위로 표시됨).
따라서와 같은 구문을 사용하는 대신 다음과 같은 구문을 사용합니다 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()메서드가 가장 적합한 크기를 결정할 수 있어야합니다.
이러한 분할 부분 범위의 크기가 달라질 수 있다면, 대신 정적의이 부분 범위의 크기에 인스턴스 멤버를 추가 할 필요가있을 것입니다 SUBRANGE_POSITIONS, 그리고 정적 메서드를 만들기 위해 int subrangeOf(int i, int j)및 int positionOffsetOf(int i, int j)비 정적으로; 및 초기화 배열 DEFAULT_POSITIONS과는 DEFAULT_VALUES떨어 뜨리거나 다르게 재정의해야합니다.
인터리빙을 지원하려면 기본적으로 기존 값을 거의 동일한 크기의 두 개로 나누는 것으로 시작합니다 (둘 다 최소 하위 범위 크기의 배수이고 첫 번째 하위 집합은 두 번째 하위 범위보다 하나 더 많은 하위 범위를 가질 수 있음). 일치하는 인터리빙을 찾기 위해 모든 연속 위치에서 더 큰 것을 스캔합니다. 그런 다음이 값을 일치 시키려고합니다. 그런 다음 하위 집합을 절반 (최소 하위 범위 크기의 배수)으로 나누어 반복적으로 반복하고 이러한 하위 집합과 일치하도록 다시 스캔합니다 (이는 하위 집합의 수에 2를 곱합니다. subrangePositions 인덱스의 크기는 효과적인 압축을 제공하는지 확인하기 위해 값의 기존 크기와 비교하여 값의 가치가 있습니다 (그렇지 않은 경우 여기서 중지합니다. 인터리빙 압축 프로세스에서 직접 최적의 하위 범위 크기를 찾았습니다. 이 경우 압축 중에 하위 범위 크기는 변경 가능합니다.
그러나이 코드는 0이 아닌 값을 할당하고 data추가 (0이 아닌) 하위 범위에 대해 배열을 재 할당 compact()하는 setAt(int i, int j, double value)방법과 중복이있을 때이 데이터의 저장소를 최적화 할 수 있는 방법 ( 이 방법을 사용하여 할당을 수행 한 후 )을 보여줍니다. 데이터 내에서 통합 될 수 있고 subrangePositions배열 의 동일한 위치에서 다시 인덱싱 될 수있는 하위 범위 .
어쨌든 trie의 모든 원칙은 거기에서 구현됩니다.
배열의 이중 인덱스 배열 (각각 개별적으로 할당 됨) 대신 단일 벡터를 사용하여 행렬을 표현하는 것이 항상 더 빠릅니다 (그리고 메모리가 더 콤팩트하여 더 나은 위치를 의미합니다). 개선은
double getAt(int, int)방법 에서 볼 수 있습니다 !많은 공간을 절약하지만 값을 할당 할 때 새 하위 범위를 재 할당하는 데 시간이 걸릴 수 있습니다. 이러한 이유로 하위 범위가 너무 작아서는 안됩니다. 그렇지 않으면 행렬을 설정하기 위해 재 할당이 너무 자주 발생합니다.
공통 하위 범위를 감지하여 초기 대형 행렬을보다 간결한 행렬로 자동 변환 할 수 있습니다. 그런 다음 일반적인 구현에는
compact()위와 같은 메서드가 포함됩니다 . 그러나 get () 액세스가 매우 빠르고 set ()이 매우 빠르면 압축 할 공통 하위 범위가 많으면 compact ()가 매우 느릴 수 있습니다 (예 : 자체적으로 희소가 아닌 무작위로 채워진 큰 행렬을 뺄 때). , 또는 0으로 곱하기 :이 경우 새 트리를 인스턴스화하고 이전 트리를 삭제하여 트리를 재설정하는 것이 더 간단하고 훨씬 빠릅니다).공통 하위 범위는 데이터의 공통 저장소를 사용하므로이 공유 데이터는 읽기 전용이어야합니다. 나머지 행렬을 변경하지 않고 단일 값을 변경해야하는 경우 먼저
subrangePositions인덱스 에서 한 번만 참조되는지 확인해야합니다 . 그렇지 않으면values벡터 의 모든 위치 (편리하게 끝 부분)에 새 하위 범위를 할당 한 다음이 새 하위 범위의 위치를subrangePositions인덱스에 저장해야합니다 .
일반 Colt 라이브러리는 비록 매우 훌륭하지만 희소 행렬에서 작업 할 때는 그다지 좋지 않습니다. 왜냐하면 현재 시도에 대한 지원을 구현하지 않는 해싱 (또는 행 압축) 기술을 사용하기 때문입니다. 특히 가장 빈번한 getAt () 작업에서 공간 과 시간을 절약 하는 탁월한 최적화 입니다.
시도를 위해 여기에 설명 된 setAt () 작업조차도 많은 시간을 절약합니다 (여기서는 방법이 구현됩니다. 즉, 설정 후 자동 압축 없이도 구현됩니다. 이는 압축이 여전히 많은 저장 공간을 절약 할 수있는 예상 시간과 수요에 따라 구현할 수 있습니다.) 시간의 가격) : 시간 절약은 하위 범위의 셀 수에 비례하고 공간 절약은 하위 범위 당 셀 수에 반비례합니다. 하위 범위 크기를 사용하는 경우 하위 범위 당 셀 수는 2D 행렬의 총 셀 수에 대한 제곱근입니다 (3D 행렬로 작업 할 때 세제곱근이 됨).
Colt 희소 행렬 구현에 사용되는 해싱 기술은 많은 스토리지 오버 헤드를 추가하고 충돌 가능성으로 인해 액세스 시간이 느려지는 불편 함이 있습니다. 시도는 모든 충돌을 피할 수 있으며 최악의 경우 선형 O (n) 시간을 O (1) 시간으로 절약 할 수 있습니다. 여기서 (n)은 가능한 충돌 수입니다 (희소 행렬의 경우 행렬의 기본 값이 아닌 셀 수까지, 즉 행렬의 총 크기 수에 해싱 채우기 비율에 비례하는 계수를 곱한 값 (비 희소, 즉 전체 행렬)
Colt에서 사용되는 RC (row-compressed) 기술은 Tries보다 더 가깝지만 이것은 다른 가격에 있습니다. 여기에 사용 된 압축 기술은 가장 빈번한 읽기 전용 get () 작업에 대한 액세스 시간이 매우 느리고 매우 느립니다. setAt () 작업을위한 압축. 또한 사용 된 압축은 직교성이 유지되는 Tries 프레젠테이션과 달리 직교가 아닙니다. 시도는 또한 striding, transposition (정수 순환 모듈 식 연산을 기반으로 한 striding 연산으로 표시됨), 하위 범위 지정 (및 일반적으로 뷰 정렬을 포함한 하위 선택)과 같은 관련보기 연산에 대해이 직교성을 유지합니다.
Colt가 향후 Tries를 사용하여 다른 구현을 구현하도록 업데이트되기를 바랍니다 (즉 HashSparseMatrix 및 RCSparseMatrix 대신 TrieSparseMatrix). 아이디어는이 기사에 있습니다.
The Trove implementation (based in int->int maps) are also based on hashing technics similar to the Colt's HashedSparseMatrix, i.e. they have the same inconvenience. Tries will be a lot faster, with a moderate additional space consumed (but this space can be optimized and become even better than Trove and Colt, in a deferred time, using a final compact()ion operation on the resulting matrix/trie).
참고 :이 Trie 구현은 특정 네이티브 유형 (여기서는 double)에 바인딩됩니다. 복싱 유형을 사용하는 일반적인 구현은 엄청난 공간 오버 헤드를 가지므로 (접근 시간이 훨씬 느림) 이는 자발적입니다. 여기서는 일반적인 벡터가 아닌 기본 1 차원 배열의 double을 사용합니다. 그러나 Tries에 대해서도 제네릭 구현을 유도하는 것은 확실히 가능합니다 ... 불행히도 Java는 여러 구현을 작성하는 것을 제외하고 (일반 객체 유형 또는 각 네이티브 유형) 및 유형 팩토리를 통해 이러한 모든 작업을 제공합니다. 언어는 자동으로 네이티브 구현을 인스턴스화하고 팩토리를 자동으로 구축 할 수 있어야합니다 (현재는 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을 반환 할 수 있습니다 (n은 객체를 포함하는 셀의 수인 경우 О (log n)).
아마도 가장 빠른 런타임 솔루션은 아니지만 가장 빠른 솔루션은 작동하는 것 같습니다. 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;
}
}
You migth look at la4j (Linear Algebra for Java) library. It supports CRS (Compressed Row Storage) as well as CCS (Compressed Column Storage) internal representaions for sparse matrices. So, these are the most efficient and fast internal stuctures for sparse data.
Here is the brief example of using sparse matrices in 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
you could just use a nested map although if you need to do matrix calculus on it that might not be the best option
Map<Integer, Map<integer, Object>> matrix;
maybe instead of object use some tuple for the actual data so you can work with it easier after extraction, something like:
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 check etc omitted for brevity
HashMap rocks. Just concatenate the indexes (as strings) with a separator, say '/', using StringBuilder (not + or String.format), and use that as the key. You can't get faster and more memory-efficient than that. Sparse matrices are soo 20th century. :-)
참고URL : https://stackoverflow.com/questions/390181/sparse-matrices-arrays-in-java
'Programing' 카테고리의 다른 글
| 확장 가능한 목록보기 그룹 아이콘 표시기를 오른쪽으로 이동 (0) | 2020.11.26 |
|---|---|
| Ajax 게시물의 JQuery 확인 성공 (0) | 2020.11.26 |
| CVS에서 Git으로의 마이그레이션 도구가 있습니까? (0) | 2020.11.25 |
| Java 게임에서 가비지 수집 지연을 방지하려면 어떻게해야합니까? (0) | 2020.11.25 |
| Android 스크롤 끝에서 동적으로 Listview를로드합니까? (0) | 2020.11.25 |