Java中的稀疏matrix/数组

我正在开发一个用Java编写的项目,这个项目要求我构build一个非常大的二维稀疏数组。 非常稀疏,如果这有所作为。 无论如何:这个应用程序的最关键的方面是时间效率(假设内存负载,尽pipe没有那么大的限制,使我可以使用标准的二维arrays – 关键的范围是在两个数十亿)。

在arrays中的kajillion单元格中,将会有数十万个包含对象的单元格。 我需要能够很快修改单元格内容。

无论如何:有没有人知道这个目的特别好的图书馆? 它必须是伯克利,LGPL或类似的许可证(没有GPL,因为产品不能完全开源)。 或者,如果只有一个非常简单的方法来制作一个自制稀疏数组对象,那也可以。

我正在考虑MTJ ,但没有听到任何意见的质量。

11 Solutions collect form web for “Java中的稀疏matrix/数组”

用hashmaps构build的分布式数组对于频繁读取数据的效率非常低。 最有效的实现是使用一个Trie,允许访问一个单独的vector,在这个vector上分布。

Trie可以通过执行只读的TWO数组索引来获取元素存储的有效位置,或者知道其是否存在于底层存储中,从而计算表中是否存在元素。

它还可以在后备存储中提供缺省值作为稀疏数组的缺省值,这样就不需要对返回的索引进行任何testing,因为Trie保证所有可能的源索引至less映射到缺省值在后台存储中的位置(在这里你会经常存储一个零,或者一个空string或一个空对象)。

在多个操作结束时,存在支持快速可更新尝试的实现,并具有情绪“compact()”操作以优化后备存储的大小。 尝试比hashmaps快得多,因为它们不需要任何复杂的散列函数,并且不需要处理冲突的读取(使用Hashmaps,读取和写入都有冲突,这需要循环跳转到下一个候选人的位置,并对他们每个人的testing,以比较有效的来源指数…)

另外,Java Hashmaps只能对Object进行索引,并且为每个散列源索引创build一个Integer对象(对于每次读取都需要创build这个对象,而不仅仅是写入)在内存操作方面成本很高,因为它强调垃圾收集器。

我真的希望JRE包含一个IntegerTrieMap <Object>作为缓慢的HashMap <Integer,Object>或LongTrieMap <Object>的默认实现,作为更慢的HashMap <Long,Object>的默认实现…但这是仍然不是这样。



你可能想知道什么是Trie?

它只是一小排整数(比matrix的整个坐标范围更小),允许将坐标映射到vector中的整数位置。

例如,假设你想要一个只包含几个非零值的1024 * 1024matrix。 而不是将该matrix存储在包含1024 * 1024元素(超过100万)的数组中,您可能只想将其分割成大小为16 * 16的子范围,而您只需要64 * 64个这样的子范围。

在这种情况下,Trie索引将只包含64 * 64个整数(4096),并且至less有16 * 16个数据元素(包含默认的零,或者稀疏matrix中最常见的子范围)。

而用于存储这些值的向量将只包含一个副本,这些副本对于彼此相等的子范围(大部分都是零填充,它们将由相同的子范围表示)。

所以不要使用像matrix[i][j]这样的语法,而是使用如下语法:

 trie.values[trie.subrangePositions[(i & ~15) + (j >> 4)] + ((i & 15) << 4) + (j & 15)] 

这将更方便地处理使用访问方法的trie对象。

下面是一个示例,内置到一个注释类(我希望它编译好,因为它是简化的;告诉我,如果有错误更正):

 /** * Implement a sparse matrix. Currently limited to a static size * (<code>SIZE_I</code>, <code>SIZE_I</code>). */ 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 <code> * (otherSubrangePosition == subrangePosition)</code>, * 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; } } } 

注意:这个代码是不完整的,因为它处理一个单一的matrix大小,它的压缩器被限制为只检测常见的子范围,不交织它们。

此外,根据matrix大小,代码不能确定将matrix分成子范围(对于x或y坐标)的最佳宽度或高度。 它只是使用16(两个坐标)相同的静态子范围大小,但它可以方便地任何其他2的小功率(但2的非幂会减慢int indexOf(int, int)int offsetOf(int, int)内部方法),独立于两个坐标,直到matrix的最大宽度或高度。compact compact()方法应该能够确定最佳的拟合尺寸。

如果这些拆分子范围的大小可以变化,那么将需要为这些子范围大小而不是静态SUBRANGE_POSITIONS添加实例成员,并使静态方法成为int subrangeOf(int i, int j)int positionOffsetOf(int i, int j)变成非静态; 并且初始化数组DEFAULT_POSITIONSDEFAULT_VALUES将需要被删除或重新定义不同。

