算法(Algorithms)第4版 练习 1.5.23
2024-09-03 23:39:06
package com.qiusongde; import edu.princeton.cs.algs4.StdOut; public class Exercise1523 { public static void main(String[] args) { int T = Integer.parseInt(args[0]);
int[] edgesQF = new int[T];
int[] edgesQU = new int[T]; for(int N = 250; true; N += N) { double timeQF = ErdosRenyi.timeTrialForQF(T, N, edgesQF);
double timeQU = ErdosRenyi.timeTrialForQU(T, N, edgesQU); double meanQFConnect = ErdosRenyi.mean(edgesQF);
double meanQUconnect = ErdosRenyi.mean(edgesQU); StdOut.printf("%6d %7.1f %7.1f %7.1f %7.1f\n", N, meanQFConnect, timeQF, meanQUconnect, 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 countByWeiQUPathCom(int N) { int edges = 0;
UFWQuickUnionPathCom uf = new UFWQuickUnionPathCom(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 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 timeTrialForQU(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.countByQU(N);
} return timer.elapsedTime(); } public static double mean(int[] edges) {
return StdStats.mean(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 854.0 0.0 738.0 0.0
500 1554.0 0.0 1832.0 0.0
1000 3291.0 0.0 3616.0 0.0
2000 10467.0 0.0 7477.0 0.0
4000 17488.0 0.0 15609.0 0.0
8000 41016.0 0.0 37187.0 0.1
16000 70888.0 0.2 74066.0 0.8
32000 166090.0 0.9 153517.0 4.1
64000 370711.0 3.5 333206.0 19.4
128000 698381.0 16.3 884453.0 233.5
比较奇怪的是Quick-union的运行时间比Quick-find的还要久。
最新文章
- 备忘:aliyun maven mirror
- jquery实现限制textarea输入字数
- Python学习笔记 for windows
- k8s pv
- java-关于浏览器的判断
- scala中集合的交集、并集、差集
- 数据库留言板例题:session和cookie区别
- linux 内核参数图解
- UI1_UITableViewHomeWork
- 专业的GIS(电子地图、地理信息系统)在房地产行业的初步应用?
- 最近关于ACM训练与算法的总结
- ndk-stack 调试 android c++ 代码崩溃位置
- git merge 冲突
- JDK8 新特性流式数据处理
- 2017.6.5项目总结(移动端touch事件)
- 螺旋矩阵 II
- BZOJ2460 Beijing2011元素(线性基+贪心)
- 方法调用---springMVC中调用controller的方法
- Thinkphp5笔记五:配置data文件夹
- DG日志不应用,GAP,主备切换解决思路与办法