当我调用一个方法 10000 次时它会抛出内存不足错误是怎么回事？

Question

情况

我的任务是在现场编码面试中实施字符串字谜问题。给定两个字符串的问题，为方法 boolean isAnagram(String str1, String str2).

编写逻辑代码

解决方案

我提出了以下解决方案（mergeSort是我自己的实现，containsChar使用的是二分查找也是我自己的实现）

public static boolean isAnagram(String value, String valueToCompare) {
    String temp = valueToCompare.replaceAll("'", "").replaceAll(" ", "").toLowerCase();
    String t = value.replaceAll("'", "").replaceAll(" ", "").toLowerCase();
    if (t.length() == temp.length()) {
        char[] c = t.toCharArray();
        char[] orderedChars = MergeSort.mergeSort(temp.toCharArray());
        for (int i = 0; i < orderedChars.length ; i++) {
                if (!containsChar(orderedChars, c[i], 0, orderedChars.length - 1))
                    return false;
        }
        return true;
    }
    return false;
}

解决方案的效率是多余的，我更关心后台发生的事情。

问题

在我提出解决方案后，面试官问我，假设我有一台内存非常低的计算机，我想运行这个算法 10.000 次，随机字符串大小在 1000 到 10000 之间，你的代码会发生什么？我不知道该回答什么，所以他告诉我，我会得到一个 OutOfMemoryError 异常。我知道（或者我至少认为）由于算法的效率，我会得到这样的异常。所以我的问题是：

为什么抛出 OutOfMemoryError 异常？
如果我调用该方法1000次，是否因为完成一次调用需要很长时间才能抛出这种异常？
当我调用该方法 x 次时，后台发生了什么？

Answer 1

说清楚这一点。

面试官问了你一个假设性问题
面试官没有正确说明条件（稍后会详细介绍）
面试官断言将发生......没有证据，也无法验证该断言。

Lets suppose I have a computer with significantly low memory ... so he told me that I would get a OutOfMemoryError exception.

我认为面试官可能是错的。

首先，你的代码没有明显的内存泄漏。我看不到，其他评论者也看不到。

您的解决方案代码确实会在每次调用时生成一些临时的 object。我最多可以数出 6 个临时字符串和 1 或 2 个临时数组，以及可能由某些库方法创建的其他临时 objects。您可能会减少... 如果开发人员在优化上花费的时间值得的话。

但临时 object 本身不应导致 OOME。现代 Oracle / OpenJDK 垃圾收集器非常擅长收集短期 objects.

除了一些病理情况：

场景 #1。

假设您已经即将运行内存不足。例如，假设在开始 1000 次方法调用之前，在运行完整 GC 之后，您只有少量空闲 (eden) space 。

为了你的任务完成，它会生成大约1000次x 10objects x 10,000字节的临时space。那大约是 100MB。

如果你有 10MB 的 Eden space 空闲，这意味着你将需要在短时间内完成大约 10 个 Eden space collections .

如果您有 1MB 的 Eden space 空闲，这意味着您将需要在短时间内完成大约 100 个 Eden space collections .

10 Eden space collection 背靠背 可能足以 导致 OOME "Overhead limit exceeded"。如果是 100，则可能性更大。

但最重要的是，如果您运行足够接近满堆，任何分配 object 的代码片段都可以成为最后一根稻草。真正的问题是你的堆对于任务来说太小了......或者其他东西正在创建/保留太多长期 objects.

场景 #2。

假设您的应用程序具有严格的延迟要求。要实现这一点，您需要将 JVM 配置为使用 low-pause 收集器，并为收集器设置一些非常积极的延迟目标。而且你的内存也不大。

现在，如果您的应用程序生成过多垃圾的速度过快，low-pause 收集器可能无法跟上。如果您将其推到限制之外，GC 将退回到执行 stop-the-world collection 以尝试恢复。你可能得到一个 OOME ...虽然我对此表示怀疑。但是您肯定无法达到您的延迟目标。

但最重要的是，如果您的应用程序有这样的要求，那么您必须运行在具有足够资源的机器上使用它；即足够的备用内存，足够的内核（并行）GC 可以跟上。您可能会将 isAnagram 方法设计为 (erm) 在创建临时 objects 的方式上更小心 ... 但您会知道的前面说你需要这样做。

回顾

回到面试官提出的问题（由您转述）：

面试官没有说有多少空闲堆 space，所以我们不能说场景 #1 是否适用。但如果确实如此，真正的问题要么是堆大小与问题之间的不匹配，要么是应用程序中 其他地方 的内存泄漏。

