Scattered arrays built with hashmaps are very inefficient for frequently read data. The most efficient implementations use Trie, which allows you to access a single vector in which the segments are distributed.
A Trie can calculate whether an item is present in a table by performing read-only TWO indexing to get the effective position in which the item is stored, or to know if it is not in the underlying storage.
It can also provide a default position in the backup storage for the default value for a sparse array, so you do not need ANY test on the returned index, since Trie ensures that all possible source indexes will be displayed at least to the default position in the backup storage copies (where you often store null or empty string or null object).
There are implementations that support fast-updating Tries with a standalone, compact operation to optimize storage size at the end of several operations. Three times much faster than hashmaps, because they don’t need a complex hash function and do not need to handle conflicts for reading (using Hashmaps you have a BOTH collision for reading and writing, it requires the loop to skip the next candidate position and test for each of them to compare the effective source index ...)
In addition, Java Hashmaps can only index objects and create an Integer object for each hashed source index (creating this object is required for every read, not just write) is expensive in terms of memory operations, as it emphasizes the garbage collector.
I really hoped the JRE included IntegerTrieMap <Object> as the default implementation for the slow HashMap <Integer, Object> or LongTrieMap <Object> as the default implementation for the slower HashMap <Long, Object> ... But that's it not so yet.
You may wonder what is Trie?
This is just a small array of integers (in a smaller range than the full range of coordinates for your matrix), which allows you to display the coordinates in an integer position in the vector.
For example, suppose you want a 1024 * 1024 matrix that contains only a few non-zero values. Instead of storing this matrix in an array containing 1024 * 1024 elements (more than 1 million), you can simply split it into 16 * 16 subbands, and you only need 64 * 64 such subbands.
In this case, the Trie index will contain only 64 * 64 integers (4096), and there will be at least 16 * 16 data elements (containing zero default values or the most common subrange found in your sparse matrix).
And the vector used to store the values will contain only 1 copy for subbands that are equal to each other (most of them are filled with zeros, they will be represented by the same subband).
Therefore, instead of using syntax like matrix[i][j] you should use syntax like:
trie.values[trie.subrangePositions[(i & ~15) + (j >> 4)] + ((i & 15) << 4) + (j & 15)]
which will be more conveniently handled using the access method for the trie object.
Here is an example built into the class with comments (I hope it compiles OK, as it has been simplified, let me know if there are any errors to fix):
public class DoubleTrie { public static final int SIZE_I = 1024; public static final int SIZE_J = 1024; public static final double DEFAULT_VALUE = 0.0; private static final int SUBRANGEBITS_I = 4; private static final int SUBRANGEBITS_J = 4; 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; 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); 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); } 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])) { if (value1 < value2) return -1; if (value1 > value2) return 1; if (value1 == value2) return 0; if (value1 == value1) return -1; if (value2 == value2) return 1; long raw1, raw2; if ((raw1 = Double.doubleToRawLongBits(value1)) != (raw2 = Double.doubleToRawLongBits(value2))) return raw1 < raw2 ? -1 : 1; } } return 0; } throw new ArrayIndexOutOfBoundsException( "The positions and length can't be negative"); } public static final int arraycompare( final double[] values, final int position1, final int position2, final int length) { return arraycompare(values, position1, values, position2, length); } 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; } public static final boolean arrayequals( final double[] values, final int position1, final int position2, final int length) { return arrayequals(values, position1, values, position2, length); } public static final void arraycopy( final double[] values, final int srcPosition, final int dstPosition, final int length) { arraycopy(values, srcPosition, values, dstPosition, length); } 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; } private double values[]; private int subrangePositions[]; private bool isSharedValues; private bool isSharedSubrangePositions; private final reset( final double[] values, final int[] subrangePositions) { this.isSharedValues = (this.values = values) == DEFAULT_VALUES; this.isSharedsubrangePositions = (this.subrangePositions = subrangePositions) == DEFAULT_POSITIONS; } public reset(final double initialValue = DEFAULT_VALUE) { reset( (initialValue == DEFAULT_VALUE) ? DEFAULT_VALUES : new double[SUBRANGE_POSITIONS](initialValue), DEFAULT_POSITIONS); } public DoubleTrie(final double initialValue = DEFAULT_VALUE) { this.reset(initialValue); } public static DoubleTrie DEFAULT_INSTANCE = new DoubleTrie(); 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()); } public double getAt(final int i, final int j) { return values[subrangePositions[subrangeOf(i, j)] + positionOffsetOf(i, j)]; } public double setAt(final int i, final int i, final double value) { final int subrange = subrangeOf(i, j); final int positionOffset = positionOffsetOf(i, j);
Note: this code is not complete, since it processes one matrix size, and its compactor is limited to detect only common subbands without alternating them.
In addition, the code does not determine where it is the best width or height for dividing the matrix into subbands (for x or y coordinates) according to the size of the matrix. It uses only the same sizes of the static subrange 16 (for both coordinates), but it can be convenient with any other small cardinality 2 (but non-force 2 will slow down the internal methods int indexOf(int, int) and int offsetOf(int, int) ). independently for both coordinates and up to the maximum width or height of the matrix. Otherwise, the compact() method should be able to determine the best fit.
If the size of the shared subranges can vary, then you will need to add instance instances for these subband sizes instead of the static SUBRANGE_POSITIONS and make the static methods int subrangeOf(int i, int j) and int positionOffsetOf(int i, int j) unsteady; and the DEFAULT_POSITIONS and DEFAULT_VALUES initialization arrays will need to be dropped or redefined in different ways.
If you want to support interleaving, you will basically start by dividing the existing values into two approximately the same size (both of which are multiples of the minimum size of the subrange, with the first subset possibly having another subrange than the second), and you will scan the larger one at all subsequent positions to find the corresponding alternation; then you will try to match these values. Then you will cyclically recursively divide the subsets in half (also a multiple of the minimum size of the subrange), and you will scan again to fit these subsets (this will multiply the number of subsets by 2: you have to wonder if the size of the index subrangePositions is worth the value compared to the existing one by the size of the values to see if it provides efficient compression (if not, you stop at it: you find the optimal size of the subband directly from the interlacing compression process ). Case, the subband size is changeable during compaction.
But this code shows how you assign non-zero values and redistribute the data array for additional (non-zero) subranges, and then how you can optimize (using compact() after completing assignments using setAt(int i, int j, double value) ) storage of this data in the presence of duplicated subranges that can be unified within the data and re-indexed at the same position in the subrangePositions array.
In any case, all the principles of trie are implemented there:
It is always faster (and more compact in memory, which means better locality) to represent a matrix using one vector instead of an array with two indices (each of which is allocated separately). The improvement is visible in the double getAt(int, int) method!
You save a lot of space, but when assigning values, it may take time to reallocate new subbands. For this reason, the subranges should not be too small, or the redistribution will occur too often to tune your matrix.
You can automatically convert the initial large matrix to a more compact matrix by detecting common subbands. 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 () can be very slow if there are many common subranges for compression (for example, when subtracting a large unallocated randomly filled matrix with itself, or multiplying it by zero : in this case it will be simpler and much faster to reset trie by initializing a new one and deleting the old one).
Shared subbands use shared storage in the data, so this shared data should be read-only. If you must change one value without changing the rest of the matrix, you must first ensure that it is referenced only once in the subrangePositions index. Otherwise, you will need to select a new subrange anywhere (conveniently at the end) of the values vector, and then save the position of this new subrange in the subrangePositions index.
Please note that the Colt general library, although very good, is not so good at working with a sparse matrix, because it uses hashing (or row compression) of techniques that do not yet implement support for attempts, despite this excellent optimization, which saves time and , especially for the most common getAt () operations.
Even the setAt () operation described here for attempts saves a lot of time (the method is implemented here, that is, without automatic compaction after installation, which can still be implemented based on demand and estimated time, when compaction will still save a lot of storage space at a price time): time saving is proportional to the number of cells in the subbands, and space saving is inversely proportional to the number of cells in each subband. A good compromise, if you then use the size of the subrange, this number of cells in each subband is the square root of the total number of cells in the 2D matrix (this will be the cubic root when working with the 3D matrix).
The hashing technique used in Colt sparse matrix solutions has the disadvantage that they add a lot of storage overhead as well as slow access times due to possible collisions. As a result, attempts can avoid all collisions and can then guarantee that linear time O (n) is maintained up to O (1) time in the worst cases, where (n) is the number of possible collisions (which, in the case of a sparse matrix, can be up to the number of cells without default values in the matrix, i.e., up to the total number of matrix sizes multiplied by a coefficient proportional to the hash fill factor for a non-sparse, i.e., full matrix).
Colt’s RC (compressed line) technique is closer to Tries, but at a different price, it uses a compression technique that has very slow access time for the most common read (get () operations, and very slow compression for setAt () operations . In addition, the compression used is not orthogonal, unlike this Tries presentation, where orthogonality is preserved. This orthogonality will also be preserved for related viewing operations, such as walking, transposing (considered as a step operation based on integer cyclic modular operations), subbands (and sub-segments in general, including sorting).
I just hope that Colt will be updated in the future to implement another implementation using Tries (i.e. TrieSparseMatrix instead of HashSparseMatrix and RCSparseMatrix). Ideas in this article.
The Trove implementation (based on int-> int maps) is also based on a hash technique similar to the Colt HashedSparseMatrix method, i.e. they have the same inconvenience. The tests will be much faster, with moderate additional space (but this space can be optimized and become even better than Trove and Colt, for the delayed time, using the final compact () ionic operation on the resulting / trie matrix).
Note: this Trie implementation is bound to a specific field type (here double). This is voluntary, since the overall implementation using box types has huge overhead (and much slower while passing). Here he simply uses his own one-dimensional arrays of double, not common vectors. But, of course, you can get a common implementation for Tries ... Unfortunately, Java still does not allow writing really general classes with all the advantages of native types, except that it writes several implementations (for a general object type or for each native type) and serving all these operations using the factory type. The language should be able to automatically initiate its own implementations and automatically create a factory (for now this is not the case, even in Java 7, and that .Net still retains its advantage for truly generic types that are as fast as native types).