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

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

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

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

在这种情况下，我认为问题在于您将所有字符串放入数组列表中，因此无法在方法执行结束之前收集它们。值得注意的是，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();
        }
    }
}