单班 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) ※ 编辑: LoganChien 来自: 140.112.241.166 (04/02 13:11) ※ 编辑: LoganChien 来自: 61.217.185.222 (07/29 00:16)