避免 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

您可以增加堆 space，如下所示：

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

使用

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

在命令行上。默认情况下，值为 32m 和 128m。

Answer 2

我不是算法专家之类的，但这是我想出的算法。（可能已经以某种形式存在）
我也不知道这样效率高不高

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。 Apppart from the method synchronization 类几乎相同。

编辑：
尝试排列长度为 11 的字符串时出现 OutOfMemoryError。
所以我猜最大值是 10（至少在我的机器上是这样）。

编辑 2：
您可以做的另一件事是将一些计算进度保存在硬盘上。但这将是一些严肃的工作！

Answer 3

首先，您需要确保了解导致 OutOfMemoryError (OOME) 的原因。您多次参考了随着时间的推移展开计算。我可能误解了你的意思，但如前所述，在这种情况下这不会有任何不同。

OOME 是 1 的结果。JVM 没有足够大的 space 空闲连续块来存储新对象 after 释放所有垃圾并压缩堆。在这种情况下，时间并不是真正的因素。如果内存是可达的，不管它存在多久都无法收集。

所以有几个原因可能会导致您在这里遇到问题。一个是您正在尝试创建一个非常大的对象（字符串允许您这样做）并且没有足够大的空闲堆块来容纳它。另一个原因是您用无法收集的对象填满了堆，因为您仍在引用它们。

在这种情况下，我认为问题在于您将所有字符串放入数组列表中，因此无法在方法执行结束之前收集它们。值得注意的是，substr 实际上创建了一个新字符串，该字符串引用了原始字符串的字符数组，因此不允许收集它。如果您想从一个大字符串中提取一小部分文本并丢弃其余部分，这可能会成为一个问题。我认为这不是问题，但还是很高兴知道。

减少内存的最有效方法是创建自己的集合 class 并在调用迭代器时生成每个排列。这将消除同时将所有排列存储在内存中的需要。如果我有时间，我会 post 一些示例代码。

编辑：我在不改变算法基本结构的情况下编写了一个示例。它应该运行在一个普通的 JVM 中用于比你想要等待完成的更大的输入。本质上，通过将所有结果放入 Arraylist，您的内存消耗会根据输入字符串长度以阶乘速率增长。通过消除结果的存储，以下方法的内存使用量相对于输入字符串长度呈线性增长。

这并不完美，有些问题我将留给 reader 解决。提示：如果您创建一个带有空字符串的 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();
        }
    }
}

Answer 4

您可以做的是 return 每次调用只有一个排列，而不是整个 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());
}

避免 OutOfMemoryError

Avoiding an OutOfMemoryError

java

out-of-memory

permutation