[雜談]程式效能(二)

之前看到某個系統把陣列轉成字串的功能
臨時想到了關於功能的效能問題
所以就稍微記了一下
他大概的程式碼如下

 public String arrayToString(String[] input){

  StringBuffer result = new StringBuffer();

  if(input!=null){

   boolean isFirstElement = true;

   for(int i = 0; i<input.length; i++){

    if(isFirstElement){

     result.append(input[i]);     

    } else {

     result.append(", ");

     result.append(input[i]);

    }    

   }   

  }      

  return result.toString();

 }

這段大概的意思是將一個陣列轉成字串
第一個字以後都要用", "分開，所以需要用isFirstElement來判斷是不是第一筆資料
可是我覺得這個寫法除了多了一個暫存值以外
每個迴圈都要判斷一次是不是第一個感覺效能不是很好
於是我就思考如何把那個if去掉
後來想到的方法如下

 public String arrayToString(String[] input){

  StringBuffer result = new StringBuffer();

  if(input!=null && input.length>0){

   result.append(input[0]);

   

   for(int i = 1; i<input.length; i++){

    result.append(", ");

    result.append(input[i]);
       

   }  

  }      

  return result.toString();

 }

把for迴圈的i=0,  i<input.length(這句相當於input.length>0)拿掉
將這判斷式移到input!=null的後面
這樣除了把isFirstElement移掉以外
也不會多做if判斷，執行時間跟記憶體空間都能節省到
可讀性的問題也可以用，提供給大家參考!

[程式風格]Guard Clause

Guard Clause是一種程式的風格，通常會至少滿足其中一種以下的行為
1.檢查傳入的參數，如果檢驗不通過就回傳錯誤訊息
2.檢查物件的狀態，如果不符合function使用的物件就
3.簡單快速的處理明顯的邏輯

舉個例子像是以下的程式碼

  if(username!=null){

   if(password!=null){

    System.out.println("do something");
    //這邊是要處理的邏輯
   }else {

    System.out.println("password is null");

   }

  }else {

   System.out.println("username is null");

  }

我們可以知道username跟password皆不為null時才會執行程式
這邊我們可以閱讀是因為巢狀的條件還只有兩層，而且有進行縮排，要是越來越多層
或是程式碼一常，我們不見得可以閱讀程式的執行條件是什麼
以這個例子做出Guard Clause的話大概是長這個樣子

  if(username!=null && password!=null){

   System.out.println("do something");
   //這邊是要處理的邏輯
  }else if(password==null){

   System.out.println("password is null");

  }else{

   System.out.println("username is null");

  }

把要處理的邏輯直接表現出來，這樣是否感覺比較容易明白想要執行的邏輯呢?
我自己覺得還是看每個人習慣，不過這種程式風格就給各位當做參考了


參考資料：http://c2.com/cgi/wiki?GuardClause

[雜談]程式效能(一)

前幾天在FB上看到有大學生在某社團問作業：1加到10的程式怎麼做
然後看到一些很有趣的解答
剛好趁機談談程式的效能
由1加到n這個運算
很直觀的做法就是1+2+3+4+5+6.+..+n
用for迴圈表示就是i=1到n，result= result+i;
但是這樣你數字越大他要跑的迴圈就越常
同樣的計算結果你用高斯方法就是n*(n+1)/2
不管你的n有多大，程式永遠做一次加法，一次乘法，一次除法
這就是所謂好的演算法
那對效能有什麼影響呢，以下我們拿這個範例程式
第一個呼叫的是for迴圈的方法
第二個呼叫的是高斯方法
我使用了結果程式的時間減掉程式開始時間來計算每一個方法使用了多少毫秒
程式碼如下

import java.util.Date;



public class SumTest {



 public static void main(String[] args) {

  

  useForLoop(10000000);

  useGaussMethod(10000000);

 }



 public static void useForLoop(long input){

  long result = 0;

  long startTime = new Date().getTime();

  for(long i = 1;i<=input;i++){

   result = result + i;

  }

  System.out.println(result);

  long endTime = new Date().getTime();

  long totalTime = endTime-startTime;

  System.out.println(totalTime);

 }

 

