笔者下面引用的程序是Robert大叔著名的程序片断来重新认识一下重构,那些java代码看起来正确,但事实上不是看起来那么简单的,一小段程序调试起来总会有些小错误。我一度怀疑是作者或译者故意去写错一些代码,然后引起阅读者的注意的。从程序的调试编写以及重构过程中,备注了作为一名一线程序员的一些总结。
“重构”,顾名思义,对程序来说就是“在不改变代码外在行为的前提下对代码做出修改,以改进代码内部结构的过程”。
下面是一个素数产生程序,首先要知道什么是素数吧?记得上学时书上说素数就是质数,是除了能被1和本身整除外,没有其他因子能整除。又google了下,其定义如下:
1.只有1和它本身这两个因数的自然数叫做素数。还可以说成素数只有1和它本身两个约数。
2.素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。
例如,15=3×5,所以15不是素数.
从编程角度我们要考虑其算法,算法是什么?算法采用Sieve of Eratosthenes筛选法,这个算法的详细情况是这样的:
由于一个合数(相对于素数的定义,即0和1之外,除了素数就是合数)总是可以分解成若干个素数的乘积,那么如果把素数(最初只知道2为素数)的倍数都去掉,那么剩下的就是素数了。
例如要查找100以内的素数,首先2是质数,把2的倍数去掉;此时3没有被去掉,可认为是素数,所以把3的倍数去掉;再到5,再到7,之后呢因为8,9,10刚都被去掉了,而100以内的任意合数肯定都有一个因子小于10(100的开方)。因此去掉2,3,5,7的倍数后剩下的都是素数了。
下面程序的主要逻辑片断是:
- //最主要逻辑在于此,Math.sqrt(s)取得该数位于中间的因子.
- //比如maxValue=10,那么Math.sqrt(s)=3
- for(i=2; i< Math.sqrt(s)+1;i++){
- //下面算法举例子,比如maxValue=10时
- //循环1:i=2
- //循环2:i=3
- //循环3:i=4
- for(j=2*i;j<s;j+=i){
- //循环11:j=4;j<11;j=4+2
- //循环12:j=6;j<11;j=6+2
- //循环13:j=8;j<11;j=8+2
- //循环14:j=10;j<11;j=10+2
- //这样就过滤掉4,6,9,10
- //循环21:j=6;j<11;j=6+3
- //循环22:j=9;j<11;j=9+3
- //这样就过滤掉9
- //循环31:j=8;j<11;j=8+4
- f[j] = false;
- }
- }
素数产生程序:一个简单的重构示例
version1:GeneratePrimesV1.java
下面的为实现需求“产生给定整数范围内所有的素数”写的第一个版本Verson1,这个版本的程序把实现需求的3个小功能全部糅合在了一个类文件中,耦合性太强。具体代码如下:
- package Prime;
- public class GeneratePrimesV1 {
- /**
- * The algorithm is quite simple. Given an array of integers
- * starting at 2.Cross out all multiples of 2.Find the next
- * uncrossed integer,and cross out all of its multiples.Repeat
- * until you have passed the squre root of the maximum value.
- *@author ZHANGRONG
- *@version 1.0
- *@param int maxValue
- *@return int[]
- *质数又称素数。
- *指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。
- *换句话说,只有两个正因数(1和自己)的自然数即为素数。
- *比1大但不是素数的数称为合数。
- *1和0既非素数也非合数.
- */
- public static int[] generatePrimes(int maxValue){
- if(maxValue >= 2){
- int s = maxValue + 1;
- boolean[] f = new boolean[s];
- int i;
- for(i=0;i<s;i++){
- f[i] = true;
- }
- f[0] = f[1] = false;
- int j;
- //最主要逻辑在于此,Math.sqrt(s)取得该数位于中间的因子.
- //比如maxValue=10,那么Math.sqrt(s)=3
- for(i=2; i< Math.sqrt(s)+1;i++){
- //下面算法举例子,比如maxValue=10时
- //循环1:i=2
- //循环2:i=3
- //循环3:i=4
- for(j=2*i;j<s;j+=i){
- //循环11:j=4;j<11;j=4+2
- //循环12:j=6;j<11;j=6+2
- //循环13:j=8;j<11;j=8+2
- //循环14:j=10;j<11;j=10+2
- //这样就过滤掉4,6,9,10
- //循环21:j=6;j<11;j=6+3
- //循环22:j=9;j<11;j=9+3
- //这样就过滤掉9
- //循环31:j=8;j<11;j=8+4
- f[j] = false;
- }
- }
- int count =0;
- for(i=0;i<s;i++){
- if(f[i]){
- count++;
- }
- }
- int[] primes = new int[count];
- for(i=0,j=0;i<s;i++){
- if(f[i]){
- primes[j++] = i;
- }
- }
- return primes;
- }else{
- return new int[0];
- }
- }
- public static void main(String args[]){
- int maxValue = 10;
- System.out.println(generatePrimes(maxValue));
- }
- }
version2:GeneratorPrimeV2.java
上述程序为实现功能,可以分成3个步骤,这3个步骤是:
1.第一对所有的变量进行初始化,并做好过滤所需要的准备工作;
2.第二执行真正的过滤工作;
3.第三把过滤后的结果存放到一个整型数组中。
在将上述3个步骤写成3个小功能时,把一些函数级的局部变量提升为类级的静态域。
实现程序如下:
- package Prime;
- public class GeneratorPrimeV2 {
- private static boolean[] f;
- private static int[] primes;
- public static int[] generatePrimes(int maxValue){
- if(maxValue < 2){
- return new int[0];
- }else{
- int s= maxValue + 1;
- initializeSieve(s);
- sieve(s);
- loadPrimes(s);
- return primes;
- }
- }
- private static void initializeSieve(int s){
- f= new boolean[s];
- int i;
- for(i=0;i<s;i++){
- f[i] = true;
- }
- f[0]=f[1]=false;
- }
- private static void sieve(int s){
- int i;
- int j;
- for(i=2;i<Math.sqrt(s)+1;i++){
- if(f[i]){
- for(j=2*i;j<s;j+=i)
- f[j] = false;
- }
- }
- }
- private static void loadPrimes(int s){
- int i ;
- int j;
- int count = 0;
- for(i=0;i<s;i++){
- if(f[i]){
- count++;
- }
- }
- primes = new int[count];
- for(i=0,j=0;i<s;i++){
- if(f[i]){
- primes[j++] = i;
- }
- }
- }
- public static void main(String args[]){
- int maxValue = 10;
- System.out.println(generatePrimes(maxValue));
- }
- }
version3:GeneratePrimesV3。java
最后,还对变量名和方法名称做更正,使其更符合实际上实现的意义。有人也许觉得更改名字的工作比较琐碎,但是对于代码的可读性以及维护成本是大有好处的。还有关键逻辑部分有关于数组长度的平方根问题,那个平方根未必就是素数,那个方法没有计算出罪的素数因子,说明性的注释是有误的。所以对注释重新写了,使他可以更好表达代码的平方根后面的原理,并且适当的改了变量的名字。
至于+1在那里起了什么作用呢?担心具有小数位的平方根会转换为小一点的整数,以至于不能充当遍历的上限。但是这种做法有必要吗?真正的遍历上限是小于或者等于数组长度平方根的最大素数。于是应该去掉+1,毫不犹豫。
- package Prime;
- public class GeneratePrimesV3 {
- private static boolean[] crossedOut;
- private static int[] result;
- public static int[] generatePrimes(int maxValue){
- if(maxValue < 2){
- return new int[0];
- }else{
- uncrossIntegersUpTo(maxValue);
- crossOutMultiples();
- putUncrossedIntegersIntoResult();
- return result;
- }
- }
- private static void uncrossIntegersUpTo(int maxValue){
- crossedOut = new boolean[maxValue + 1];
- for(int i=2;i<crossedOut.length;i++){
- crossedOut[i] = false;
- }
- }
- private static void crossOutMultiples(){
- int limit = determineIterationLimit();
- for(int i=2;i<limit;i++){
- if(notCrossed(i)){
- crossOutMultiplesOf(i);
- }
- }
- }
- private static int determineIterationLimit(){
- double iterationLimit = Math.sqrt(crossedOut.length);
- return (int)iterationLimit;
- }
- private static void crossOutMultiplesOf(int i){
- for(int multiple=2*i;multiple<crossedOut.length;multiple+=i){
- crossedOut[multiple]=true;
- }
- }
- private static boolean notCrossed(int i){
- return crossedOut[i]==false;
- }
- private static void putUncrossedIntegersIntoResult(){
- result = new int[numberOfUncrossedIntegers()];
- for(int j=0,i=2;i<crossedOut.length;i++){
- if(notCrossed(i)){
- result[j++]=i;
- }
- }
- }
- private static int numberOfUncrossedIntegers(){
- int count = 0;
- for(int i=2;i<crossedOut.length;i++){
- if(notCrossed(i)){
- count++;
- }
- }
- return count;
- }
- }
测试程序,TestGeneratePrimes.java
下面的测试程序有个大的特点,与原来用junit.framework.*下的TestCase不同,在mian方法中添加一个框架的main方法启动图形用户界面(GUI)来进行测试,是用swing做的,之前我用过swing写过一点简单的socket的即时通的小程序,好久没有用了。下面这样使用,运行出界面后,很是惊喜,运行结果用图片抓了出来,本来想放到这边博文中的,可是总是找不到csdn插入图片的工具,找到了后,也插入不进去,很是郁闷。
下面测试为了防止在改变程序后,有的边角没有测试到,另外一个方法 testExhaustive()来检查2~500之间产生的素数列表中没有倍数存在。
- package Prime;
- import junit.framework.*;
- /**
- * @version 1.3
- * @author ZHANGRONG
- *
- */
- public class TestGeneratePrimes extends TestCase{
- /**
- * @param args
- */
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- String[] testCaseName = { TestGeneratePrimes.class.getName() };
- junit.swingui.TestRunner.main(testCaseName);
- }
- public TestGeneratePrimes(String name){
- super(name);
- }
- public void testPrimes(){
- int[] nullArray = GeneratePrimesV3.generatePrimes(0);
- assertEquals(nullArray.length,0);
- int[] minArray = GeneratePrimesV3.generatePrimes(2);
- assertEquals(minArray.length,1);
- assertEquals(minArray[0],2);
- int[] threeArray = GeneratePrimesV3.generatePrimes(3);
- assertEquals(threeArray.length,2);
- assertEquals(threeArray[0],2);
- assertEquals(threeArray[1],3);
- int[] centArray = GeneratePrimesV3.generatePrimes(100);
- assertEquals(centArray.length,25);
- assertEquals(centArray[24],97);
- }
- public void testExhaustive(){
- for(int i=2;i<500;i++){
- verifyPrimeList(GeneratePrimesV3.generatePrimes(i));
- }
- }
- private void verifyPrimeList(int[] list){
- for(int i=0;i<list.length;i++){
- verifyPrime(list[i]);
- }
- }
- private void verifyPrime(int n){
- for(int factor=2;factor<n;factor++){
- System.out.print((n%factor!=0));
- }
- }
- }
结论:
写完这3个版本并且逐一测试后,发现重构后的程序读起来比一开始要好得多。程序变得更易理解,因此也更容易修改、变更,程序结构的各部分之间相互隔离,耦合性比较小。
from:http://blog.csdn.net/zhang13579rong/article/details/5307346