Java中的稀疏矩阵/数组

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (31)

我正在开发一个用Java编写的项目,这需要我构建一个非常大的2D稀疏数组。非常稀疏,如果这有所作为。无论如何:这个应用程序的最关键的方面是时间效率(假设内存的负载,尽管没有那么大的限制,以至于我不能使用标准的2-D阵列 - 关键范围在两个方面的数十亿)。

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

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

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

提问于
用户回答回答于

用hashmaps构建的分布式数组对于频繁读取数据的效率非常低。最有效的实现使用Trie,允许访问分段分布的单个向量。

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

它还可以在后备存储中为稀疏数组的默认值提供默认位置,这样您就不需要对返回的索引进行任何测试,因为Trie确保所有可能的源索引至少映射到缺省值在后台存储中的位置(您将经常存储一个零,或者一个空字符串或一个空对象)。

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

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

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

你可能想知道什么是Trie?

它只是一小排整数(范围小于矩阵的整个坐标范围),允许将坐标映射到向量中的整数位置。

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

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

并且用于存储值的向量将仅包含彼此相等的子范围的1个副本(其中大多数都是满零,它们将由相同的子范围表示)。

因此,不要使用类似的语法matrix[i][j],而应使用如下语法:

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

这将更方便地使用针对特定对象的访问方法进行处理。

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

/**
 * 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;
        }
    }

}

注意:此代码并不完整,因为它处理单个矩阵大小,并且它的压缩器仅限于检测常见的子范围,而不会交织它们。

此外,根据矩阵大小,代码不会确定将矩阵分成子范围(对于x或y坐标)的最佳宽度或高度。它只是使用16的相同的静态子范围的大小(两个坐标),但它可以很方便地任意2等小功率(但2非动力将减缓int indexOf(int, int)int offsetOf(int, int)内部方法),independantly两个坐标,最多到矩阵的最大宽度或高度。最后该compact()方法应该能够确定最佳的拟合尺寸。

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

如果你想支持交织,基本上你会首先将现有值分成两个大小相同的尺寸(两个尺寸都是最小子尺寸的倍数,第一个子尺寸可能比第二个子尺寸多一个子尺寸),以及你会扫描所有连续位置上较大的一个来找到匹配的交错; 那么你会尝试匹配这些值。然后,通过将子集分成两半(也是最小子范围大小的倍数)递归循环,然后再次扫描以匹配这些子集(这会将子集数乘以2:您必须怀疑是否加倍subrangePositions索引的大小与值的现有大小相比是值得的值,以查看它是否提供了有效的压缩(如果没有,则停在那里:您已经从交错压缩过程直接找到了最佳的子范围大小)。在这种情况下; 在压缩过程中,子区域大小将是可变的。

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

无论如何,在这里实现了一个模式的所有原则:

  1. 它总是更快(并且内存更紧凑,意味着更好的局部性),以使用单个向量而不是双索引数组阵列(每个阵列单独分配)来表示矩阵。double getAt(int, int)方法中可以看到改进!
  2. 您可以节省大量空间,但在分配值时可能需要一些时间来重新分配新的子范围。出于这个原因,子范围不应该太小,否则重新分配将过于频繁地设置您的矩阵。
  3. 通过检测常见的子范围,可以将初始大矩阵自动转换为更紧凑的矩阵。一个典型的实现将包含一个compact()如上所述的方法。但是,如果get()访问速度非常快并且set()速度非常快,那么如果有许多常用的子范围要压缩,compact()可能会非常缓慢(例如,在减去一个大型非稀疏随机填充矩阵时,或者将它乘以零:在这种情况下,通过实例化一个新的和删除旧的那个来重置该特里将更简单和更快)。
  4. 常用子范围在数据中使用公共存储,因此该共享数据必须是只读的。如果您必须更改单个值而不更改矩阵的其余部分,则必须首先确保它在subrangePositions索引中仅被引用一次。否则,您需要在values矢量的任何位置(方便地结束)分配新的子区域,然后将此新子区域的位置存储到subrangePositions索引中。

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

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

在Colt稀疏矩阵实现中使用的散列技术会带来不便,因为它们会增加大量存储开销,并且由于可能的冲突而导致访问时间延长。尝试可以避免所有冲突,然后可以保证在最坏的情况下将O(n)时间保存为O(1)时间,其中(n)是可能碰撞的次数(如果是稀疏矩阵,则可能是直到矩阵中非默认值单元的数量,即对于非稀疏即完整矩阵,直到矩阵大小的总数乘以与散列填充因子成比例的因子。

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

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

Trove实现(基于int-> int映射)也基于类似于Colt的HashedSparseMatrix的散列技术,即它们具有相同的不便之处。尝试将会快得多,并且会消耗一定量的额外空间(但是这个空间可以在延迟的时间内进行优化并且比Trove和Colt更好,对最终的矩阵/ trie使用最终的compact()离子操作)。

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

用户回答回答于

在测试Java Matrix Libraries的框架之后,还提供了一个很好的列表! https://lessthanoptimal.github.io/Java-Matrix-Benchmark/

经过测试的Libraries:

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

扫码关注云+社区