Algs4-1.5.22Erods-renyi模型的倍率实验

1.5.22Erods-renyi模型的倍率实验。开发一个性能测试用例 ，从命令行接受一个int值T并进行T次以下实验：使用练习1.5.17的用例生成随机连接，和我们的开发用例一样使用UnionFind来检查触点的连通性，不断循环直到所有触点均相互连通。对于每个N，0打印出N值和平均所需的连接数以及前后两次运行时间的比值。使用你的程序验证正文中的猜想：quick-find算法和quick-union算法的运行时间是平方级别的，加权quick-union算法则接近线性级别。
答：

public class E1d5d22
{
    public static int countOfQuickFind(int N)
    {
        int Times=0;
        QuickFindUF uf=new QuickFindUF(N);
         while (uf.count()>1)
           {
               int p=StdRandom.uniform(N);
               int q=StdRandom.uniform(N);
               Times++;
               uf.union(p,q);
            }//end while
        return Times;
    }
   
     public static int countOfQuickUnion(int N)
    {
        int Times=0;
        QuickUnionUF uf=new QuickUnionUF(N);
        while (uf.count()>1)
           {
               int p=StdRandom.uniform(N);
               int q=StdRandom.uniform(N);
               Times++;
               uf.union(p,q);
            }//end while
        return Times;
    }
    
   public static int countOfWeightedQuickUnion(int N)
    {
        int Times=0;
        WeightedQuickUnionUF uf=new WeightedQuickUnionUF(N);
        while (uf.count()>1)
           {
               int p=StdRandom.uniform(N);
               int q=StdRandom.uniform(N);
               Times++;
               uf.union(p,q);
            }//end while
        return Times;
    }
         

   public static void DoubleTestQuickFind(int T)
   {
        int totalConnections=0;
        double lastElapsedTime=0;
        double currentElapsedTime=0;
        StdOut.println("---QuickFind---");
        for(int N=2;N<=Math.pow(2,15);N=N+N)
            {
               Stopwatch timer=new Stopwatch();
               totalConnections=0;
               for (int t=1;t<=T;t++)
                 {
                   totalConnections=totalConnections+countOfQuickFind(N);
                 }
              currentElapsedTime=timer.elapsedTime();
              StdOut.printf("N=%6d  avg Connection=%8d  time=%8.2f   Rate=%5.2f ",N,totalConnections/T,currentElapsedTime,currentElapsedTime/lastElapsedTime);
              lastElapsedTime=currentElapsedTime;
            }
   }
  
  
   public static void DoubleTestQuickUnion(int T)
   {
        int totalConnections=0;
        double lastElapsedTime=0;
        double currentElapsedTime=0;
        StdOut.println("---QuickUnion---");
        for(int N=2;N<=Math.pow(2,15);N=N+N)
            {
               Stopwatch timer=new Stopwatch();
               totalConnections=0;
               for (int t=1;t<=T;t++)
                 {
                   totalConnections=totalConnections+countOfQuickUnion(N);
                 }
              currentElapsedTime=timer.elapsedTime();
              StdOut.printf("N=%6d  avg Connection=%8d  time=%8.2f   Rate=%5.2f ",N,totalConnections/T,currentElapsedTime,currentElapsedTime/lastElapsedTime);
              lastElapsedTime=currentElapsedTime;
            }
   }
  
   public static void DoubleTestWeightedQuickUnion(int T)
   {
        int totalConnections=0;
        double lastElapsedTime=0;
        double currentElapsedTime=0;
        StdOut.println("---WeightedQuickUnion---");
        for(int N=2;N<=Math.pow(2,15);N=N+N)
            {
               Stopwatch timer=new Stopwatch();
               totalConnections=0;
               for (int t=1;t<=T;t++)
                 {
                   totalConnections=totalConnections+countOfWeightedQuickUnion(N);
                 }
              currentElapsedTime=timer.elapsedTime();
              StdOut.printf("N=%6d  avg Connection=%8d  time=%8.2f   Rate=%5.2f ",N,totalConnections/T,currentElapsedTime,currentElapsedTime/lastElapsedTime);
              lastElapsedTime=currentElapsedTime;
            }
   }
  
    public static void main(String[] args)
    {
        int T=Integer.parseInt(args[0]);
       DoubleTestQuickFind(T);
       DoubleTestQuickUnion(T);
       DoubleTestWeightedQuickUnion(T);
    }
}