java - 避免内存不足错误

Question

我最近在Java中创建了一个方法来获取字符串的排列，但是当字符串太长时它会抛出此错误:java.lang.OutOfMemoryError:Java堆空间 我确信该方法是有效的，因此我需要有关如何分散计算以避免错误的建议。 我使用 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 中运行，以获得比您想要等待完成的更大的输入。本质上，通过将所有结果放入数组列表中，您的内存消耗会随着输入字符串长度的阶乘比率而增加。通过消除结果的存储，以下方法的内存使用量相对于输入字符串长度呈线性增长。

这并不完美，有些问题我留给读者去解决。提示:如果您使用空字符串创建 Permutor 会发生什么？

正如有人提到的，StringBuffer 不是最好的选择，但使用 substring 和 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();
        }
    }
}