动态规划算法：位数组Java

Question

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

在这个矩阵中，我将在特定的ith和jth索引中存储0或1。因此，我的使用仅限于一位，我需要一种方法，使每个矩阵单元只使用1位大小，而不是在一个只需要1位的单元中保留8位的内存溢出

我怎样才能做到这一点

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

Answer 1

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

BitSet的genious 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位的信息。这需要9536 MB才能在堆上分配此阵列，因此空间不足。这个内存量很可能对您的机器来说太多了。然而，在存储位时，仍然需要1192MB。（不考虑由BitSet引起的任何开销。）这仍然是一个很高的数字，所以请确保您的机器提供了足够多的空间，您必须额外分配给JVM实例

Answer 2

在许多情况下，您不需要所有子问题来评估当前问题，因此我建议使用hashmap来存储解决方案，使用递归自上而下的方法来解决DP问题。使用子问题后，可以将其从hashmap中删除，以防止溢出。 有时会有轻微的性能损失，但会防止内存满错误

Memoization

Answer 3

Java提供了一种基于位的托管数据结构，称为^{}。我说这是管理的，因为Java没有用于存储位的本机类型，相反，BitSet将单个位存储为long的一个组件，并保留一个long[]来支持该集。这是一种非常高效的存储方法，但是implementation of ^{}在每64位中保留6位用于“寻址”，仅在原始存储层就相当于10%的开销

这意味着您可以通过保持并仔细地处理自己的{}，以代码的复杂性和风险为代价，在存储上击败{}。除非您的空间非常有限，否则可能不值得为BitSet节省约10%的原始开销

上面描述的两种解决方案都是一维位数组，这可能也不值得一提。通过将一维数组视为行的串联，可以轻松地将二维数组转换为一维数组（至少，在这种情况下，您似乎假定行宽度相等）。对矩阵中特定单元格的寻址很简单：

row * (row_width) + column