面试官没有提到延迟限制。即使它们存在，第一步也是指定硬件并使用适当的（即现实的）JVM GC 设置。

如果您运行遇到问题（OOME，错过延迟目标），然后您开始寻找解决方案。使用内存分析来识别问题的性质（例如，它是由临时objects、长期objects、内存泄漏等引起的）和追踪有问题的 object 的来源。

不要仅仅假设特定的代码会导致 OOME ......正如面试官所做的那样。过早的优化是个坏主意。

Answer 2

我的最佳猜测：

您的 MergeSort 有问题，但您没有向我们展示；
并不是每次输入都会发生，所以面试官希望你运行随机输入 10000 次，以使其发生的概率更高；
该问题可能导致您的合并排序递归太深。也许 O(N) 而不是 O(log N) 深度，或者无限递归；和
您的合并排序在每次递归调用中都不必要地分配了一个新的临时数组。由于它们太多了，这会导致内存不足错误。

Answer 3

让它发挥作用。改正它。快点。

现在考虑性能或内存使用还为时过早。您的方法 returns 误报，因为它只检查第一个单词中的每个字母是否都包含在第二个单词中。

通过此检查，'aaa' 和 'abc' 被认为是变位词，但 'abc' 和 'aaa' 不是。

这里有一个完整的 class 来测试您的代码：

import java.util.Arrays;


public class AnagramTest
{
    public static void main(String[] args) {
        String[][] anagrams = {
                { "abc", "cba" },
                { "ABC", "CAB" },
                { "Clint Eastwood", "Old West action" }
        };

        for (String[] words : anagrams) {
            if (isAnagram(words[0], words[1])) {
                System.out.println(".");
            } else {
                System.out.println(
                        "OH NO! '" + words[0] + "' and '" + words[1] + "' are anagrams but isAnagram returned false.");
            }
        }

        String[][] notAnagrams = {
                { "hello", "world" },
                { "aabb", "aab" },
                { "abc", "aaa" },
                { "aaa", "abc" },
                { "aab", "bba" },
                { "aab", "bba" },
        };

        for (String[] words : notAnagrams) {
            if (isAnagram(words[0], words[1])) {
                System.out.println(
                        "OH NO! '" + words[0] + "' and '" + words[1] + "' are not anagrams but isAnagram returned true.");
            } else {
                System.out.println(".");
            }
        }
    }

    public static boolean isAnagram(String value, String valueToCompare) {
        String temp = valueToCompare.replaceAll("'", "").replaceAll(" ", "").toLowerCase();
        String t = value.replaceAll("'", "").replaceAll(" ", "").toLowerCase();
        if (t.length() == temp.length()) {
            char[] c = t.toCharArray();
            char[] orderedChars = mergeSort(temp.toCharArray());
            for (int i = 0; i < orderedChars.length; i++) {
                if (!containsChar(orderedChars, c[i], 0, orderedChars.length - 1))
                    return false;
            }
            return true;
        }
        return false;
    }

    // Dummy method. Warning: sorts chars in place.
    private static char[] mergeSort(char[] chars) {
        Arrays.sort(chars);
        return chars;
    }

    // replace with your binary search if you want.
    private static boolean containsChar(char[] orderedChars, char c, int m, int n) {
        for (int i = m; i <= n; i++) {
            if (orderedChars[i] == c) {
                return true;
            }
        }
        return false;
    }
}

它输出：

.
.
.
.
.
.
OH NO! 'aaa' and 'abc' are not anagrams but isAnagram returned true.
OH NO! 'aab' and 'bba' are not anagrams but isAnagram returned true.
OH NO! 'aab' and 'bba' are not anagrams but isAnagram returned true.

这是一个应该通过所有测试的示例实现：

public static boolean isAnagram(String word1, String word2) {
    word1 = word1.replaceAll("'", "").replaceAll(" ", "").toLowerCase();
    word2 = word2.replaceAll("'", "").replaceAll(" ", "").toLowerCase();
    return Arrays.equals(mergeSort(word1.toCharArray()), mergeSort(word2.toCharArray()));
}

当我调用一个方法 10000 次时它会抛出内存不足错误是怎么回事？

How is it that when I call a method 10000 times it throws out of memory error?

java

algorithm

memory-management

out-of-memory

java-memory-model

情况

解决方案

问题

场景 #1。

场景 #2。

回顾

让它发挥作用。改正它。快点。