Избегайте OutOfMemoryError

Question

Недавно я создал метод в Java, чтобы получить перестановку строки, но она бросает это, когда строка слишком длинная: java.lang.OutOfMemoryError: Java heap space Я уверен, что этот метод эффективен поэтому мне нужен совет о том, как распространять вычисления, чтобы избежать ошибки. Я запускаю его, используя консоль в Eclipse.

public static ArrayList<String> permutation(String s) { 
     ArrayList<String> res = new ArrayList<String>(); 
     if (s.length() == 1) { 
      res.add(s); 
     } else if (s.length() > 1) { 
      int lastIndex = s.length() - 1; 
      String last = s.substring(lastIndex); 
      String rest = s.substring(0, lastIndex); 
      res = merge(permutation(rest), last); 
     } 
     return res; 
    } 
    public static int factorial(int n) { 
     int fact = 1; 
     for (int i = 1; i <= n; i++) { 
      fact *= i; 
     } 
     return fact; 
    } 
    public static ArrayList<String> merge(ArrayList<String> list, String c) { 
     ArrayList<String> res = new ArrayList<String>(); 
     for (String s : list) { 
      for (int i = 0; i <= s.length(); ++i) { 
       String ps = new StringBuffer(s).insert(i, c).toString(); 
       res.add(ps); 
      } 
     } 
     return res; 
    } 

здоровается, Робин

Answer 1

Что вы можете сделать возвращает только одну перестановку за вызов, а не целое List. Таким образом, вы можете продолжить вызов этого метода, чтобы получить следующую перестановку по мере необходимости.

class Permutation { 

    private String str; 
    private int first; 
    private int swap; 
    private BigInteger count; 
    private BigInteger numPermutations; 

    public Permutation(String str) { 
     this.str = str; 
     this.first = 0; 
     this.swap = 1; 
     this.count = BigInteger.ZERO; 
     this.numPermutations = factorial(str.length()); 
    } 

    public String next() { 
     if (swap >= str.length()) { 
      swap = 1; 
      first = 0; 
     } 

     char[] array = str.toCharArray(); 
     char tmp = array[first]; 
     array[first] = array[swap]; 
     array[swap] = tmp; 

     swap++; 
     first++; 
     count = count.add(BigInteger.ONE); 

     str = String.valueOf(array); 
     return str; 
    } 

    public boolean hasNext() { 
     return count.compareTo(numPermutations) < 0; 
    } 

    private static BigInteger factorial(int n) { 
     BigInteger fact = BigInteger.ONE; 
     for (int i = 1; i <= n; i++) { 
      fact = fact.multiply(BigInteger.valueOf(i)); 
     } 
     return fact; 
    } 
} 

Вот пример его использования.

Permutation perm = new Permutation("abcde"); 
while (perm.hasNext()) { 
    System.out.println(perm.next()); 
} 

Answer 2

Вы можете увеличить пространство кучи, как представлено здесь:

http://www.oracle.com/technetwork/java/javase/tech/vmoptions-jsp-140102.html

использованием

java -Xms<initial heap size> -Xmx<maximum heap size> 

в командной строке. По умолчанию значения 32 м и 128 м.

Answer 3

Я не специалист по алгоритму или что-то в этом роде, но вот алгоритм, который я придумал с головой. (Вероятно, allready существует в той или иной форме)
Я также не знаю, если он более эффективен.

public static List<String> permutations(String s) { 
    List<String> permutations = new ArrayList<String>(); 
    if (s.length() == 1) { 
     permutations.add(s); 
     return permutations; 
    } 
    for (int i = 0; i < s.length(); i++) { 
     char starChar = s.charAt(i); 
     String rest = new StringBuilder(s).deleteCharAt(i).toString(); 
     for (String string : permutations(rest)) { 
      permutations.add(starChar + string); 
     } 
    } 
    return permutations; 
} 

Он смог перестроить строку длиной 10 до сих пор.
Поскольку я пишу это, мой компьютер по-прежнему пытается перестановить строку длиной 11 для чего-то вроде 10 минут, и до сих пор нет OutOfMemoryError.

Я также заметил, что вы используете код StringBuffer. Методы StringBuffer синхронизированы и, следовательно, медленнее. Вместо этого вы должны использовать StringBuilder. Appart из метода синхронизации классов являются почти идентичными.

