Сила двух возрастает в геометрической прогрессии. Если значение vowelCount высокое, один массив может легко вызвать OutOfMemoryError (2^32 = 4GB).
Вы можете попытаться настроить максимальные требования к памяти вашей виртуальной машины (например, -Xmx512m), но понимаете, что ваш алгоритм требует МНОГО ПАМЯТИ . Возможно, вы захотите найти лучший алгоритм, если это вообще возможно.
Смотри также
После редактирования: как я и ожидал, вы генерируете огромный массив, заполненный всеми двоичными возможностями. Вам редко нужно хранить весь этот массив в памяти. Вы можете просто сгенерировать каждую возможную комбинацию «на лету» и передать ее всем, кто нуждается в 0 и 1 «точно в срок».
Имейте в виду, что это все еще экспоненциальный рост, поэтому, несмотря на то, что вы позаботились о потребности в памяти от O(2^N) до O(N), сложность вашего времени по-прежнему O(2^N).
каждый раз, когда вызывается этот метод, создается этот массив. Возможно ли, что массив не освобождается.
Да, это очень возможно, если ссылка на массив когда-либо просочилась, а затем что-то где-то держится за эту ссылку. Сборщику мусора на самом деле все равно, что вы думаете, что это / не мусор; пока объект ссылается на что-то (и это не слабая ссылка и т. д.), это НЕ мусор.
После выяснения того, что вы пытаетесь сделать, вот мое решение. Обратите внимание, что он вообще не генерирует массив битов.
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 , как ожидается .