package com.tc.javabase.collection;
package com.tc.javabase.collection;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;
/**
* @Classname ArrayDequeCompareLinkedList
* @Description 基于动态数组实现的循环队列 和 双向链表的队列 性能比较
* ArrayDeque compare with LinkedList
* ArrayDeque 和 LinkedList 时间复杂度分析
* ArrayDeque LinkedList
* 入队操作： O(1) O(1)
* 出队操作： O(1) O(1)
* 查看队首元素： O(1) O(1)
*
* 猜测: ArrayDeque 的底层是用动态数组来实现，会出现动态扩容和缩容的情况，虽然均摊到每次操作的
* 时间复杂度仍然是O(1), 但性能比底层使用链表的队列性能低一点点
*
* 结果：
* n ArrayDeque耗时 LinkedList耗时
* 10w 0.0054 0.0067
* 100w 0.0186 0.0271
* 1000w 1.8155 4.3795
*
* ArrayDeque的性能比LinkedList好 随着n的增加 耗时间隔越来越大
* 原因:1.在每次新增元素的时候 链表都要创建一个node节点 分配内存时间大
*
*
*
* @Date 2020/7/21 19:48
* @Created by zhangtianci
*/
public class ArrayDequeCompareLinkedList {
private static Queue<Integer> linkedlistQueue = new LinkedList<Integer>();
private static Queue<Integer> arrayQueue = new ArrayDeque<>();
private static final int count = 1000000; //测试1000w条数据的入队出队
public static void main(String[] args) {
double arrayQueueTime = arrayQueue();
double linkedlistQueueTime = linkedlistQueue();
System.out.println("linkedlistQueue 耗时：" + linkedlistQueueTime);
System.out.println("arrayQueue 耗时：" + arrayQueueTime);
}
public static double linkedlistQueue(){
long startTime = System.nanoTime();
for (int i = 0;i < count;i++){
linkedlistQueue.add(i);
}
for (int i = 0;i < linkedlistQueue.size();i++){
linkedlistQueue.remove();
}
long endTime = System.nanoTime();
return (endTime - startTime) / Math.pow(10,9);
}
public static double arrayQueue(){
long startTime = System.nanoTime();
for (int i = 0;i < count;i++){
arrayQueue.add(i);
}
for (int i = 0;i < arrayQueue.size();i++){
arrayQueue.remove();
}
long endTime = System.nanoTime();
return (endTime - startTime) / Math.pow(10,9);
}
}