（四）循环队列 VS 数组队列（效率对比）

￡神魔★判官ぃ 2022-05-14 11:42 166阅读 0赞

*  背景
 *  测试代码
 *  结果
 *  链表
 *  随机访问

--------------------

# 背景 #

各自完成插入 **`10万、20万`**条随机数，然后再将这些随机数出队列 ；

--------------------

# 测试代码 #

/** * 测试速度 */
     public String testSpeed(Queue<Integer> queue, int num) {
            long start = System.currentTimeMillis();
            Random random = new Random(47);
            for (int i = 0; i < num; i++) {
                queue.enQueue(random.nextInt(num));
            }
            for (int i = 0; i < num; i++) {
                queue.deQueue();
            }
    
            long end = System.currentTimeMillis();
            return (end - start) / 1000.0 + " s";
        }
    
        @Test
        public void test() {
    // 十万、二十万的数据
            int num = 200000;
            ArrayQueue<Integer> arrayQueue = new ArrayQueue();
            LoopQueue<Integer> loopQueue = new LoopQueue();
    
            // 十万测试的时间： 16.374 s | 二十万测试的时间： 63.724 s
            System.out.println(testSpeed(arrayQueue, num));
            // 十万测试的时间： 0.085 s 、 | 二十万测试的时间： 0.128 s
            System.out.println(testSpeed(loopQueue, num));
    
        }

--------------------

# 结果 #

从打印的时间看，二者的差距是 **天壤之别**；

**`循环队列`** 在完成 10万、20万 数据 入列、出列的时候，均在 `1 s` 之内 ；

测试 **二百万** 的时间是 `0.8 s`，**二千万** 数据，时间在 `28 s`；

--------------------

**`数组队列`** 在完成 10万、20万 数据 入列、出列的时候，分别使用 `16 s`、`64 s` ；

**二百万**、**二千万**，我没测试；但是，我测试 **一百万** 我等了 **`17`** 分钟，没跑完，然后我结束了运行，二千万的数据 ，估计得按 **`小时`** 算 ；

--------------------

备注：我的 `CPU` 是 `i7-4710mq` ，具体测试，跟 `CPU` 型号有关 ；

--------------------

# 链表 #