稀疏矩阵，也称为稀疏数组，是用于表示大多数元素为零或未定义的矩阵的数据结构。与传统矩阵不同，稀疏矩阵仅存储非零元素，这使得它们可以有效地存储具有大量零的大型矩阵。
使用哈希图实现稀疏矩阵对于频繁读取的数据可能效率低下，因为哈希图会引入冲突对于读取和写入，需要复杂的散列函数和循环来处理每个候选位置并将其与源索引进行比较。
更有效的方法是使用Trie（Trie Radix Tree）结构，该结构允许直接访问分布有段的单个向量。尝试只需两次数组索引操作即可确定表中是否存在元素，从而提供快速只读访问和默认值后备存储中的默认位置。
这种方法避免了对返回的任何测试索引，保证所有源索引至少映射到后备存储中的默认位置，并通过可选的“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中文网其他相关文章！