 public static void useGaussMethod(long input){

  long startTime = new Date().getTime();

  long result = input*(input+1)/2;

  System.out.println(result);

  long endTime = new Date().getTime();

  long totalTime = endTime-startTime;

  System.out.println(totalTime);

 }

 

}

然後實驗開始啦，首先是n等於一萬

看起來兩個花的時間都是0毫秒沒什麼差別，於是我將n值放大到十萬

似乎有點差別了，不過可能是誤差，再放大n到100萬看看

差距來到了三毫秒，最後我們再放大n到1000萬

for回圈的消耗時間增加到了25毫秒

所以我們可以知道

在資料量小的時候，我們不一定能感覺出演算法的好壞

但是好的演算法在輸入的值越大的時候，節省的效能會越明顯

雖然一般來講先完成功能就好，但是當功能完成之後應該要去思考如何提升程式效能提高使用品質

之後會不會繼續這個主題就看我有沒有時間囉~_~+

[Java]複製陣列的方法(System.arraycopy)

有時候需要建立一個新陣列，這個新陣列跟舊的陣列前面都一樣
只有最後幾個值不同或是加了幾個值

或是有兩個陣列，我們需要合併這兩個陣列的時候
除了用for迴圈把陣列一個一個倒進去以外
我們可以使用System的arraycopy方法

文件方法如下
arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

第一個src要放入的是被複製的陣列
srcPos是指定被複雜的陣列從第幾項開始複製

dest放入的是要複製的陣列
destPos是指定要複製的陣列從第幾項開始寫入

length放入的是你總共要複製幾項資料
以下是最常用的兩個範例

public class copyArrayDemo {



 public static void main(String[] args) {

  System.out.println("This is demo 1");

  int[] arr1 = {1,2,3};

  int[] arr2 = new int[arr1.length+1];

  System.arraycopy(arr1, 0, arr2, 0, arr1.length);

  arr2[arr1.length]= 4;

  // arr2 == {1,2,3,4}

  for(int item:arr2){

   System.out.println(item);

  }

  System.out.println("This is demo 2");



  

  String[] array1 = {"item1","item2","item3"};  

  String[] array2 = {"demo1","demo2","demo3"};

  

  

  String[] sum = new String[array1.length+array2.length];

  System.arraycopy(array1, 0, sum, 0, array1.length);

  System.arraycopy(array2, 0, sum, array1.length, array2.length);

  // sum =={"item1","item2","item3","demo1","demo2","demo3"}

  for(String item:sum){

   System.out.println(item);

  }    

 }

}

[Java]StringTokenizer

今天介紹一個除了split()方法以外，分割String的方法
StringTokenizer的方法主要有下列幾個

countTokens()：可以知道你的String被Tokenizer分成幾段
hasMoreTokens()：檢查StringTokenizer是否還有Token
nextToken()：將StringTokenizer的下一個Token用String表示

以下是簡單的範例：

import java.util.StringTokenizer;



public class StringDemo {


 public static void main(String[] args) {

  String demo = "String,int,long,double";



  StringTokenizer st = new StringTokenizer(demo,",");

 

  System.out.println("st has "+st.countTokens()+"tokens");

 

  while(st.hasMoreTokens()){

   System.out.println();

  }

 }

}

[Java面試考題]Map處理

今天去松凌科技面試時遇到的考題
限時30分鐘
做出來後我問了一下面試官說能不能把考題公佈
面試官很慷慨的答應了，表示說他們也希望大家都能夠會處理map
於是我回家後馬上將這題題目重現
中文的註解可能有些誤差，以下是題目跟參考解答
題目詳細內容請見註解

import java.util.HashMap;

import java.util.Map;



public class RightLeft {

 

 Map<String, Integer> left;

 Map<String, Integer> right;

 

 public void setUp(){

  left = new HashMap<String, Integer>();

  left.put("a", 1);

  left.put("b", 2);

  left.put("c", 3);

  

  right = new HashMap<String, Integer>();

  right.put("b", 2);

  right.put("c", 4);

  right.put("d", 5);

  

 }

 

