本系列博客習(xí)題來自《算法(第四版)》，算是本人的讀書筆記，如果有人在讀這本書的，歡迎大家多多交流。為了方便討論，本人新建了一個微信群(算法交流)，想要加入的，請?zhí)砑游业奈⑿盘枺簔hujinhui207407 謝謝。另外，本人的個人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論
知識點
- StdDraw庫使用
- 計時器的設(shè)計
題目
1.4.3 修改DoublingTest,使用StdDraw產(chǎn)生類似于正文中的標(biāo)準(zhǔn)圖像和對數(shù)圖形,根據(jù)需要調(diào)整比例使圖像總能夠充滿窗口的大部分區(qū)域
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);
}
}
}
書中的標(biāo)準(zhǔn)圖像和對數(shù)圖形如下
關(guān)于StdDraw庫
又見到StdDraw庫了，如果大家還不熟悉，這里提供了相應(yīng)的鏈接
算法練習(xí)(13):隨機連接(1.1.31)
算法練習(xí)(14):直方圖(1.1.32)
算法練習(xí)(18):長方形的一個實現(xiàn)(1.2.3)
觀察這兩張圖，我們一點點分析
1.X軸，Y軸大小的設(shè)置
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軸上寫數(shù)字
static void text(double x, double y, String s)
3.設(shè)置點的顏色、大小
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);
得到如下圖所示
如圖，我們設(shè)置X軸Y軸為-1.1到1.1就是為了給坐標(biāo)的刻度留位置，接下來我們畫相應(yīng)的刻度：
//設(shè)置坐標(biāo)系
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));
}
得到的圖如下所示:
當(dāng)然，還缺少了刻度的那個小線，我們也加一下
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中保留的小數(shù)位太少了，不能直觀的看到時間，我替換了最后一句
StdOut.printf("%7d %5.1f\n", N, time);
為
StdOut.printf("%7d %5.3f\n", N, time);
因此得到的打印結(jié)果為
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倍，依次類推那么上面的所有對應(yīng)關(guān)系會變成：
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
所以我們畫出標(biāo)準(zhǔn)圖形的代碼如下：
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);
}
//設(shè)置畫筆大小
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);
基本上已經(jīng)完成要求了，但這些都是寫死的，跟題目的“根據(jù)需要調(diào)整比例使圖像總能夠充滿窗口的大部分區(qū)域”，因此我們稍微改動一下即可。
答案
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();
}
// 繪制標(biāo)準(zhǔn)圖形
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);
// 建立坐標(biāo)系
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]);
}
//繪制對數(shù)圖形
public static void drawLog(int[] arrN,double[] timeN)
{
//將時間轉(zhuǎn)換為其對數(shù)
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);
//建立坐標(biāo)系
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);
}
}
代碼索引
廣告
我的首款個人開發(fā)的APP壁紙寶貝上線了，歡迎大家下載。
