jsp*_*cal 14
该柯尔特库有一个Java的稀疏矩阵实现.
您也可以使用Berkeley DB作为存储引擎.
现在,如果您的计算机具有足够的实际RAM(至少9 GB可用),则可以在Java命令行中增加堆大小.
100,000 x 100,000 = 10,000,000,000(100亿)条目.即使您存储单字节条目,仍然在10 GB附近 - 您的机器甚至拥有那么多物理内存,更不用说有意愿将这么多内容分配给单个进程了吗？
你可能需要考虑某种方式,只在任何给定时间将矩阵的一部分保留在内存中,其余的缓冲在磁盘上.
听起来你需要一个稀疏矩阵.其他人已经提出了可以满足您需求的良好第三方实施......
根据您的应用程序,只需使用Map作为矩阵数据的后备存储,就可以在没有第三方矩阵库的情况下离开.的种类...
public class SparseMatrix<T> {
private T defaultValue;
private int m;
private int n;
private Map<Integer, T> data = new TreeMap<Integer, T>();
/// create a new matrix with m rows and n columns
public SparseMatrix(int m, int n, T defaultValue) {
this.m = m;
this.n = n;
this.defaultValue = defaultValue;
}
/// set value at [i,j] (row, col)
public void setValueAt(int i, int j, T value) {
if (i >= m || j >= n || i < 0 || j < 0)
throw new IllegalArgumentException(
"index (" + i + ", " +j +") out of bounds");
data.put(i * n + j, value);
}
/// retrieve value at [i,j] (row, col)
public T getValueAt(int i, int j) {
if (i >= m || j >= n || i < 0 || j < 0)
throw new IllegalArgumentException(
"index (" + i + ", " +j +") out of bounds");
T value = data.get(i * n + j);
return value != null ? value : defaultValue;
}
}
一个简单的测试用例说明了SparseMatrix的用法:
public class SparseMatrixTest extends TestCase {
public void testMatrix() {
SparseMatrix<Float> matrix =
new SparseMatrix<Float>(100000, 100000, 0.0F);
matrix.setValueAt(1000, 1001, 42.0F);
assertTrue(matrix.getValueAt(1000,1001) == 42.0);
assertTrue(matrix.getValueAt(1001,1000) == 0.0);
}
}
这不是最有效的方法,因为矩阵中的每个非默认条目都存储为Object.根据您期望的实际值的数量,这种方法的简单性可能胜过集成第三方解决方案(并且可能再次根据您的情况处理其许可证).
在上述SparseMatrix实现中添加矩阵运算(如乘法)应该是直截了当的(并留给读者练习;-)
有许多可能的解决方案取决于您拥有多少内存,阵列实际上是多么稀疏,以及访问模式将是什么.
如果100K*100K*8的计算量小于机器上供JVM使用的物理内存量,则简单的非稀疏阵列是可行的解决方案.
如果数组是稀疏的,(例如)75%或更多的元素为零,那么您可以使用稀疏数组库来节省空间.已经提出了各种替代方案,但在所有情况下,如果能够为您节省足够的成本,您仍然需要解决问题.计算出有多少非零元素,乘以8(给你双精度)和(比如)4来计算稀疏数组的开销.如果这小于您可以为JVM提供的物理内存量,那么稀疏阵列是一种可行的解决方案.
如果稀疏和非稀疏数组(在内存中)不起作用,事情会变得更复杂,任何解决方案的可行性将取决于数组数据的访问模式.
一种方法是将数组表示为以MappedByteBuffer形式映射到内存的文件.假设您没有足够的物理内存来将整个文件存储在内存中,那么您将很难进入虚拟内存系统.因此,最好是您的算法只需要随时对阵列的连续部分进行操作.否则,你可能会死于交换.
第二种方法是第一种方法的变体.一次将数组/文件映射到一个部分,完成后,取消映射并移至下一部分.这仅适用于算法在节中处理数组的情况.
第三种方法是使用像BDB这样的轻量级数据库来表示阵列.这将比任何内存中的解决方案慢,因为读取数组元素将转换为光盘访问.但如果你弄错了它就不会像内存映射方法那样杀死系统.(如果在Linux/Unix上执行此操作,系统的磁盘块缓存可能会加快速度,具体取决于算法的阵列访问模式)
第四种方法是使用分布式存储器高速缓存.这将用网络i/o替换光盘i/o,很难说这是好事还是坏事.
第五种方法是分析您的算法,看它是否适合作为分布式算法实现; 例如,在不同的机器上具有阵列的部分和算法的相应部分.
| 归档时间： |
|
| 查看次数： |
3805 次 |
| 最近记录： |