算法練習(xí)(56): 計時器的設(shè)計(1.4.3)

本系列博客習(xí)題來自《算法(第四版)》,算是本人的讀書筆記惜犀,如果有人在讀這本書的铛碑,歡迎大家多多交流狠裹。為了方便討論虽界,本人新建了一個微信群(算法交流),想要加入的涛菠,請?zhí)砑游业奈⑿盘枺簔hujinhui207407 謝謝莉御。另外,本人的個人博客 http://www.kyson.cn 也在不停的更新中俗冻,歡迎一起討論

算法(第4版)

知識點

  • StdDraw庫使用
  • 計時器的設(shè)計

題目

1.4.3 修改DoublingTest,使用StdDraw產(chǎ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);
        }
    }
}

書中的標準圖像和對數(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就是為了給坐標的刻度留位置新症,接下來我們畫相應(yīng)的刻度:

//設(shè)置坐標系
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中保留的小數(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

所以我們畫出標準圖形的代碼如下:

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();
    }

    // 繪制標準圖形
    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]);
    }
    
    //繪制對數(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);
        //建立坐標系
        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);
    }
}

代碼索引

DoublingTest2.java

廣告

我的首款個人開發(fā)的APP壁紙寶貝上線了,歡迎大家下載。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末帽芽,一起剝皮案震驚了整個濱河市删掀,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌导街,老刑警劉巖披泪,帶你破解...
    沈念sama閱讀 211,639評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異搬瑰,居然都是意外死亡款票,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,277評論 3 385
  • 文/潘曉璐 我一進店門泽论,熙熙樓的掌柜王于貴愁眉苦臉地迎上來艾少,“玉大人,你說我怎么就攤上這事翼悴「抗唬” “怎么了?”我有些...
    開封第一講書人閱讀 157,221評論 0 348
  • 文/不壞的土叔 我叫張陵鹦赎,是天一觀的道長谍椅。 經(jīng)常有香客問我,道長钙姊,這世上最難降的妖魔是什么毯辅? 我笑而不...
    開封第一講書人閱讀 56,474評論 1 283
  • 正文 為了忘掉前任,我火速辦了婚禮煞额,結(jié)果婚禮上思恐,老公的妹妹穿的比我還像新娘。我一直安慰自己膊毁,他們只是感情好胀莹,可當我...
    茶點故事閱讀 65,570評論 6 386
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著婚温,像睡著了一般描焰。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上栅螟,一...
    開封第一講書人閱讀 49,816評論 1 290
  • 那天荆秦,我揣著相機與錄音,去河邊找鬼力图。 笑死步绸,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的吃媒。 我是一名探鬼主播瓤介,決...
    沈念sama閱讀 38,957評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼吕喘,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了刑桑?” 一聲冷哼從身側(cè)響起氯质,我...
    開封第一講書人閱讀 37,718評論 0 266
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎祠斧,沒想到半個月后闻察,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,176評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡梁肿,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,511評論 2 327
  • 正文 我和宋清朗相戀三年蜓陌,在試婚紗的時候發(fā)現(xiàn)自己被綠了觅彰。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片吩蔑。...
    茶點故事閱讀 38,646評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖填抬,靈堂內(nèi)的尸體忽然破棺而出烛芬,到底是詐尸還是另有隱情,我是刑警寧澤飒责,帶...
    沈念sama閱讀 34,322評論 4 330
  • 正文 年R本政府宣布赘娄,位于F島的核電站,受9級特大地震影響宏蛉,放射性物質(zhì)發(fā)生泄漏遣臼。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 39,934評論 3 313
  • 文/蒙蒙 一拾并、第九天 我趴在偏房一處隱蔽的房頂上張望揍堰。 院中可真熱鬧,春花似錦嗅义、人聲如沸屏歹。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,755評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽蝙眶。三九已至,卻和暖如春褪那,著一層夾襖步出監(jiān)牢的瞬間幽纷,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,987評論 1 266
  • 我被黑心中介騙來泰國打工博敬, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留友浸,地道東北人。 一個月前我還...
    沈念sama閱讀 46,358評論 2 360
  • 正文 我出身青樓冶忱,卻偏偏與公主長得像尾菇,于是被迫代替她去往敵國和親境析。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 43,514評論 2 348