java - 在 Java 中递归列表的正确方法是什么？

Question

当在 Java 中递归使用列表时，我经常会多次分配和复制列表。比如我想生成一个List<List<Integer>>所有可能的整数序列，其中:

• 每个数字都在 1 到 9 之间
• 每个数字都大于或等于它前面的数字
• 数字可以连续出现 0 到 3 次。

例如，[1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9]是最大的序列。我有一个递归方法可以做到这一点:

static void recurse(List<List<Integer>> addto, List<Integer> prev, int n){
    if(n>=10)
        addto.add(prev);
    else{
        for(int i=0; i<=3; i++){
            List<Integer> newlist = new ArrayList<Integer>(prev);
            for(int k=0; k<i; k++){
                newlist.add(n);
            }
            recurse(addto, newlist, n+1);
        }
    }
}

这里发生的情况是我正在复制整个 prev每次递归列出 3 次。我需要这样做，以便将内容连接到我的列表并将其传递到下一次迭代。这非常慢(2 秒)。使用 10 个嵌套循环的不太优雅的版本运行速度要快得多，因为它不必复制这么多列表。执行此操作的“正确”方法是什么？

顺便说一句，这不是家庭作业，而是与 USACO 问题之一相关。

Answer 1

速度减慢可能是由于 ArrayList 内部使用的内存被重新分配所致。默认情况下，ArrayList 的起始容量为 10。当您添加第 11 个元素时，它必须扩展该容量，但仅扩展了 50%。此外，当您使用复制构造函数创建 ArrayList 时，新列表最终的容量甚至更小——我认为是源列表中的实际元素数量加上 10%。 (我猜你的 10 循环版本的算法只使用了一个“工作”列表，它在添加到 List > 之前复制了该列表)。

因此，您可以尝试在创建列表时提供容量，看看是否可以加快速度:

List<Integer> newlist = new ArrayList<Integer>(27);  // longest list size is 9 * 3
newlist.addAll(prev);

编辑:顺便说一句，您应该能够实现没有 10 个嵌套循环的非递归算法。使用堆栈，类似于深度优先树搜索。