Java嵌套ArrayList复制效率低，求高效实现方案及数据结构建议

在解决N块积木的楼梯搭建组合问题（每列高度至少递减1，例如6块积木的结果为[[5, 1], [4, 2], [3, 2, 1]]）时，我采用递归+memo缓存的方案。从HashMap中获取存储整数的嵌套ArrayList时，由于返回的是引用，修改会改动缓存内的数据，因此需要创建数据副本。目前通过循环为每个内层ArrayList创建新实例来复制，但大数据量下耗时极长，想请教更高效的实现方式或合适的数据结构。

当前复制代码：

ArrayList<ArrayList<Integer>> calcRes = memo.get(n - i);
ArrayList<ArrayList<Integer>> calc = new ArrayList<>();

for (ArrayList<Integer> item : calcRes) {
    calc.add(new ArrayList<>(item));
}

1. 改用不可变集合存储缓存 #

把缓存里的嵌套列表换成不可变实现，比如Guava的ImmutableList或者Java 9+的List.of()。不可变集合本身不允许修改，从缓存取出后可以直接复用外层列表，仅当需要生成新组合时，再复制单个内层列表并修改，无需一次性复制整个嵌套结构。

示例调整：

// 缓存存储不可变列表
ImmutableList<ImmutableList<Integer>> memoValue = ImmutableList.copyOf(...);
memo.put(n, memoValue);

// 使用时仅复制需要修改的内层列表
ImmutableList<ImmutableList<Integer>> calcRes = memo.get(n - i);
ArrayList<ArrayList<Integer>> calc = new ArrayList<>();
for (ImmutableList<Integer> item : calcRes) {
    // 仅当需要修改这个列表时才复制
    ArrayList<Integer> newItem = new ArrayList<>(item);
    newItem.add(xxx); // 执行你的修改操作
    calc.add(newItem);
}

如果不需要修改所有内层列表，还可以跳过不需要修改的项，直接复用不可变实例，进一步减少复制操作。

2. 优化现有复制逻辑 #

• 用ArrayList.clone()替代new ArrayList<>(item)，底层实现更简洁，能小幅提升复制效率；
• 初始化新ArrayList时指定容量（如new ArrayList<>(item.size())），避免自动扩容带来的额外开销；
• 若使用Java 8+，可以用流操作简化代码（性能提升有限，主要优化代码可读性）：

ArrayList<ArrayList<Integer>> calc = calcRes.stream()
    .map(ArrayList::new)
    .collect(Collectors.toCollection(ArrayList::new));

3. 缓存不可修改视图替代全量复制 #

用Collections.unmodifiableList()包装缓存中的内层和外层列表，这样从缓存取出的列表无法被直接修改，既保护了缓存数据，又无需提前复制。仅当需要生成新组合时，再复制单个需要修改的内层列表：

// 缓存存储不可修改视图
List<List<Integer>> unmodifiable = Collections.unmodifiableList(originalList);
memo.put(n, unmodifiable);

// 使用时
List<List<Integer>> calcRes = memo.get(n - i);
ArrayList<ArrayList<Integer>> calc = new ArrayList<>();
for (List<Integer> item : calcRes) {
    // 仅复制需要修改的列表
    ArrayList<Integer> newItem = new ArrayList<>(item);
    newItem.add(xxx);
    calc.add(newItem);
}

4. 换用高性能集合库 #

使用专门优化过的集合库，比如Eclipse Collections的MutableList，它的复制操作比原生ArrayList更快；或者用primitive集合（如IntList）存储整数，避免自动装箱拆箱的开销，大幅提升数据处理和复制的效率。

内容的提问来源于stack exchange，提问作者Noah Dennis