稀疏矩陣，也稱為稀疏數組，是用來表示大多數元素為零或未定義的矩陣的資料結構。與傳統矩陣不同，稀疏矩陣僅儲存非零元素，這使得它們可以有效地儲存具有大量零的大型矩陣。
使用雜湊圖實作稀疏矩陣對於頻繁讀取的資料可能效率低下，因為雜湊圖會引入衝突對於讀取和寫入，都需要複雜的雜湊函數和迴圈來處理每個候選位置並與來源索引進行比較。
更有效的方法是使用允許直接存取的 Trie（Trie Radix Tree）結構到單一向量，其中段被分佈。嘗試只需兩次數組索引操作即可確定表中是否存在元素，從而提供快速只讀存取和預設值後備儲存中的預設位置。
這種方法避免了對傳回的任何測試索引，保證所有來源索引至少對應到後備儲存中的預設位置，並支援快速可更新的Tries 和可選的「compact()」操作，以在多個操作結束時最佳化儲存空間。
Tries 比hashmap 快得多，因為它們不需要複雜的雜湊函數或衝突處理，而且它們可以與Java IntegerTrieMap 和LongTrieMap 高效地配合用於Integer 和Long 索引，儘管這些目前不包含在JRE 中。
範例程式碼：
<code class="java">public class DoubleTrie {
// Matrix 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];
private static final double DEFAULT_VALUES[] = new double[SUBRANGE_POSITIONS](DEFAULT_VALUE);
// Internal fast computations
private static final int subrangeOf(int i, int j) {
return (i >> SUBRANGEBITS_I) * SUBRANGE_J + (j >> SUBRANGEBITS_J);
}
private static final int positionOffsetOf(int i, int j) {
return (i & SUBRANGEMASK_I) * SUBRANGE_J + (j & SUBRANGEMASK_J);
}
// Internal member variables
private double values[];
private int subrangePositions[];
private boolean isSharedValues;
private boolean isSharedSubrangePositions;
// Internal method
private final void reset(double[] values, int[] subrangePositions) {
this.isSharedValues = (this.values = values) == DEFAULT_VALUES;
this.isSharedSubrangePositions = (this.subrangePositions = subrangePositions) == DEFAULT_POSITIONS;
}
// Reset method
public void reset(double initialValue = DEFAULT_VALUE) {
reset((initialValue == DEFAULT_VALUE) ? DEFAULT_VALUES : new double[SUBRANGE_POSITIONS](initialValue), DEFAULT_POSITIONS);
}
// Default constructor
public DoubleTrie(double initialValue = DEFAULT_VALUE) {
this.reset(initialValue);
}
// Immutable default instance
public static DoubleTrie DEFAULT_INSTANCE = new DoubleTrie();
// Copy constructor
public DoubleTrie(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
public double getAt(int i, int j) {
return values[subrangePositions[subrangeOf(i, j)] + positionOffsetOf(i, j)];
}
// Fast indexed setter
public double setAt(int i, int j, double value) {
int subrange = subrangeOf(i, j);
int positionOffset = positionOffsetOf(i, j);
// Check if the assignment will change anything
int subrangePosition, valuePosition;
if (Double.compare(values[valuePosition = (subrangePosition = subrangePositions[subrange]) + positionOffset], value) != 0) {
// The assignment will change something, check if the affected subrange is shared
if (isSharedValues) {
values = values.clone();
isSharedValues = false;
}
// Scan all other subranges to check if the affected position is shared
for (int otherSubrange = subrangePositions.length; --otherSubrange >= 0;) {
if (otherSubrange != subrange) {
continue; // Ignore the target subrange
}
// Check if the target position is shared by another subrange
if ((otherSubrangePosition = subrangePositions[otherSubrange]) >= valuePosition && otherSubrangePosition + SUBRANGE_POSITIONS < valuePosition) {
// The target position is shared, we need to make it unique by cloning the subrange and copying all its values to the end of the new vector
if (isSharedSubrangePositions) {
subrangePositions = subrangePositions.clone();
isSharedSubrangePositions = false;
}
values = DoubleTrie.arraysetlength(values, (subrangePositions[subrange] = subrangePositions = values.length) + SUBRANGE_POSITIONS);
valuePosition = subrangePositions + positionOffset;
break;
}
}
// Assign the new value
values[valuePosition] = value;
}
return value;
}
// Compact storage method
public void compact() {
int oldValuesLength = values.length;
int newValuesLength = 0;
for (int oldPosition = 0; oldPosition < oldValuesLength; oldPosition += SUBRANGE_POSITIONS) {
int oldPosition = positions[subrange];
boolean 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
for (subrange = subrangePositions.length; --subrange >= 0;) {
if (subrangePositions[subrange] == oldPosition) {
subrangePositions[subrange] = newPosition;
}
}
break;
}
}
if (!commonSubrange) {
// Move down the non-common values
if (!commonSubrange && oldPosition != newValuesLength) {
DoubleTrie.arraycopy(values, oldPosition, newValuesLength, SUBRANGE_POSITIONS);
newValuesLength += SUBRANGE_POSITIONS;
}
}
}
// Check the number of compressed values
if (newValuesLength < oldValuesLength) {
values = values.arraysetlength(newValuesLength);
isSharedValues = false;
}
}
}</code>以上是如何使用 Trie 資料結構來高效實現稀疏矩陣，與傳統雜湊圖相比提供更快的唯讀存取和優化的儲存？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
