1.5.23在Erdos-Renyi模型下比较quick-find算法和quick-union算法。开发一个性能测试用例，从命令行接受一个int值T并进行T次以下实验:使用练习1.5.17的用例生成随机连接。保存这些连接并和我们的开发用例一样分别用quikc-find算法和quick-union算法检查触点的连通性，不断循环直到所有触点均相互连通。对于每个N,打印出N值和两种算法的运行时间的比值。

答：

public class E1d5d23

{

     public static class Connection

    {

        int p;

        int q;

        public Connection(int p,int q)

        {this.p=p; this.q=q;}

       

        public int P()

        {return p;}

   

        public int Q()

        {return q;}

    }

        //

    public static int[][]  Generate(int N)

    {

        Queue<Connection> cnns=new Queue();

        WeightedQuickUnionUF uf=new WeightedQuickUnionUF(N);

         while (uf.count()>1)

           {

               int p=StdRandom.uniform(N);

               int q=StdRandom.uniform(N);

               uf.union(p,q);

               cnns.enqueue(new Connection(p,q));

            }//end while

       //

         int[][] cnnsOfArray=new int[cnns.size()][2];

         int i=0;

         while(!cnns.isEmpty())

         {

             Connection item=cnns.dequeue();

             cnnsOfArray[i][0]=item.P();

             cnnsOfArray[i][1]=item.Q();

             i++;

         }

         return cnnsOfArray;

    }

   

   public static double QuickFindElapsedTime(int[][] cnns,int T,int N)

   {

        Stopwatch timer=new Stopwatch();

        for (int t=1;t<=T;t++)

        {

             QuickFindUF uf=new QuickFindUF(N);

             int i=0;

             while(uf.count()>1)

             {

                 uf.union(cnns[i][0],cnns[i][1]);

                 i++;

             }

        }

         return timer.elapsedTime();

   }

     

     

  public static double QuickUnionElapsedTime(int[][] cnns,int T,int N)

   {

        Stopwatch timer=new Stopwatch();

        for (int t=1;t<=T;t++)

        {

             QuickUnionUF uf=new QuickUnionUF(N);

             int i=0;

             while(uf.count()>1)

             {

                 uf.union(cnns[i][0],cnns[i][1]);

                 i++;

             }

        }

         return timer.elapsedTime();

   }

   

      

    public static void main(String[] args)

    {

        int T=Integer.parseInt(args[0]);

        for (int N=2;N<=Math.pow(2,32);N=N+N)

        {

            int[][] cnns=Generate(N);

            double QuickFindTime=QuickFindElapsedTime(cnns,T,N);

            double QuickUnionTime= QuickUnionElapsedTime(cnns,T,N);

           

            StdOut.printf("N=%6d T=%3d  QF=%7.2f QU=%7.2f   QF/QU=%5.2f \n",N,T,QuickFindTime,QuickUnionTime,QuickFindTime/QuickUnionTime);

        }

       

    }

}