400-616-5551

您所在位置: 首页> 学习课程> java培训学校 | Java 面试题:反转不可变列表

java培训学校 | Java 面试题:反转不可变列表

发布百知教育 来源:学习课程 2019-10-10

最近的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培训学校:http://www.baizhiedu.com/java2019


上一篇:java培训学校 | java开发人员需要掌握的常见linux命令

下一篇:应届生去公司找个Java程序员的职位需要什么技能?

相关推荐

www.baizhiedu.com

有位老师想和您聊一聊

关闭

立即申请