如果你想支持交织,基本上你会开始将现有的值分成两个大小相同的大小(都是最小子范围的倍数,第一个子集可能比第二个子集大一个子范围),你会扫描在所有连续位置较大的一个find一个匹配的交错; 那么你会尝试匹配这些值。 然后,你将通过将子集分成两半(也是最小子范围的倍数)recursion地循环,然后再次扫描以匹配这些子集(这将使子集数乘以2:你不得不怀疑是否加倍subrangePositions索引的大小值与现有值的大小相比是值得的,看它是否提供了有效的压缩(如果不是,则停止在那里:直接从交织压缩过程中find了最佳的子范围大小)。大小写在压缩过程中,子范围的大小是可变的。

但是这段代码展示了如何分配非零值并为其他(非零)子范围重新分配data数组,然后如何优化(使用setAt(int i, int j, double value)方法)在数据中存在可能统一的重复子范围时存储此数据,并重新索引到subrangePositions数组中的相同位置。

无论如何,一个特里的所有原则都在那里实现:

  1. 它总是更快(更紧凑的内存,意味着更好的局部性)来表示一个matrix,而不是一个双索引数组(每一个单独分配)。 这个改进在double getAt(int, int)方法中是可见的!

  2. 您可以节省很多空间,但是在分配值时可能需要一些时间来重新分配新的子范围。 出于这个原因,子范围不应该太小,否则重新分配将会频繁发生,无法设置matrix。

  3. 通过检测常见的子范围,可以将初始大matrix自动转换成更紧凑的matrix。 然后一个典型的实现将包含一个如上面的compact()方法。 但是,如果get()访问速度非常快并且set()速度非常快,那么如果要压缩很多常用的子范围,compact()可能会非常缓慢(例如,在减去一个大的非稀疏随机填充matrix时,或者将其乘以零:在这种情况下,通过实例化一个新的和删除旧的那个将会更简单和更快)。

  4. 常见的子范围在数据中使用公共存储,所以这个共享数据必须是只读的。 如果必须更改单个值而不更改matrix的其余部分,则必须首先确保在subrangePositions索引中仅引用一次。 否则,您需要在values向量的任何位置(方便地结束)分配一个新的子范围,然后将此新子范围的位置存储到subrangePositions索引中。



请注意,通用的Colt库虽然非常好,但在处理稀疏matrix时效果并不好,因为它使用散列(或行压缩)工艺,尽pipe它现在还没有实现对尝试的支持优化的优化,既节省空间又节省时间,特别是对于最常见的getAt()操作。

即使在这里描述的setAt()操作也可以节省很多时间(这里的实现方式,即设置后没有自动压缩,这仍然可以根据需求和估计的时间来实现,压缩仍然可以节省大量的存储空间时间价格):节省的时间与子范围内的单元数成正比,并且节省的空间与每个子范围的单元数成反比。 如果使用子区域大小(如每个子区域的单元格数量),那么这是一个很好的折衷scheme,它是2Dmatrix中单元格总数的平方根(当使用3Dmatrix时,它将是立方根)。

在Colt稀疏matrix实现中使用的散列技术具有添加大量存储开销的不便,并且由于可能的冲突而导致访问时间较慢。 尝试可以避免所有的碰撞,然后可以保证在最坏的情况下将线性O(n)时间保存到O(1)时间,其中(n)是可能碰撞的次数(在稀疏matrix的情况下,直到matrix中的非默认值单元的数量,即对于非稀疏即全matrix,直到matrix的总大小乘以与散列填充因子成比例的因子。

Colt中使用的RC(行压缩)技术距离Tries更近,但这是另一个价格,这里使用的是压缩技术,对于最频繁的只读get()操作来说访问时间非常慢,而且非常慢压缩setAt()操作。 另外,所使用的压缩并不是正交的,这与保存正交性的Tries的介绍不同。 尝试还可以保留相关查看操作的正交性,例如跨步,转置(作为基于整数循环模块化操作的跨步操作),分类(以及一般的子select,包括分类视图)。

我只是希望科尔特将在未来更新,以实现另一个实现使用Tries(即TrieSparseMatrix而不是HashSparseMatrix和RCSparseMatrix)。 这个想法在这篇文章中。

Trove实现(基于int-> int地图)也基于类似于Colt的HashedSparseMatrix的散列技术,即它们具有相同的不便。 尝试将会更快,消耗更多的空间(但是这个空间可以被优化,甚至比Trove和Colt更好,在延迟的时间内,使用最终的compact()离子操作)。

注意:这个Trie实现绑定到一个特定的本地types(这里是double)。 这是自愿的,因为使用装箱types的通用实现具有巨大的空间开销(并且在acccess时间中慢得多)。 在这里,它只是使用本地一维双数组而不是genericsVector。 但是对于Tries也可以派生出一个通用的实现……不幸的是,Java仍然不允许编写具有本地types所有好处的真正的generics类,除了编写多个实现(对于通用对象types或每个原生types),并通过types工厂提供所有这些操作。 该语言应该能够自动实例化本地实现并自动构build工厂(现在即使在Java 7中也不是这种情况,这是.Net仍然保持其优势的真正genericstypes,types)。

下面的框架来testingJavamatrix库,也提供了一个很好的列表! https://lessthanoptimal.github.io/Java-Matrix-Benchmark/

经过testing的图书馆:

 * 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) 

以下是您可能感兴趣的论文,其中讨论了matrix计算的数据结构,包括稀疏数组:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.7544

您可以将文件下载为PDF或PS。 它也包括源代码。

也许柯尔特是有帮助的。 它提供了一个稀疏的matrix实现。

这似乎很简单。

您可以使用row * maxcolums +列的数据的二叉树作为索引。

要查找项目,只需计算row * maxcolums +列和二进制search查找它的树,如果不存在,则可以返回null(它是О(log n),其中n是包含对象的单元格的数目)。

不是最快的运行时间解决scheme,但最快我可以拿出似乎工作。 创build一个Index类并将其用作SortedMap的键,如下所示:

  SortedMap<Index, Object> entries = new TreeMap<Index, Object>(); entries.put(new Index(1, 4), "1-4"); entries.put(new Index(5555555555l, 767777777777l), "5555555555l-767777777777l"); System.out.println(entries.size()); System.out.println(entries.get(new Index(1, 4))); System.out.println(entries.get(new Index(5555555555l, 767777777777l))); 

我的索引类看起来像这样(来自Eclipse代码生成器的一些帮助)。

 public static class Index implements Comparable<Index> { private long x; private long y; public Index(long x, long y) { super(); this.x = x; this.y = y; } public int compareTo(Index index) { long ix = index.x; if (ix == x) { long iy = index.y; if (iy == y) { return 0; } else if (iy < y) { return -1; } else { return 1; } } else if (ix < x) { return -1; } else { return 1; } } public int hashCode() { final int PRIME = 31; int result = 1; result = PRIME * result + (int) (x ^ (x >>> 32)); result = PRIME * result + (int) (y ^ (y >>> 32)); return result; } public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; final Index other = (Index) obj; if (x != other.x) return false; if (y != other.y) return false; return true; } public long getX() { return x; } public long getY() { return y; } } 

