Как получается, что когда я вызываю метод 10000 раз, он выдает ошибку памяти?

Question

Ситуация

Мне было поручено реализовать проблему строковой анаграммы в интервью с живым программированием. Задаче было дано две строки, код логики c для метода 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. Что происходит в фоновом режиме, когда я вызываю этот метод х раз?

Answer 1

Давайте проясним это.

• Интервьюер задал вам гипотетический вопрос
• Интервьюер не указал условия правильно (более позднее)
• Интервьюер имеет утверждал, что что-то произойдет произойдет ... без каких-либо доказательств и без возможности проверить это утверждение.

Предположим, у меня есть компьютер со значительно низким объемом памяти .. поэтому он сказал мне, что я получу исключение OutOfMemoryError.

Я думаю, что Интервьюер, вероятно, ошибался.

Прежде всего, ваш код не имеет явных утечек памяти. Не то, что я вижу, и не то, что видят другие комментаторы.

Код вашего решения генерирует несколько временных объектов при каждом вызове. Я могу сосчитать до 6 временных строк и 1 или 2 временных массива, а также потенциально другие временные объекты, созданные некоторыми методами библиотеки. Вы могли бы, вероятно, уменьшить это ... , если бы оно стоило затраченного времени на оптимизацию .

Но временные объекты сами по себе не должны приводить к OOME. Современные Oracle / OpenJDK сборщики мусора действительно хороши для сбора краткосрочных объектов.

За исключением пары патологических сценариев ios:

Сценарий # 1.

Предположим, что вы были уже на пороге исчерпания памяти. Например, предположим, что до того, как вы начали 1000 вызовов методов, у вас было только небольшое количество свободного (eden) пространства после выполнения полного G C.

Для вашей задачи завершено, он сгенерирует порядка 1000 x 10 объектов x 10 000 байт временного пространства. Это около 100 МБ.

• Если у вас есть 10 МБ свободного пространства Эдема, это означает, что вам потребуется примерно 10 сборок пространства Эдема за короткий промежуток времени.

• Если у вас есть 1 МБ свободного пространства в Эдеме, это означает, что вам потребуется примерно 100 коллекций пространства Эдема за короткий промежуток времени.

10 Коллекций пространства Eden вплотную может быть достаточно , чтобы вызвать OOME "Превышен предел накладных расходов". С 100 это гораздо более вероятно.

Но суть в том, что если вы работаете достаточно близко к полной куче, любой фрагмент кода, который выделяет объект, может быть последней каплей. Настоящая проблема в том, что ваша куча слишком мала для задачи ... или что-то еще создает / сохраняет слишком много долгосрочных объектов.

Сценарий # 2 .

Предположим, что ваше приложение имеет строгие требования к задержке. Чтобы реализовать это, вы настраиваете JVM для использования сборщика с низкой паузой и устанавливаете некоторые очень агрессивные цели задержки для сборщика. И у вас также недостаточно памяти.

Теперь, если ваше приложение генерирует слишком много мусора слишком быстро, сборщик с низкой паузой может не справиться. Если вы поставите sh за пределы этого предела, G C вернется к выполнению коллекции «останови мир», чтобы попытаться восстановиться. Вы могли бы получить OOME ... хотя я сомневаюсь в этом. Но вы, безусловно, не достигнете своих целей по задержкам.

Но суть в том, что если у вас есть приложение с такими требованиями, важно, чтобы вы запускали его на машине с достаточными ресурсами; то есть достаточно свободной памяти, достаточно ядер, чтобы (параллельный) G C мог не отставать. Возможно, вы бы спроектировали свой метод isAnagram, чтобы он был (эмм) немного более осторожным в том, как он создает временные объекты ... но вы бы заранее знали, что вам нужно это сделать.

Резюме

Возвращаясь к вопросу, заданному вашим интервьюером (как вам передано):

• Интервьюер не говорит, сколько есть свободного места в куче, поэтому мы не можем сказать, будет ли применяться сценарий № 1. Но если это произойдет, настоящей проблемой будет либо несоответствие между размером кучи и проблемой, либо утечка памяти где-то еще в приложении.

• Интервьюер не упоминает ограничения по времени ожидания. Даже если бы они существовали, первым шагом было бы указать c аппаратное обеспечение и использовать соответствующие (то есть реалистичные c) настройки JVM G C.

• Если вы столкнулись с проблемами (OOMEs, пропущенные цели задержки), , то вы начинаете искать решения. Используйте профилирование памяти, чтобы определить характер проблемы (например, вызвано ли она временными объектами, долговременными объектами, утечкой памяти и т. Д. c) и отследить источник проблем c объекты.

  Не просто предполагайте, что определенный бит кода будет вызывать OOMEs ... как это делает интервьюер. Преждевременная оптимизация - плохая идея.

Answer 2

Заставь это работать. Сделать это правильно. Сделайте это быстро.

Слишком рано думать о производительности или использовании памяти. Ваш метод возвращает ложное срабатывание, поскольку он только проверяет, включены ли все буквы в первом слове во второе слово.

При этой проверке '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()));
}

Answer 3

Мое лучшее предположение:

• У вас есть проблема в сортировке MergeSort, которую вы нам не показали;
• Это происходит не на каждом входе, поэтому интервьюер хочет, чтобы вы запускали его 10000 раз со случайными входами, чтобы это произошло с большой вероятностью;
• Эта проблема может привести к тому, что ваша сортировка слиянием будет повторяться слишком глубоко. Возможно O (N) вместо O (log N) глубины, или, может быть, бесконечная рекурсия; и
• Ваша сортировка слиянием излишне выделяет новый временный массив в каждом рекурсивном вызове. Поскольку их слишком много, это приводит к ошибке нехватки памяти.