这篇我们来看看ArrayDeque的性能分析。
之前我们在《【八】ArrayList与LinkedList的遍历》中提到，ArrayList作为数组，用for + get(i)的遍历性能是LinkedList的两倍。
那么今天我们看看ArrayList与ArrayDeque的遍历性能。
start = System.currentTimeMillis();
ArrayList<Integer> arrayList = new ArrayList(2000000);
for (int i=0; i < 2000000; i++){
arrayList.add(i);
}
end = System.currentTimeMillis();
System.out.println("ArrayList init 2000000 cost time = " + (end-start) + "ms");
start = System.currentTimeMillis();
for (int i=0; i < arrayList.size(); i++) {
arrayList.get(i);
}
end = System.currentTimeMillis();
System.out.println("for get 2000000 cost time = " + (end-start) + "ms");
ArrayList init 2000000 cost time = 75ms
for get 2000000 cost time = 10ms
long start, end;
int size = 2000000;
start = System.currentTimeMillis();
ArrayDeque arrayDeque = new ArrayDeque(size);
for (int i=0; i < size; i++){
arrayDeque.add(i);
}
end = System.currentTimeMillis();
System.out.println("ArrayDeque init 2000000 cost time = " + (end-start) + "ms");
start = System.currentTimeMillis();
for (Object item : arrayDeque) {
//System.out.println(item);
}
end = System.currentTimeMillis();
System.out.println("for 1 cost time = " + (end-start) + "ms");
start = System.currentTimeMillis();
Iterator<Integer> it = arrayDeque.iterator();
while (it.hasNext()) {
it.next();
}
end = System.currentTimeMillis();
System.out.println("Iterator cost time = " + (end-start) + "ms");
start = System.currentTimeMillis();
while (arrayDeque.size() != 0) {
arrayDeque.removeFirst();
}
end = System.currentTimeMillis();
System.out.println("removeFirst cost time = " + (end-start) + "ms");
ArrayDeque init 2000000 cost time = 70ms
for 2000000 cost time = 10ms
Iterator cost time = 10ms
removeFirst cost time = 10ms
看来作为数组，两者性能都是差不多的。
那作为队列呢，ArrayDeque就要跟同样实现了Deque接口的LinkedList对比一番啦。
先来看看FIFO先进先出列队性能对比。
start = System.currentTimeMillis();
LinkedList linkedList = new LinkedList();
for (int i=0; i<2000000; i++) {
linkedList.addFirst(i);
}
end = System.currentTimeMillis();
System.out.println("LinkedList addFirst 2000000 cost time = " + (end-start) + "ms");
LinkedList addFirst 2000000 cost time = 262ms
ArrayDeque arrayDeque = new ArrayDeque();
start = System.currentTimeMillis();
for (int i=0; i < 2000000; i++){
arrayDeque.addFirst(i);
}
end = System.currentTimeMillis();
System.out.println("ArrayDeque addFirst 2000000 cost time = " + (end-start) + "ms");
ArrayDeque addFirst 2000000 cost time = 120ms
即使是不用预先分配空间的构造函数，而是用了ArrayDeque的自动扩容能力，还是比LinkedList快了将近一倍。在入队能力上，LinkedList还是个弟弟啊。
继续看出队能力。
LinkedList的出队：
start = System.currentTimeMillis();
while (linkedList.size() != 0) {
linkedList.removeFirst();
}
end = System.currentTimeMillis();
System.out.println("LinkedList removeFirst cost time = " + (end-start) + "ms");
LinkedList removeFirst cost time = 40ms
start = System.currentTimeMillis();
while (arrayDeque.size() != 0) {
arrayDeque.removeFirst();
}
end = System.currentTimeMillis();
System.out.println("ArrayDeque removeFirst cost time = " + (end-start) + "ms");
ArrayDeque removeFirst cost time = 10ms
ArrayDeque在出队性能上碾压LinkedList呀，都快了3倍了。也难怪，ArrayDeque就是通过Head的偏移地址直接计算到元素的内存地址，读完了就顺手置空而已。而LinkedList虽然有First引用快速找到头部，但是元素删除方面还得一通操作。
那可能有人问，FILO先进后出呢？性能也是一样的。为什么？本质上，双向链表出队都要操作节点，就导致了它比数组慢。因为ArrayDeque的出队不改变任何内存结构。
就好像哥哥写错字就画条斜线，而弟弟写错字还要用涂改液修改一番。
好了，最后我们来总结下今天的结论（在我的机器上）：
- ArrayDeque与ArrayList作为数组，性能都差不多
- ArrayDeque与LinkedList作为队列，入队快1倍，出队快3倍
