java - 动态规划 : Bits Array Java

Question

我需要解决一个动态编程 问题，为此我需要在内存中创建一个N*N 大小的矩阵。如果我确实创建了一个大小为 N = 100000; 的 byte[][] 矩阵，那么它会抛出 java.lang.OutOfMemoryError: Java heap space 错误。

在这个矩阵中，我将在特定的 ith<​​ 和 jth 索引处存储 0 或 1。所以我的使用仅限于一点，我需要一种方法，这样我就可以只使用每个矩阵单元的 1 位大小，而不是过度淹没内存，在一个只需要 1 位的单元中保留 8 位。

我怎样才能做到这一点？

请注意，我关心的不是增加 JVM 堆，我只是在寻找一种方法来最佳地实现动态问题的解决方案。

Answer 1

更新:我刚刚检查了一下，不幸的是，忘记了 BitSet。

BitSet 的巧妙 API 建立在 int 索引之上。 N * N 的整数范围超出了您的范围。因此，您需要自己实现一些东西。一个建议:

public class BetterBitSet {

  private final long[] values;

  public BetterBitSet(int dimension) {
    values = new long[(int) ((long) dimension) * dimension / 8 / 64 + 1];
  }

  public void set(int i, int j, boolean value) {
    long index = index(i, j);
    int arrayIndex = arrayIndex(index);
    if (value) {
        values[arrayIndex] = set(values[arrayIndex], offset(index));
    } else {
        values[arrayIndex] = unset(values[arrayIndex], offset(index));
    }
  }

  public boolean isSet(int i, int j) {
    long index = index(i, j);
    return isSet(values[arrayIndex(index)], offset(index));
  }

  private boolean isSet(long value, int bitIndex) {
    return (value & (1L << bitIndex)) != 0;
  }

  private long set(long value, int bitIndex) {
    return value | (1L << bitIndex);
  }

  private long unset(long value, int bitIndex) {
    return value & ~(1L << bitIndex);
  }

  private long index(int i, int j) {
    return j * 8L + i;
  }

  private int arrayIndex(long index) {
    return (int) index / 64;
  }

  private int offset(long index) {
    return (int) index % 64;
  }
}

如有疑问，请查看 BitSet 的源代码并尝试类似的操作。

旧答案:问题是 byte[][] 的每个索引都需要 8 位，而您只存储大约 1 位的信息。这已经需要 9,536 MB 用于在堆上分配此数组，因此空间不足。这个内存量对于您的机器来说很可能太多了。然而，对于存储位，您仍然需要 1,192 MB。 (不考虑 BitSet 造成的任何开销。)这仍然是一个很高的数字，因此请确保您的机器提供足够的空间，您必须额外分配给您的 JVM 实例。