Edit:
OutOfMemoryError при попытке permutate строку длины 11.
Так что максимум 10 я думаю (по крайней мере, на моей машине).

Редактировать 2:
Еще одна вещь, которую вы могли бы сделать - это сохранить некоторые успехи в caculation на жестком диске. Но это будет какая-то работа seriouis!

Answer 4

Прежде всего, вам нужно убедиться, что вы понимаете, что вызывает OutOfMemoryError (OOME). Вы делаете пару ссылок на распространение вычислений с течением времени. Я могу неправильно понять, что вы подразумеваете под этим, но, как сказано, это не будет иметь никакого значения в этой ситуации.

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

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

В этом случае, я думаю, проблема заключается в том, что вы помещаете все строки в arraylist, чтобы они не могли быть собраны до окончания выполнения метода. Стоит отметить, что substr фактически создает новую строку, которая ссылается на массив символов исходной строки и, следовательно, не позволит ее собирать. Это может быть проблемой, если вы хотите вытащить небольшой бит текста из большой строки и отказаться от остальных. Я не думаю, что это проблема, но хорошо знать все то же самое.

Самый эффективный способ уменьшить память - создать собственный класс Collection и сгенерировать каждую перестановку при вызове итератора. Это исключило бы необходимость сохранения всех перестановок в памяти одновременно. Если я получу минуту, я отправлю код примера.

Редактировать: Я разработал пример без изменения фундаментальной структуры вашего алгоритма. Он должен работать в обычном JVM для больших входов, чем вы когда-либо захотите подождать до конца. По существу, помещая все результаты в Arraylist, ваше потребление памяти растет факториальной скоростью по отношению к вашей длине строки ввода. Исключая хранение результатов, нижеприведенный подход использует использование памяти, которое растет линейно по отношению к длине входной строки.

Это не идеально, и есть некоторые проблемы, которые я оставляю читателю для решения. Подсказка: что произойдет, если вы создадите Permutor с пустой строкой?

Как кто-то упомянул StringBuffer не самый лучший выбор здесь, но вы, вероятно, даже лучше, используя подстроку и Concat что-то вроде этого:

current.substring(0, position).concat(last).concat(current.substring(position)); 

Пример:

public class Example 
{ 
    public static void main(String... args) { 
     Permutor p = new Permutor("abcdefghijklmnopqrstuvwxyz"); 

     System.out.println(p.size()); 

     int i = 0; 

     for (String s : p) { 
      System.out.println(i++ + ": " + s); 
     } 
    } 


    public static int factorial(int n) { 
     int fact = 1; 
     for (int i = 1; i <= n; i++) { 
      fact *= i; 
     } 
     return fact; 
    } 

    public static class Permutor extends AbstractCollection<String> 
    { 
     private String characters; 

     public Permutor(String s) 
     { 
      characters = s; 
     } 

     @Override 
     public Iterator<String> iterator() 
     { 
      if (characters.length() == 1) { 
       return Collections.singleton(characters).iterator(); 
      } else { 
       return new PermutingIterator(characters); 
      } 
     } 

     @Override 
     public int size() 
     { 
      return factorial(characters.length()); 
     } 
    } 

    private static class PermutingIterator implements Iterator<String> 
    { 
     private final char last; 
     private final Iterator<String> inner; 

     private String current; 
     private int position; 

     PermutingIterator(String s) 
     { 
      int lastIndex = s.length() - 1; 
      this.inner = new Permutor(s.substring(0, lastIndex)).iterator(); 
      this.last = s.charAt(lastIndex); 
     } 

     @Override 
     public boolean hasNext() 
     { 
      return inner.hasNext() || (current != null && position <= current.length()); 
     } 

     @Override 
     public String next() 
     { 
      while(true) { 
       if (current != null && position <= current.length()) { 
        return new StringBuffer(current).insert(position++, last).toString(); 
       } else if (inner.hasNext()) { 
        position = 0; 
        current = inner.next(); 
       } else { 
        throw new IllegalStateException("no more permutations available"); 
       } 
      } 
     } 

     @Override 
     public void remove() 
     { 
      throw new UnsupportedOperationException(); 
     } 
    } 
}