本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
算法(第4版)
知识点
- StdDraw库使用
- 计时器的设计
题目
1.4.3 修改DoublingTest,使用StdDraw产生类似于正文中的标准图像和对数图形,根据需要调整比例使图像总能够充满窗口的大部分区域
1.4.3 Modify DoublingTest to use StdDraw to produce plots like the standard and log-log plots in the text, rescaling as necessary so that the plot always fills a substantial portion of the window.
分析
DoublingTest会用到Stopwatch，这个类是个计时器
public class Stopwatch {
private final long start;
public Stopwatch() {
start = System.currentTimeMillis();
}
public double elapsedTime() {
long now = System.currentTimeMillis();
return (now - start) / 1000.0;
}
}
DoublingTest 是个计算ThreeSum时间的用例
public class DoublingTest {
public static double timeTrial(int N) { // Time ThreeSum2.count() for N random 6-digit ints.
int MAX = 1000000;
int[] a = new int[N];
for (int i = 0; i < N; i++)
a[i] = StdRandom.uniform(-MAX, MAX);
Stopwatch timer = new Stopwatch();
int cnt = ThreeSum.count(a);
return timer.elapsedTime();
}
public static void main(String[] args) { // Print table of running times.
for (int N = 250; true; N += N) { // Print time for problem size N.
double time = timeTrial(N);
StdOut.printf("%7d %5.1f\n", N, time);
}
}
}
书中的标准图像和对数图形如下
关于StdDraw库
又见到StdDraw库了，如果大家还不熟悉，这里提供了相应的链接
算法练习(13):随机连接(1.1.31)
算法练习(14):直方图(1.1.32)
算法练习(18):长方形的一个实现(1.2.3)
观察这两张图，我们一点点分析
1.X轴，Y轴大小的设置
static void setXscale(double x0, double x1) //reset x range to (x0 , x1)
static void setYscale(double y0, double y1) //reset y range to (y0 , y1)
2.在X轴，Y轴上写数字
static void text(double x, double y, String s)
3.设置点的颜色、大小
static void setPenColor(Color c) //set pen color to c
static void setPenRadius(double r) //set pen radius to r
接下来我们利用上面的知识，一点点绘制
1.绘制X轴Y轴
StdDraw.setXscale(-0.1,1.1);
StdDraw.setYscale(-0.1,1.1);
StdDraw.line(0,0,0,1.05);
StdDraw.line(0,0,1.05,0);
得到如下图所示
如图，我们设置X轴Y轴为-1.1到1.1就是为了给坐标的刻度留位置，接下来我们画相应的刻度：
//设置坐标系
StdDraw.setXscale(-0.1,1.1);
StdDraw.setYscale(-0.1,1.1);
StdDraw.line(0,0,0,1.05);
StdDraw.line(0,0,1.05,0);
//画刻度
for (double f = 0 ; f <= 1 ; f += 0.2 ){
DecimalFormat df = new DecimalFormat("0.0");
StdDraw.text(f,-0.06,df.format(f));
StdDraw.text(-0.06,f,df.format(f));
}
得到的图如下所示:
当然，还缺少了刻度的那个小线，我们也加一下
StdDraw.setXscale(-0.1,1.1);
StdDraw.setYscale(-0.1,1.1);
StdDraw.line(0,0,0,1.05);
StdDraw.line(0,0,1.05,0);
for (double f = 0 ; f <= 1 ; f += 0.2 ){
DecimalFormat df = new DecimalFormat("0.0");
StdDraw.text(f,-0.06,df.format(f));
StdDraw.text(-0.06,f,df.format(f));
StdDraw.line(f,-0.02,f,0);
StdDraw.line(-0.02,f,0,f);
}
在原来的DoublingTest中保留的小数位太少了，不能直观的看到时间，我替换了最后一句
StdOut.printf("%7d %5.1f\n", N, time);
为
StdOut.printf("%7d %5.3f\n", N, time);
因此得到的打印结果为
250 0.017
500 0.037
1000 0.218
2000 1.770
4000 9.512
由此可见，在N为4000时，我可以把4000放在我们这个图的1的位置，就是最大值，也就是说X轴放大了1000倍，这样X轴就确定下来了；接下来，确定Y轴，如果把9.512 放在Y轴的位置，那么也就是说Y轴放大了9.15倍，依次类推那么上面的所有对应关系会变成：
X轴 0.0625 Y轴 0.002
X轴 0.125 Y轴 0.003
X轴 0.25 Y轴 0.022
X轴 0.5 Y轴 0.18
X轴 1 Y轴 1
所以我们画出标准图形的代码如下：
StdDraw.setXscale(-0.1,1.1);
StdDraw.setYscale(-0.1,1.1);
StdDraw.line(0,0,0,1.05);
StdDraw.line(0,0,1.05,0);
for (double f = 0 ; f <= 1 ; f += 0.2 ){
DecimalFormat df = new DecimalFormat("0.0");
StdDraw.text(f,-0.06,df.format(f));
StdDraw.text(-0.06,f,df.format(f));
StdDraw.line(f,-0.02,f,0);
StdDraw.line(-0.02,f,0,f);
}
//设置画笔大小
StdDraw.setPenRadius(0.01);
//画点
StdDraw.point(0.0625,0.002);
StdDraw.point(0.125,0.003);
StdDraw.point(0.25,0.022);
StdDraw.point(0.5,0.18);
StdDraw.point(1,1);
基本上已经完成要求了，但这些都是写死的，跟题目的“根据需要调整比例使图像总能够充满窗口的大部分区域”，因此我们稍微改动一下即可。
答案
public class DoublingTest2 {
public static double timeTrial(int N) { // Time ThreeSum2.count() for N
// random 6-digit ints.
int MAX = 1000000;
int[] a = new int[N];
for (int i = 0; i < N; i++)
a[i] = StdRandom.uniform(-MAX, MAX);
Stopwatch timer = new Stopwatch();
int cnt = ThreeSum.count(a);
return timer.elapsedTime();
}
// 绘制标准图形
public static void drawStandard(int[] n, double[] time) {
StdDraw.setXscale(-0.5, 1.2 * n[n.length - 1] / 1000.0);
StdDraw.setYscale(-0.5, time[n.length - 1] * 1.2);
// 建立坐标系
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius(0.001);
StdDraw.line(0, 0, 1.1 * n[n.length - 1] / 1000, 0);
StdDraw.line(0, 0, 0, 1.1 * time[n.length - 1]);
for (int i = 1; i < 1.1 * n[n.length - 1] / 1000.0; i++)
StdDraw.text(i, -0.2, i + "K");
for (double t = 2; t < time[n.length - 1] * 1.1; t += 2)
StdDraw.text(-0.2, t, t + "");
// 绘制图像
StdDraw.setPenColor(StdDraw.BOOK_RED);
StdDraw.setPenRadius(0.02);
for (int i = 0; i < n.length; i++)
StdDraw.point(n[i] / 1000.0, time[i]);
}
//绘制对数图形
public static void drawLog(int[] arrN,double[] timeN)
{
//将时间转换为其对数
double[] timelog=new double[timeN.length];
for(int i=0;i<timeN.length;i++)
timelog[i]=Math.log(timeN[i]);
StdDraw.setXscale(-0.5,1.2*arrN[arrN.length-1]/1000.0);
StdDraw.setYscale(-0.5,timelog[arrN.length-1]*1.2);
//建立坐标系
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.setPenRadius(0.001);
StdDraw.line(0, 0, 1.1*arrN[arrN.length-1]/1000, 0);
StdDraw.line(0, 0,0, 1.1*timelog[arrN.length-1]);
for(int i=1;i<1.1*arrN[arrN.length-1]/1000.0;i++)
StdDraw.text(i,-0.2,i+"K");
for(double t=0;t<timelog[arrN.length-1]*1.1;t+=timelog[arrN.length-1]/5)
StdDraw.text(-0.2, t, String.format("%.2f",t));
//绘制图像
StdDraw.setPenColor(StdDraw.BOOK_RED);
StdDraw.setPenRadius(0.02);
for(int i=0;i<arrN.length;i++)
StdDraw.point(arrN[i]/1000.0, timelog[i]);
}
public static void main(String[] args) {
int MAX = 2000;
int i = 0;
int step = 10;
int len = MAX / step + 1;
int[] arrN = new int[len];
double[] timeN = new double[len];
for (int N = 0; N <= MAX; N = N + step) {
double time = timeTrial(N);
StdOut.printf("%7d %5.7f\n", N, time);
arrN[i] = N;
timeN[i++] = time;
}
drawStandard(arrN, timeN);
drawLog(arrN,timeN);
}
}
代码索引
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
