[教學] 單班 00P HW4 提示文

看板b97902HW作者LoganChien (簡子翔)時間16年前 (2009/04/01 21:42)推噓15(15推 0噓 2→)

留言17則, 15人參與討論串1/1

單班 00P HW4 提示文 -------- 單班 00P 的第四個作業的死線在 4/4 號，如果還沒有靈感的人，希望本文可以給你一些幫助。首先，我們要先有一個認知就是：在大部分的情況下，Java 是一個很慢的語言。為什麼慢？第一個凶手就是跨平台，因為所有的程式碼都是編譯成 bytecode 再交由 JVM 去執行的，所以 Java 會很慢。第二個凶手就是額外的工作，Java 比較慢，並不是因為多了幾個沒有用的 for 迴圈，多花的時間其實是用來做一些多餘的工作。例如：Garbage Collecting、 Boundary Check ...。這一篇文的重點就放在 Boundary Check。首先 Boundary Check 是什麼呢？Boundary Check 直接翻成中文就是界限檢查。什麼界限？這一個界限是指陣列索引的界限。一般來說一個大小為 5 的陣列，他的索引大小是 0 ... 4 。原則上我用下標 Subscript 運算子來操作這一個陣列的時候，我們只應使用 0 ... 4 這一些數字。然而 C 語言完全不在乎這一些，我們可以寫出如下的奇怪程式碼： // -- [[ C Source Code Start -------- int a[5] = { 9, 4, 6, 8, 4 }; int *b = a + 2; printf("%d\n", b[-2]); /* Print 9 */ // -- C Source Code End ]] -------- 不過在 Java 中，這樣的行為是不合法的！不只是不能傳入負的索引，索引 i 的值一定要介於區間 [0, arr.length-1] 之間。所以以下的程式碼都是錯的！ // -- [[ Java Source Code Start -------- int [] a = { 9, 4, 6, 8, 4 }; System.out.println(a[-1]); System.out.println(a[5]); System.out.println(a[10000]); // -- Java Source Code End ]] -------- 如果你把上面的程式碼複製並用 javac 編譯，你會發現上面的程式碼可以毫無困難地被編譯！你也許會很訝異？為什麼明明有這麼明顯的錯誤，javac 都不輸出 error？主要的原因在於，陣列的大小在執行期常常會變動，在編譯期檢查索引的值常常防不慎防！所以在 Java Programming Language 之中，所有的 Boundary Check 都是在執行期進行檢查。如果你去用 java XXX 來執行上述程式碼，你一定會很到以下的訊息： Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 這就是一個 Exception (例外)，所謂的例外就是當程式發生非遇期的狀況時，原來的工作就會終止，並拋出一個 Exception。好像是有一個人，在計算一些帳務，發現帳冊有問題，他就索興不幹了，大叫「這本爛帳，老子不算了！看你們有誰要處理這一個問題。」在我們的程式碼中，就是發生了 ArrayIndexOutOfBoundsException，意思清楚明瞭：陣列的索引超出它應屬於的範圍的例外！如果沒有人處理或抓住 (Catch) 這一個例外，整個程式就會終止！就如同你上面看到的錯誤訊息！好了，扯了半天，所以 Boundary Check 會什麼會讓 Java 變慢？這一個問題其實很簡單！請想像一下所有的下標(Subscript)的前面都多了： // -- [[ Pseudocode Start -------- int [] a = { 9, 4, 6, 8, 4 }; System.out.println(a[3]); ==> if (!(0 <= 3 && 3 < a.length)) { throw ArrayIndexOutOfBoundsException; } System.out.println(a\[3\]); // -- Pseudocode End ]] -------- 程式不慢才奇怪呢！你可以下載這一個檔案來看看 Boundary Check 對速度的影響。 http://w.csie.org/~b97073/SubscriptSpeedTest.java 不過話說回來，這一個 Boundary Check 有沒有辦法關掉呢？答案是：不行。Java 程式語言的設計者認為安全比速度更為重要，所以 Boundary Check 是不能關掉的。你唯一加快你的程式的方法就是儘可能減少你的 [] 的數目。怎麼減少 [] 的數目呢？一個重大提示是每一次 for 迴圈 [] 一次就好，盡量不要做很多次 [][] 。這一部分要怎麼做呢？就有待各位的思考！另外你也可能會很好奇，會什麼 JVM 或 javac 不會自動幫我們做 Common Subexpression Elimation 呢？現在的 Compiler / Interupter 不是都很聰明嗎？因為 Java 之中，陣列是 Row-Major Array 以列為主，而不是以欄為主，所以在一些 Common Subexpression 的提取當中，我們不能提出某一欄。 // -- [[ Java Source Code Start -------- int [][] array = new int[5][5]; for (int i = 0; i < 5; ++i) { for (int j = 0; j < 5; ++j) { array[i][j] = Random.nextInt(); } } int [] column = a[][0]; // 錯誤!!! 不能用這樣寫來提取一欄!!! // -- Java Source Code End ]] -------- 好啦，就寫到這了，再寫下去，答案就出來了！ (OS. 怎麼我的教學文都和陣列有關呢?) \ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.241.166 ※ 編輯: LoganChien 來自: 140.112.241.166 (04/01 21:42)

推

iForests

04/01 22:11, , 1^F

04/01 22:11, 1^F

推

sn6783

04/01 22:13, , 2^F

04/01 22:13, 2^F

推

oscarchichun

04/01 22:39, , 3^F

04/01 22:39, 3^F