java中的内存不足错误

Question

我要离开内存错误：java堆

方法的片段：

{
// 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使用的内存纯粹是增量的。 因此，这并不是说堆的大小在某一点上更小，而是内存被重复使用，并且不会以某种方式释放

如果你需要更多细节，请告诉我

请帮助调试错误

阿努伊

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

整数totalCombination=（整数）数学。pow（2.0，（双）元音计数）

    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

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

您可以尝试调整VM的最大内存需求（例如^{），但要意识到您的算法需要大量内存。如果可能的话，你可能想找到一个更好的算法

---

另见

• Wikipedia: exponential growth
  • Wheat and chessboard problem这是一个著名的轶事，说明了两种力量的增长速度惊人
• ^{} 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，正如预期的那样