当我调用一个方法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异常。我知道（或我最不认为），由于算法的效率，我会得到这样的异常。所以我的问题是：

1. 为什么会引发OutOfMemoryError异常？
2. 如果我调用该方法1000次，是因为完成一次调用会花费很长时间引发此类异常吗？
3. 当我调用该方法x次时，后台发生了什么？

Answer 1

请对此明确。

• 访调员问了你一个[[假设问题
采访者未正确指定条件（稍后）
• 采访者断言某事[[will
... ...没有证据，也没有办法验证该断言。

假设我有一台内存明显不足的计算机...所以他告诉我，我会收到OutOfMemoryError异常。

我认为采访者可能是错误的。

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

您的解决方案代码在每次调用时都会生成一些临时对象。我最多可以计算6个临时字符串和1或2个临时数组，以及可能由某些库方法创建的其他临时对象。您可能可以减少它...

如果值得在优化上花费更多的开发时间

。

但是临时对象本身不应导致OOME。现代的Oracle / OpenJDK垃圾收集器非常擅长收集短期对象。

在几种病理情况下除外：

方案1。

假设您

已经

即将耗尽内存。例如，假设在开始1000个方法调用之前，您只有少量的空闲（eden）空间

运行完整的GC后>。为了完成任务，它将生成大约1000倍x 10个对象x 10,000字节的临时空间。大约是100MB。

如果您有10MB的Eden空间可用，这意味着您将需要在短时间内进行大约10个Eden空间收集。

• 如果您有1MB的Eden空间可用，这意味着您将需要在短时间内进行大约100个Eden空间收集。

10个Eden空间收集背对背

可能足够导致OOME“超出开销限制”。如果设置为100，则可能性更大。

但是最重要的是，如果您运行的足够接近满堆，分配对象的any

代码段可能是最后的稻草。真正的问题是您的堆对于任务来说太小了……或者

something正在创建/保留太多的longterm对象。方案2。

假设您的应用程序有严格的延迟要求。为了实现此目的，您将JVM配置为使用低暂停时间的收集器，并为收集器设置了一些非常积极的延迟目标。而且您也没有很多内存。

现在，如果您的应用程序生成太多垃圾的速度太快，低暂停时间的收集器可能无法跟上。如果将其超过限制，GC将退回到进行世界停止收集以尝试恢复。您

可能

收到一个OOME…尽管我对此表示怀疑。但是您肯定会无法达到延迟目标。

但是如果您的应用程序具有这样的要求，最重要的是，必须在具有足够资源的计算机上运行它；也就是说，有足够的备用内存，有足够的内核可以供（并行）GC使用。您可能会在创建临时对象的方式上将isAnagram方法设计为（erm）更多[[careful

...，但您会预先知道需要这样做。回顾

返回面试官提出的问题（由您转达）：

采访者没有说有多少可用堆空间，所以我们不能说方案＃1是否适用。但是，如果这样做，真正的问题可能是堆大小和问题之间的不匹配，或者是应用程序中的内存泄漏

somewhere other

。

采访者没有提及延迟限制。即使它们存在，第一步也将是指定硬件并使用适当的（即实际的）JVM GC设置。

如果您确实遇到了问题（OOME，错过了延迟目标），

然后

您开始寻找解决方案。使用内存配置文件来识别问题的

nature

（例如，它是由临时对象，长期对象，内存泄漏等引起的），还是跟踪有问题的对象的来源。

不只是假设代码的特定部分将

导致OOMEs ...，就像采访者所做的那样。过早的优化不是一个好主意。

Answer 2

您的MergeSort中有问题，您没有显示给我们；

并非每次输入都会发生，因此访调员希望您使用随机输入将其运行10000次，以使其有很高的可能性发生]

该问题可能会导致您的合并排序太深地递归。也许是O（N）而不是O（log N）深度，或者是无限递归；和
• 您的合并排序不必要在每个递归调用中分配一个新的临时数组。由于它们太多了，因此会导致内存不足错误。

Answer 3

通过此检查，'aaa'和'abc'被认为是字谜，但不是'abc'和'aaa'。

这是测试您的代码的完整课程：

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()));
}