查看原文
其他

Java 面试题:反转不可变列表

ImportNew ImportNew 2019-10-01

(给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()产生开销很小。实际编程中,如何使用列表值得仔细考虑。如果访问列表非常频繁,则最好使用副本。


最后,有些人过于强调函数式编程和不变性对性能始终带来负面影响。实际上不能一概而论。


以本文讨论的面试题为例,最好的解决方案往往取决于问题本身的约束条件。


推荐阅读

(点击标题可跳转阅读)

最近面试 Java 后端开发的感受

10 个有关 String 的面试问题

Java 线程面试题 Top 50


看完本文有收获?请转发分享给更多人

关注「ImportNew」,提升Java技能

好文章,我在看❤️

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存