Java 面试题：反转不可变列表
（给ImportNew加星标，提高Java技能）
编译：ImportNew/唐尤华
最近的Java面试中，我准备了一个反转不可变列表的问题。结果发现，对于大多数候选人而言，问题并不像想象中那么简单。因此决定在这里分享一下。
问题
实现下面的接口实现反转输入的列表：
public interface Reverser {
List<Integer> reverseList(List<Integer> list);
}期望结果：
输入: 1, 2, 3
输出: 3, 2, 1唯一的要求是输入的list是不可变的。
实现如下：
public List<Integer> reverseList(List<Integer> list) {
final int size = list.size();
List<Integer> reversedList = new ArrayList<>();
for (int i = 0; i < size; i++) {
// 把元素i添加到位置0
reversedList.add(0, list.get(i));
}
return reversedList;
}这个解决方案能达到预期结果。但是从性能角度来看还有问题，你能找出来吗？
能不能用其他方式实现？
通常认为，访问输入列表中指定索引的元素耗费的时间是常数。
作为基准测试，在Intel Core i7-7700（3.6 GHz）上使用Oracle JDK 9，输入100万个元素列表执行的响应时间如下：
problem avgt 403.000 us/op可能的解决方案
迭代模式
首先看一下输入列表迭代的几种方式。众所周知，有许多经典方式可供选择。
从Java 5开始，可以使用for-each循环：
for (int i : list) {
reversedList.add(0, i);
}这么做真的更快吗？在Effective Java中，Joshua Block谈到：
在某些情况下，[for-each循环]与普通的for循环相比可能会具有一些性能上的优势，因为前者只计算一次数组索引的极限。尽管可以手动计算，但程序员并不总是这样做。
换句话说，如果已经预先计算了列表大小（就像在最初的实现中所做的那样），那么与经典版本相比不会有任何差别。
Java 8提供了另一个选项，使用Stream API：
list
.stream()
.forEach(e -> reversedList.add(0, e));同样，这么做没有带来任何明显的性能提升。使用for-each和Stream运行基准测试得到的结果几乎相同：
problem avgt 403.000 us/op
for-each avgt 403.000 us/op
stream avgt 403.000 us/op分配ArrayList
ArrayList数组大小可以调整。背后的实现包含capacity变量，用来存储数组大小。
每种ArrayList实现都有自己的扩容策略，根据JDK的版本不同扩容策略也不同（例如，数组填满时容量递增50％）。
要取消这种动态增长，可以指定初始容量初始化ArrayList。由于我们已经知道输出列表的大小，因此可以做到这一点。
实现如下：
ArrayList<Integer> reversedList = new ArrayList<>(size);运行结果：
problem avgt 403.000 us/op
initial-capacity avgt 403.000 us/op结果并没有发生变化。如何解释呢？
JIT编译器提供的运行时优化让人们相信，设置初始容量并不重要。如果禁用预热时间，就能看到两个测试响应时间之间的差异。
元素移位
让我们仔细看看生成结果ArrayList插入元素方式：
reversedList.add(0, elem);这个简单的表达式时间复杂度是线性的，不是恒定的常量。实际上，在ArrayList位置0插入元素需要把所有元素右移。
这是上面实现中存在的主要问题。那么还有什么其他选择吗？
第一种，使用操作时间为常量的数据结构在位0插入元素。在Java中，可以使用LinkedList来管理指向第一个元素的指针。
调用addFirst()在第一个位置插入元素：
public List<Integer> reverseList(List<Integer> list) {
final int size = list.size();
LinkedList<Integer> reversedList = new LinkedList<>();
for (int i = 0; i < size; i++) {
// Add element i to the first position
reversedList.addFirst(list.get(i));
}
return reversedList;
}效果有没有明显提升？
problem avgt 403.000 us/op
linked-list avgt 541 us/op结果好多了！
第二种方法，保留ArrayList结构，在末尾插入元素（这样操作的时间复杂度是常数）。
必须对列表倒序迭代，如下所示：
public List<Integer> reverseList(List<Integer> list) {
final int size = list.size();
List<Integer> reversedList = new ArrayList<>(size);
for (int i = size - 1; i >= 0; i--) {
// Add element i to the last position
reversedList.add(list.get(i));
}
return reversedList;
}
problem avgt 403.000 us/op
linked-list avgt 541 us/op
insert-last-pos avgt 281 us/op响应时间甚至比LinkedList方案还要短。
实际上，由于LinkedList会动态分配内存（每个元素都包装为一个节点对象），使用时会增加少量内存开销。因此，如果已经知道结构大小，那么使用像ArrayList这样的数据结构显然会更快。
内部数组拷贝
ArrayList的底层实现是数组。如果我们试着复制内部数组并对副本直接进行反转会怎么样？
public List<Integer> reverseList(List<Integer> list) {
final int size = list.size();
final Integer[] array = list.toArray(new Integer[0]); // Copy array
for (int i = 0; i < size / 2; i++) {
swap(array, i, size - i - 1); // Swap elements
}
return Arrays.asList(array);
}swap()函数只交换两个索引对应的数组元素。
这样能不能带来性能提升？
problem avgt 403.000 us/op
linked-list avgt 541 us/op
insert-last-pos avgt 281 us/op
copy-swap-array avgt 254 us/op有趣的是，这种方案甚至比之前的解决方案更快。一些可能的解释：
数组副本由System.arraycopy()管理，这是一个优化过的本地方法。
这种代码对CPU缓存更友好。
视图
最后一种解决方案借助了输入列表的不可变性。因此，可以继承AbstractList创建一个新列表：
public List<Integer> reverseList(List<Integer> list) {
return new AbstractList<Integer>() {
@Override
public Integer get(int index) {
return list.get(list.size() - 1 - index);
}
@Override
public int size() {
return list.size();
}
};
}显然，在这种情况下与基准测试比较reverseList()性能是不合适的，因为输出结果在调用时才生成：
problem avgt 403.000 us/op
linked-list avgt 541 us/op
insert-last-pos avgt 281 us/op
copy-swap-array avgt 254 us/op
view avgt 0,002 us/op需要处理list.size()-1-index时，调用get()产生开销很小。实际编程中，如何使用列表值得仔细考虑。如果访问列表非常频繁，则最好使用副本。
最后，有些人过于强调函数式编程和不变性对性能始终带来负面影响。实际上不能一概而论。
以本文讨论的面试题为例，最好的解决方案往往取决于问题本身的约束条件。
推荐阅读
（点击标题可跳转阅读）
看完本文有收获？请转发分享给更多人
关注「ImportNew」，提升Java技能
好文章，我在看❤️