2.4.38

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

直接构造相应的数组测试即可。
测试结果如下:

最大堆来说顺序时会比较慢,因为每次插入都要一路上升到顶部。
逆序的时候则是删除比较慢,最后一个元素是最小的元素,交换后需要一路下沉到底部。
由于元素相同的时候我们选择不交换(less(i, j) 返回 false),较多的重复元素并不会影响性能。

代码

using System;
using System.Linq;
using System.Diagnostics;
using PriorityQueue;

namespace _2._4._38
{
    /*
     * 2.4.38
     * 
     * 练习测试。
     * 编写一个练习用例,
     * 用算法 2.6 中实现的优先队列的接口方法处理实际应用中可能出现的高难度或是极端情况。
     * 例如,元素已经有序、元素全部逆序、元素全部相同或是所有元素只有两个值。
     * 
     */
    class Program
    {
        static Random random = new Random();

        static void Main(string[] args)
        {
            int n = 200000;
            int repeatTimes = 5;
            int doubleTimes = 4;
            for (int i = 0; i < doubleTimes; i++)
            {
                Console.WriteLine("n=" + n);
                // 升序数组
                long totalTime = 0;
                Console.Write("Ascending:\t");
                for (int j = 0; j < repeatTimes; j++)
                {
                    MaxPQ<int> pq = new MaxPQ<int>(n);
                    int[] data = GetAscending(n);
                    long time = Test(pq, data);
                    Console.Write(time + "\t");
                    totalTime += time;
                }
                Console.WriteLine("Average:" + totalTime / repeatTimes);
                // 降序数组
                totalTime = 0;
                Console.Write("Descending:\t");
                for (int j = 0; j < repeatTimes; j++)
                {
                    MaxPQ<int> pq = new MaxPQ<int>(n);
                    int[] data = GetDescending(n);
                    long time = Test(pq, data);
                    Console.Write(time + "\t");
                    totalTime += time;
                }
                Console.WriteLine("Average:" + totalTime / repeatTimes);
                // 全部元素相同
                totalTime = 0;
                Console.Write("All Same:\t");
                for (int j = 0; j < repeatTimes; j++)
                {
                    MaxPQ<int> pq = new MaxPQ<int>(n);
                    int[] data = GetSame(n, 17763);
                    long time = Test(pq, data);
                    Console.Write(time + "\t");
                    totalTime += time;
                }
                Console.WriteLine("Average:" + totalTime / repeatTimes);
                // 只有两个值
                totalTime = 0;
                Console.Write("Binary Dist.:\t");
                for (int j = 0; j < repeatTimes; j++)
                {
                    MaxPQ<int> pq = new MaxPQ<int>(n);
                    int[] data = GetBinary(n, 15254, 17763);
                    long time = Test(pq, data);
                    Console.Write(time + "\t");
                    totalTime += time;
                }
                Console.WriteLine("Average:" + totalTime / repeatTimes);
                n *= 2;
            }
        }

        static long Test(MaxPQ<int> pq, int[] data)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < data.Length; i++)
            {
                pq.Insert(data[i]);
            }
            for (int i = 0; i < data.Length; i++)
            {
                pq.DelMax();
            }
            sw.Stop();
            return sw.ElapsedMilliseconds;
        }

        static int[] GetAscending(int n)
        {
            int[] ascending = new int[n];
            for (int i = 0; i < n; i++)
                ascending[i] = random.Next();
            Array.Sort(ascending);
            return ascending;
        }

        static int[] GetDescending(int n)
        {
            int[] descending = GetAscending(n);
            descending = descending.Reverse().ToArray();
            return descending;
        }

        static int[] GetSame(int n, int v)
        {
            int[] same = new int[n];
            for (int i = 0; i < n; i++)
            {
                same[i] = v;
            }
            return same;
        }

        static int[] GetBinary(int n, int a, int b)
        {
            int[] binary = new int[n];
            for (int i = 0; i < n; i++)
            {
                binary[i] = random.NextDouble() > 0.5 ? a : b;
            }
            return binary;
        }
    }
}

另请参阅

PriorityQueue 库

上一题 下一题