java - java中的内存不足错误

Question

我收到 OutOfMemoryError: java heap

方法的片段:

{
// step 1: I am creating a 2 dim array
  int totalCombination = (int) Math.pow(2.0, (double) vowelCount);
// here vowelCount > 10

// step2: initializing my array
// step3: and using that array
}

我的问题:

每次调用此方法时，都会创建该数组。 有没有可能阵列没有被释放。

在 Windows taskmanager 中，我可以看到 java 使用的内存是纯粹增量的。 因此，并不是堆大小在某一点上变小了，而是内存被重复使用而没有以某种方式释放。

如果您需要更多详细信息，请告诉我。

请帮忙调试错误

阿努杰

可能导致错误的代码部分:

int totalCombination = (int) Math.pow(2.0, (double) vowelCount);

    int lookupArray[][] = new int[totalCombination][vowelCount];

    // initialize lookupArray

    for (int i = 0; i < totalCombination; i++) {
        for (int j = 0; j < vowelCount; j++) {
            lookupArray[i][j] = 0;
        }
    }

    // populate lookupArray
    //vowelCount : number of vowels in a word
    // if count is 2, then array will contain 00,01,10,11

    for (int i = 1; i < totalCombination; i++) {
        for (int c = 0; c < vowelCount; c++) {
            lookupArray[i][c] = lookupArray[i - 1][c];
        }
        boolean flag = true;
        for (int j = vowelCount - 1; j >= 0 && flag; j--) {
            if (lookupArray[i - 1][j] == 1) {
                lookupArray[i][j] = 0;
            } else if (lookupArray[i - 1][j] == 0) {
                lookupArray[i][j] = 1;
                flag = false;
            }
        }
    }


  // this part total combination of a word having different combination of vowels in it.


    for (int i = 0; i < totalCombination; i++) {
        int vcount = vowelCount - 1;
        StringBuffer stringBuffer = new StringBuffer();

        for (int j = 0; j < word.length(); j++) {
            if (wordArr[j] == 'a' || wordArr[j] == 'e' || wordArr[j] == 'i'
                    || wordArr[j] == 'o' || wordArr[j] == 'u') {
                if (lookupArray[i][vcount] == 1) {
                    stringBuffer.append(wordArr[j]);
                }
                vcount--;
            } else {
                stringBuffer.append(wordArr[j]);
            }
        }

Answer 1

2 的幂呈指数增长。如果 vowelCount 很高，单独一个数组很容易导致 OutOfMemoryError (2^32 = 4GB)。

您可以尝试调整您的 VM 最大内存要求(例如 -Xmx512m)，但要意识到您的算法需要大量内存。如果可能的话，您可能希望找到更好的算法。

---

另见

• Wikipedia: exponential growth
  • Wheat and chessboard problem -- 一个著名的轶事，展示了两人的力量如何惊人地迅速增长
• java application launcher command line options
  • "-Xmxn : 指定内存分配池的最大大小。"

---

编辑后:正如我所料，您正在生成一个充满所有二进制可能性的巨大数组。您很少需要将整个数组实际存储在内存中。您可以“即时”生成每个可能的组合，并将其“即时”提供给需要 0 和 1 的任何人。

请记住，这仍然是指数级增长，因此即使您已经处理了从 O(2^N) 到 O(N)< 的内存需求，你的时间复杂度仍然是O(2^N)。

each time this method is called, that array is getting created. Is it possible that the array is not getting released .

是的，这是很有可能的，如果对数组的引用曾被泄露，然后某个地方的某些东西保留了这个引用。垃圾收集器并不真正关心您认为什么是/不是垃圾；只要某个对象被某物引用(并且它不是弱引用等)，它就不是垃圾。

---

在弄清楚您要做什么之后，这是我的解决方案。请注意，它根本不会生成位数组。

static void generate(String prefix, String suffix) {
    int i = suffix.replaceAll("[aeiou].*", "").length();
    if (i == suffix.length()) {
        System.out.println(prefix + suffix);
    } else {
        generate(prefix + suffix.substring(0, i), suffix.substring(i + 1));
        generate(prefix + suffix.substring(0, i+1), suffix.substring(i + 1));
    }
}

// generate("", "apple");

它使用正则表达式查找下一个元音的位置。您可以改用常规的 for 循环，通用算法仍然有效。您可以优化它以使用 StringBuilder 代替(我主要是为了简明扼要，希望这段代码清晰)。

---

这里有一个替代解决方案，它使用 split 将输入字符串预切成片段(O(N) 空间)，然后使用 StringBuilder 生成所有其他字符串(O(N) 空间)。

static void generate(StringBuilder sb, String[] parts, int i) {
    if (i == parts.length) {
        System.out.println(sb.toString());
    } else {
        if ("aeiou".contains(parts[i])) {
            generate(sb, parts, i + 1);
        }
        sb.append(parts[i]);
        generate(sb, parts, i + 1);
        sb.setLength(sb.length() - parts[i].length());
    }
}
static void generate(String s) {
    generate(
        new StringBuilder(),
        s.split("(?<=[aeiou])|(?=(?!^)[aeiou])"),
        0
    );
}

// generate("apple");

正则表达式将 "apple" 拆分为 [ "a", "ppl", "e"]。它在元音后到处分开，或者(如果它不是字符串的开头)在元音前到处分开。

现在应该很明显，空间要求是 O(N)，所以除非您的字符串长得离谱，否则这不应该导致 OutOfMemoryError.

当然，如果您存储生成的字符串——它们的所有O(2^N)——在内存中，那么当然 你会得到 OutOfMemoryError。我希望这个事实是显而易见的。

整个想法 是不在内存中存储您不需要生成此巨大输出的任何内容。如果您随后将所有这些巨大的输出存储在内存中(而不是将它们打印到 stdout 或文件)，那么它会破坏整个目的，您将得到一个 OutOfMemoryError 符合预期。