为什么迭代置换生成器比递归慢？

Question

我正在比较两个用作置换生成器的函数。这个问题是关于很多事情的:字符串intern表，使用迭代和递归解决这个问题的优缺点，等等。

public static List<String> permute1(String input) {
    LinkedList<StringBuilder> permutations = new LinkedList<StringBuilder>();
    permutations.add(new StringBuilder(""+input.charAt(0)));

    for(int i = 1; i < input.length(); i++) {
        char c = input.charAt(i);
        int size = permutations.size();
        for(int k = 0; k < size ; k++) {
            StringBuilder permutation = permutations.removeFirst(),
                    next;
            for(int j = 0; j < permutation.length(); j++) {
                    next = new StringBuilder();
                    for(int b = 0; b < permutation.length(); next.append(permutation.charAt(b++)));
                    next.insert(j, c);
                    permutations.addLast(next);
            }
            permutation.append(c);
            permutations.addLast(permutation);
        }
    }
    List<String> formattedPermutations = new LinkedList<String>();
    for(int i = 0; i < permutations.size(); formattedPermutations.add(permutations.get(i++).toString()));
    return formattedPermutations;
}

public static List<String> permute2(String str) { 
    return permute2("", str); 
}

private static List<String> permute2(String prefix, String str) {
    int n = str.length();
    List<String> permutations = new LinkedList<String>();
    if (n == 0) permutations.add(prefix);
    else 
        for (int i = 0; i < n; i++) 
            permutations.addAll(permute2(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)));
    return permutations;
}

我认为这两个算法大体上应该是相等的，但是递归实现在n=10上做得很好，而迭代解决方案permute1在n=8上有一个内存错误，其中n是输入字符串长度。我使用StringBuilder然后转换成字符串的事实是不是一个坏主意？如果有，原因何在？我认为无论何时你添加到一个字符串中，它都会创建一个新的字符串，这是不好的，因为java会对它进行实例化，对吧？所以你最终会得到一堆中间字符串，它们不是排列，而是卡在实习生的表中。

编辑：

我用String替换了StringBuilder，这样就不需要使用StringBuilder.insert()了。但是，我必须使用String.substring()来构建置换字符串，这可能不是最好的方法，但从经验上讲它比StringBuilder.insert()更好。我没有像Alex Suo建议的那样使用字符数组，因为我的方法应该返回一个字符串列表，所以我必须将这些字符数组转换为字符串，这将导致在字符数组上进行更多的垃圾回收(这就是OutOfMemoryError的原因)。因此，有了这些，OutOfMemoryError和速度问题都得到了解决。

public static List<String> permute3(String input) {
        LinkedList<String> permutations = new LinkedList<String>();
        permutations.add(""+input.charAt(0));
        for(int i = 1; i < input.length(); i++) {
            char c = input.charAt(i);
            int size = permutations.size();
            for(int k = 0; k < size ; k++) {
                String permutation = permutations.removeFirst(),
                        next;
                for(int j = 0; j < permutation.length(); j++) {
                        next = permutation.substring(0, j + 1) + c + permutation.substring(j + 1, permutation.length());
                        permutations.addLast(next);
                }
                permutations.addLast(permutation + c);
            }
        }
        return permutations;
    }

Answer 1

首先，自从你得到了OutOfMemoryError，这暗示着你有很多GC正在进行，正如我们所知道的，GC是一个性能杀手。因为年轻一代的GC是停止世界的，你可能会因为遭受GC的痛苦而获得更糟糕的性能。

查看您的代码，如果您深入研究StringBuilder的实际实现，您会发现insert()是一个非常昂贵的操作，涉及到System.arraycopy()等，还可能涉及到expandCapacity()。因为你没有提到n表示排列，所以我假设你的缓冲区是n<10，所以这里不会有问题--因为StringBuilder的默认缓冲区大小只有16，所以你需要重新分配内存。StringBuilder基本上是一个自动字符数组，但它并不神奇--无论您需要通过从头开始编写代码来做什么，StringBuilder也需要这样做。

话虽如此，如果你真的想获得最大的性能，既然你的字符串数组的长度是预先定义的，为什么不使用长度= String.length()的字符数组呢？就性能而言，这可能是最好的。