 /*

  * <pre>

  * 備住：有兩個Map left right，請在Test()內完成程式碼輸出以下內容

  *

  * 1.key一樣value不一樣的內容

  * 2.key一樣value一樣的內容

  * 3.key只存在left不存在right的內容

  * 4.key只存在right不存在left的內容

  *

  */

 

 public void Test(){

  

  //answer of 1

  System.out.println("1.");

  for(Object key:left.keySet()){

   if(right.get(key)!=null){

    if(!right.get(key).equals(left.get(key))){

     System.out.println("left key="+key+", value="+left.get(key));

     System.out.println("right key="+key+", value="+right.get(key));

    }

   }   

  }

  

  //answer of 2

  System.out.println("2.");

  for(Object key:left.keySet()){

   if(right.get(key)!=null){

    if(right.get(key).equals(left.get(key))){

     System.out.println("left: key="+key+", value="+left.get(key));

     System.out.println("right: key="+key+", value="+right.get(key));

    }

   }   

  }

  

  //answer of 3

  System.out.println("3.");

  for(Object key:left.keySet()){

   if(right.get(key)==null){  

     System.out.println("left: key="+key+", value="+left.get(key));    

   }   

  }

  

  //answer of 4

  System.out.println("4.");

  for(Object key:right.keySet()){

   if(left.get(key)==null){

    

     System.out.println("right: key="+key+", value="+right.get(key));

    

   }   

  }

  

  

 }

 

  

 

 public static void main(String[] args) {

  RightLeft demo = new RightLeft();

  demo.setUp();

  demo.Test();



 }



}

[Java]如何求N個整數的最大公因數

這個問題我認為原理非常的簡單...我在學Java的第一週就可以把他做出來
不過後來時間久了就忘記要把這個問題的解法丟上來

趁著現在比較有空的時間把教學簡單的打一下


首先從兩個整數的最大公因數開始
整數的最大公因數就是能夠同時整除他們的最大整數
求最大公因數的方法有很多種，其中一種方法叫做輾轉相除法
我們直接拿30跟18這兩個整數做例子
30/18=1餘12
18/12=1餘6
12/6=2

由於6整除了，所以30跟18的最大公因數就是6

從例子我們知道做法就是如果兩數沒有整除，就把原來的除數當做被除數，把餘數當做除數繼續除下去，直到兩數整除為止

於是我們可以知道求a,b兩數的最大公因數，相當於求b與a,b的餘數的最大公因數
以下就是簡單的範例，我們用一般的while迴圈展示輾轉相除法的演算法
另外使用遞迴當做參考

public class Gcd {



 public static void main(String[] args) {  

  //demo1

  System.out.println(gcd(18,12));

    

  //demo2

  System.out.println(gcd2(30,18));  



 }



 public static int gcd(int m, int n){

  int result = 1;

  while(m%n!=0){

   result=n;   

   n=m%n;

   m=result;

  }

  result=n;

  

  return result;

 }

 

 public static int gcd2(int m, int n){

  if(m%n==0){

   return n;

  } else {

   return gcd2(n,m%n);

  }  

 } 

}

接下來三個整數的最大公因數就是將前兩個最大公因數跟第三個數字做最大公因數
四個整數的最大公因數則是將三個整數的最大公因數與第四個數字做最大公因數...
以此類推
以下程式碼就只用while迴圈當範例，遞迴的寫法請自情參考兩個整數的程式碼

public class Gcd {



 public static void main(String[] args) {

  

  //demo1

  int[] x = new int[] {18,12,30};  

  System.out.println(dogcd(x));  

  

  //demo2 

  int[] y = new int[] {15,18,30,42,9};

  System.out.println(dogcd(y));

 }

 

 public static int dogcd(int[] input){

  for(int i=0;i<input.length-1;i++){

   input[i+1] = gcd(input[i],input[i+1]);

      

  }  

  return input[input.length-1];

 }



 public static int gcd(int m, int n){

  int result = 1;

  while(m%n!=0){

   result=n;   

   n=m%n;

   m=result;

  }

  result=n;

  

  return result;

 }
  

}