我刚刚使用了比使用int-> int映射(用于实现稀疏matrix)的Colt更好的性能的Trove 。

你可以看看la4j (Linear Algebra for Java)库。 它支持CRS(压缩行存储)以及稀疏matrix的CCS(压缩列存储)内部表示。 所以,对于稀疏数据,这些是最有效和最快速的内部结构。

下面是在la4j中使用稀疏matrix的简单示例:

 Matrix a = new CRSMatrix(new double[][]{ // 'a' - CRS sparse matrix { 1.0, 0.0, 3.0 }, { 0.0, 5.0, 0.0 }, { 7.0, 0.0. 9.0 } }); Matrix b = a.transpose(); // 'b' - CRS sparse matrix Matrix c = b.multiply(a, Matrices.CCS_FACTORY); // 'c' = 'b' * 'a'; // 'c' - CCS sparse matrix 

你可以使用一个嵌套的地图,虽然如果你需要做matrix微积分,可能不是最好的select

  Map<Integer, Map<integer, Object>> matrix; 

也许而不是对象使用一些元组来实际的数据,所以你可以在提取之后更容易地处理它,例如:

 class Tuple<T extends yourDataObject> { public final int x; public final int y; public final T object; } class Matrix { private final Map<Integer, Map<interger, Tupple>> data = new...; void add(int x, int y, Object object) { data.get(x).put(new Tupple(x,y,object); } } //etc 

为了简洁起见省略了空白检查等

SuanShu有一套Java稀疏matrix和Java稀疏matrix求解器 。

HashMap的岩石。 只需使用StringBuilder(不是+或String.format)将索引(作为string)与分隔符(比如“/”)连接起来,并将其用作键。 你不能更快,更有记忆效率。 稀疏的matrix是20世纪。 🙂

  • Pythonmatrix的逆matrix
  • 如何在R中将vector转换为matrix?
  • 在JavaScript中转换2D数组
  • 在MATLAB中构造邻接matrix
  • 查找matrix中最大值的行和列索引
  • 什么是一个圈出来的意思?
  • 将三列数据框重塑为matrix(“长”到“宽”格式)
  • matrix乘法:matrix大小差异小,时序差异大
  • 如何在Python中定义一个二维数组
  • 在Python中稀疏的3dmatrix/数组?
  • Python中的“@ =”符号是什么?