我正在开发一个用Java编写的项目,它要求我构建一个非常大的2-D稀疏数组.非常稀疏,如果这有所不同.无论如何:这个应用程序最关键的方面是时间上的效率(假设内存负载,虽然不能无限制地允许我使用标准的2-D阵列 - 关键范围是两个维度的数十亿).
在阵列中的kajillion细胞中,将有数十万个细胞包含一个物体.我需要能够很快地修改单元格内容.
无论如何:有没有人为此目的知道一个特别好的图书馆？它必须是伯克利,LGPL或类似的许可证(没有GPL,因为该产品不能完全开源).或者,如果只有一种非常简单的方法来制作自制的稀疏数组对象,那也没关系.
我正在考虑MTJ,但没有听到任何关于其质量的意见.
使用哈希映射构建的Sparsed数组对于频繁读取的数据效率非常低.最有效的实现使用Trie,允许访问分段分段的单个向量.
Trie可以通过仅执行只读两个数组索引来获得存储元素的有效位置,或者知道它是否不存在于底层存储中,来计算表中是否存在元素.
它还可以在后备存储中为缺省数组的默认值提供默认位置,这样您就不需要对返回的索引进行任何测试,因为Trie保证所有可能的源索引都至少映射到默认值在后备存储中的位置(您经常存储零,或空字符串或空对象).
There exists implementations that support fast-updatable Tries, with an otional "compact()" operation to optimze the size of the backing store at end of multiple operations. Tries are MUCH faster than hashmaps, because they don't need any complex hashing function, and don't need to handle collisions for reads (With Hashmaps, you have collision BOTH for reading and for writing, this requires a loop to skip to the next candidate position, and a test on each of them to compare the effective source index...)
In addition, Java Hashmaps can only index on Objects, and creating an Integer object for each hashed source index (this object creation will be needed for every read, not just writes) is costly in terms of memory operations, as it stresses the garbage collector.
I really hoped that the JRE included an IntegerTrieMap
You may wonder what is a Trie?
It's just a small array of integers (in a smaller range than the full range of coordinates for your matrix) that allows mapping the coordinates into an integer position in a vector.
For example suppose you want a 1024*1024 matrix containing only a few non zero values. Instead of storing that matrix in a array containing 1024*1024 elements (more than 1 million), you may just want to split it into subranges of size 16*16, and you'll just need 64*64 such subranges.
In that case, the Trie index will contain just 64*64 integers (4096), and there will be at least 16*16 data elements (containing the default zeroes, or the most common subrange found in your sparse matrix).
And the vector used to store the values will contain only 1 copy for subranges that are equal with each other (most of them being full of zeroes, they will be represented by the same subrange).
So instead of using a syntax like matrix[i][j], you'd use a syntax like:
trie.values[trie.subrangePositions[(i & ~15) + (j >> 4)] +
((i & 15) << 4) + (j & 15)]
which will be more conveniently handled using an access method for the trie object.
Here is an example, built into a commented class (I hope it compiles OK, as it was simplified; signal me if there are errors to correct):
/** * Implement a sparse matrix. Currently limited to a static size * (SIZE_I,SIZE_I). */ 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* (otherSubrangePosition == subrangePosition), * 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索引的大小值与该值的现有大小相比较,以查看它是否提供有效压缩(如果没有,则停在那里:您已经直接从交错压缩过程中找到了最佳子范围大小).在这种情况下; 在压缩过程中,子范围大小将是可变的.
但是此代码显示了如何data为其他(非零)子范围分配非零值并重新分配数组,以及如何在存在重复时优化(compact()使用该setAt(int i, int j, double value)方法执行分配后)此数据的存储可以在数据中统一的子范围,并在subrangePositions数组中的相同位置重新编制索引.
无论如何,trie的所有原则都在那里实现:
使用单个向量而不是双索引数组(每个都单独分配)来表示矩阵总是更快(并且在内存中更紧凑,意味着更好的局部性).在double getAt(int, int)方法中可以看到改进!
You save a lot of space, but when assigning values it may take time to reallocate new subranges. For this reason, the subranges should not be too small or reallocations will occur too frequently for setting up your matrix.
It is possible to transform an initial large matrix automatically into a more compact matrix by detecting common subranges. A typical implementation will then contain a method such as compact() above. However, if get() access is very fast and set() is quite fast, compact() may be very slow if there are lots of common subranges to compress (for example when substracting a large non-sparse randomly-filled matrix with itself, or multiplying it by zero: it will be simpler and much faster in that case to reset the trie by instanciating a new one and dropping the old one).
Common subranges use common storage in the data, so this shared data must be read-only. If you must change a single value without changing the rest of the matrix, you must first make sure that it is referenced only one time in the subrangePositions index. Otherwise you'll need to allocate a new subrange anywhere (conveniently at end) of the values vector, and then store the position of this new subrange into the subrangePositions index.
Note that the generic Colt library, though very good as it is, is not as good when working on sparse matrice, because it uses hashing (or row-compresssed) technics which do not implement the support for tries for now, despite it is an excellent optimization, which is both space-saving and time-saving, notably for the most frequent getAt() operations.
Even the setAt() operation described here for tries saves lot of time (the way is is implemented here, i.e. without automatic compaction after setting, which could still be implemented based on demand and estimated time where compaction would still save lot of storage space at the price of time): the time saving is proportional to the number of cells in subranges, and space saving is inversely proportional to the number of cells per subrange. A good compromize if then to use a subrange size such the number of cells per subrange is the square root of the total number of cells in a 2D matrix (it would be a cubic root when working with 3D matrice).
Hashing technics used in Colt sparse matrix implementations have the inconvenience that they add a lot of storage overhead, and slow access time due to possible collisions. Tries can avoid all collisions, and can then warranty to save linear O(n) time to O(1) time in the worst cases, where (n) is the number of possible collisions (which, in case of sparse matrix, may be up to the number of non-default-value cells in the matrix, i.e. up to the total number of size of the matrix times a factor proportional to the hashing filling factor, for a non-sparse i.e. full matrix).
The RC (row-compressed) technics used in Colt are nearer from Tries, but this is at another price, here the compression technics used, that have very slow access time for the most frequent read-only get() operations, and very slow compression for setAt() operations. In addition, the compression used is not orthogonal, unlike in this presentation of Tries where orthogonality is preserved. Tries would also be preserve this orthogonality for related viewing operations such as striding, transposition (viewed as a striding operation based on integer cyclic modular operations), subranging (and subselections in general, including with sorting views).
I just hope that Colt will be updated in some future to implement another implementation using Tries (i.e. TrieSparseMatrix instead of just HashSparseMatrix and RCSparseMatrix). The ideas are in this article.
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).
Note: this Trie implementation is bound to a specific native type (here double). This is voluntary, because generic implementation using boxing types have a huge space overhead (and are much slower in acccess time). Here it just uses native unidimensional arrays of double rather than generic Vector. But it is certainly possible to derive a generic implementation as well for Tries... Unfortunately, Java still does not allow writing really generic classes with all the benefits of native types, except by writing multiple implementations (for a generic Object type or for each native type), and serving all these operation via a type factory. The language should be able to automatically instanciate the native implementations and build the factory automatically (for now it is not the case even in Java 7, and this is something where .Net still maintains its advantage for really generic types that are as fast as native types).
遵循框架来测试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)
京公网安备 11010802040832号 | 京ICP备19059560号-6 