首页 > 代码库 > 算法(Algorithms)第4版 练习 1.5.22
算法(Algorithms)第4版 练习 1.5.22
package com.qiusongde; import edu.princeton.cs.algs4.StdOut; import edu.princeton.cs.algs4.StdStats; public class Exercise1522 { public static double timeTrialForQF(int T, int N, int[] edges) { Stopwatch timer = new Stopwatch(); // repeat the experiment T times for (int t = 0; t < T; t++) { edges[t] = ErdosRenyi.countByQF(N); } return timer.elapsedTime(); } public static double timeTrialForWeiQU(int T, int N, int[] edges) { Stopwatch timer = new Stopwatch(); // repeat the experiment T times for (int t = 0; t < T; t++) { edges[t] = ErdosRenyi.countByWeiQU(N); } return timer.elapsedTime(); } public static double mean(int[] edges) { return StdStats.mean(edges); } public static void main(String[] args) { int T = Integer.parseInt(args[0]); int edgesQF[] = new int[T]; int edgesQU[] = new int[T]; double prevQF = timeTrialForQF(T, 125, edgesQF); double prevQU = timeTrialForWeiQU(T, 125, edgesQU); for(int N = 250; true; N += N) { double timeQF = timeTrialForQF(T, N, edgesQF); double timeQU = timeTrialForWeiQU(T, N, edgesQU); double meanQFConnect = mean(edgesQF); double meanQUconnect = mean(edgesQU); StdOut.printf("%6d %7.1f %7.1f %7.1f %7.1f\n", N, meanQFConnect, timeQF/prevQF, meanQUconnect, timeQU/prevQU); prevQF = timeQF; prevQU = timeQU; } } }
package com.qiusongde; import edu.princeton.cs.algs4.StdOut; import edu.princeton.cs.algs4.StdRandom; import edu.princeton.cs.algs4.StdStats; import edu.princeton.cs.algs4.UF; import edu.princeton.cs.algs4.WeightedQuickUnionUF; public class ErdosRenyi { public static int countByUF(int N) { int edges = 0; UF uf = new UF(N); while (uf.count() > 1) { int i = StdRandom.uniform(N); int j = StdRandom.uniform(N); uf.union(i, j); edges++; } return edges; } public static int countByQF(int N) { int edges = 0; UFQuickFind uf = new UFQuickFind(N); while (uf.count() > 1) { int i = StdRandom.uniform(N); int j = StdRandom.uniform(N); uf.union(i, j); edges++; } return edges; } public static int countByQU(int N) { int edges = 0; UFQuickUnion uf = new UFQuickUnion(N); while (uf.count() > 1) { int i = StdRandom.uniform(N); int j = StdRandom.uniform(N); uf.union(i, j); edges++; } return edges; } public static int countByWeiQU(int N) { int edges = 0; WeightedQuickUnionUF uf = new WeightedQuickUnionUF(N); while (uf.count() > 1) { int i = StdRandom.uniform(N); int j = StdRandom.uniform(N); uf.union(i, j); edges++; } return edges; } public static void main(String[] args) { int n = Integer.parseInt(args[0]); // number of vertices int trials = Integer.parseInt(args[1]); // number of trials int[] edges = new int[trials]; // repeat the experiment trials times for (int t = 0; t < trials; t++) { edges[t] = countByUF(n); } // report statistics StdOut.println("1/2 n ln n = " + 0.5 * n * Math.log(n)); StdOut.println("mean = " + StdStats.mean(edges)); StdOut.println("stddev = " + StdStats.stddev(edges)); } }
package com.qiusongde; public class Stopwatch { private final long start; public Stopwatch() { start = System.currentTimeMillis(); } public double elapsedTime() { long now = System.currentTimeMillis(); return (now - start) / 1000.0; } }
结果:
250 761.1 2.9 761.4 1.0 500 1698.6 2.8 1717.8 5.2 1000 3739.0 3.8 3737.7 2.0 2000 8184.8 3.7 8174.3 2.1 4000 17773.4 3.9 17799.1 2.2 8000 38312.6 4.1 38229.6 2.2
算法(Algorithms)第4版 练习 1.5.22
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。