2012年4月18日 星期三

100年警察特考資訊處理三等第五小題解答(下)

五、Collection Framework(即Collection其subclass如ArrayList和LinkedList)都有提供排序的功能(即sort()的method或function),但都只限於數值型態(如Integer或Double等)或String所構成的Collection。請問如何讓一般Class的物件所組成的Collection也可以直接使用Collection所提供的排序功能?(Class需做那些事情?)(15分)(警三100)


最後我們來看這個題目的答法,
畢竟寫答案跟理解是不一樣低。

答1:
一般自建Class可透過implement Comparable方式使用Collection提供的排序功能,
透過實現Comparable介面(interface),實作該interface的compareTo() method,如下例:
假設有三個學生,我們要讓他們按照身高排序:
1.學生類別(Student)設計如下:
public class Student {
   //建構子,constructor


   Student(int h,int n){
          height=h;
          number=n;
   }
   //學生的屬性
   int height; //身高
   int number; //座號
}
2.要使其可使用Collection自動排序,需implement comparable,並實作compareTo()方法:
public int compareTo(Object a) {
    if(this.height>((Student)a).height)
         return -1; //-1表示後面a物件比較大
    else if(this.height==((Student)a).height)
         return 0; //0表示相等
    else
         return 1; //1表示後面a物件比較小
}
如此一來,Collection便可透過此方法得知判斷大小的依據來排序,
即可使用Collections.sort(array)來進行排序。
整體程式碼如下(省略import部分):
public class Student implements Comparable{


//學生的屬性
int height; //身高
int number; //座號


//建構子,constructor
public Student(int height, int number) {
     this.height = height;
     this.number = number;
}


//因implement Comparable interface所以要寫的compareTo method
public int compareTo(Object a) {
    if(this.height>((Student)a).height)
         return -1;   //-1表示後面a物件比較大


    else if(this.height==((Student)a).height)
         return 0;    //0表示相等


    else
         return 1;   //1表示後面a物件比較小


}
//覆寫這個method方便我們做列印
public String toString(){
      return "身高:"height+",座號:"+number;
}


public static void main(String[] args) {
       //有三個學生,分別是a:身高160,座號1;b:身高:170,座號:2;c:身高:180,座號:3

       Student a=new Student(160,1);
       Student b=new Student(170,2);
       Student c=new Student(180,3);
       ArrayList arrayList=new ArrayList();
       arrayList.add(a);
       arrayList.add(b);
       arrayList.add(c);
       //排序前印出來看看吧
       for(Student i:arrayList)
             System.out.println(i);
      //排序中
      Collections.sort(arrayList);
      System.out.println("排序後:");
      //排序完印出來看看吧
      for(Student i:arrayList)
          System.out.println(i);
       }
}
列印結果為:
身高:160,座號:1
身高:170,座號:2
身高:180,座號:3
排序後:
身高:180,座號:3
身高:170,座號:2
身高:160,座號:1

如果是我,我當下立馬會這樣答,
不過你現在都已經知道還有其他兩種case了,
就要連同他們一起答。

答2:
一般自建Class可透過下列方式使用Collection提供的排序功能:
(一)implement Comparable:
透過實現Comparable介面(interface),實作該interface的compareTo() method,如下例:

假設有三個學生,我們要讓他們按照身高排序。

public class Student implements Comparable{
//學生的屬性
int height; //身高
int number; //座號
//建構子,constructor
public Student(int height, int number) {
   this.height = height;
   this.number = number;
}
//因implement Comparable interface所以要寫的compareTo method
public int compareTo(Object a) {
      if(this.height>((Student)a).height)
              return -1; //-1表示後面a物件比較大
     else if(this.height==((Student)a).height)
             return 0; //0表示相等
    else
            return 1; //1表示後面a物件比較小
}
//覆寫這個method方便我們做列印
public String toString(){
      return "身高:"height+",座號:"+number;
}
public static void main(String[] args) {
//有三個學生,分別是a:身高160,座號1;b:身高:170,座號:2;c:身高:180,座號:3
     Student a=new Student(160,1);
     Student b=new Student(170,2);
     Student c=new Student(180,3);
     ArrayList arrayList=new ArrayList();
           arrayList.add(a);
           arrayList.add(b);
           arrayList.add(c);
    //排序前
   for(Student i:arrayList)
         System.out.println(i);
  //使用collections.sort進行排序
  Collections.sort(arrayList);
  System.out.println("排序後:");
  for(Student i:arrayList)
         System.out.println(i);
  }
}
列印結果為:
身高:160,座號:1
身高:170,座號:2
身高:180,座號:3
排序後:
身高:180,座號:3
身高:170,座號:2
身高:160,座號:1

透過implement Comparable,實作compareTo() method,以提供Collections比較的基準依據,
即可使用如上例中Collections.sort(arrayList)進行排序。
另,在compareTo() method中不使用將兩物件的height屬性相減,改以if判斷式是為了可讀性(readable)。

(二)使用Comparator介面:
上例中,亦可使用Comparator介面來實作compare()方法,如下例:
public class CompareByHeight implements Comparator Student>{

          public int compare(Student a, Student b) {
              if(a.height>b.height)
                    return -1; //b比較高,排前面
             else if(a.height==b.height)
                   return 0; //a,b一樣高
             else
                   return 1; //a比較高,排前面
           }
}
即可在main中以Collections.sort(arrayList,new CompareByHeight());方式排序。
(三)自建Class本身已繼承自已實現comparable的class:
直接覆寫compareTo()method即可。


因本題只有15分,斟酌著寫即可,程式碼占很大部分,實在無法刪除。

2012年4月17日 星期二

100年警察特考資訊處理三等第五小題解答(中)

在上篇我們提到了第一種的解決方式。
你可能會大驚!啥!那才第一種?
事實上,寫法有很多種,端看你的應用。

寫在前頭,如果你是為了考試,看上篇跟下篇就可以。
如果你是路過想要學怎麼用comparator,可以看上跟中篇

我們來想想上篇所說的那個排隊問題,
如果你今天是想要學生按照座號排呢?
相信你也很聰明,之道要改哪裡了。
但是如果你今天有時候想要讓他按照座號排,
有時候想要按身高,
那程式要怎麼寫?

當然不是叫你自創用:
compareToByHeight()
compareToByNumber()

這些method就可達成,因為Java的Collection看不懂
他只認得compareTo()。

那怎麼辦?
相信大家還有一個印象,就是上篇有提到API中還有另外一個sort():

static void sort(List list, Comparator c)

那個Comparator就是解答。

我們上篇有提到,Collection就是那個班長幫你排順序的人,
他的工作就是用很快的排序方法幫你排序,
但是你必須告訴他,
你的比較標準是什麼,
假使你今天同時可能有需要多個比較標準,
比如說你的應用可能一下子要按照號碼排,
一下子要按照身高排,
一下子要按照年齡排,
你就需要三個比較標準,
這個比較標準就是用Comparator去寫。

先來看一下Comparator的API:
java.util
Interface Comparator
又是interface,有2個method要implement(實作):
int compare(T o1, T o2)

boolean equals(Object obj)

Comparator API中有一個T的部分,
那個就是泛型(generic),
讓你可以放進去各式類別的,
以我們的例子就是放進去Student,
強烈建議大家可以動動腦想看看要怎麼用它,
再來看我的答案。

//比較基準1:身高
import java.util.Comparator;


public class CompareByHeight implements Comparator Student>{

    @Override
    public int compare(Student a, Student b) {
        // TODO Auto-generated method stub
        if(a.height>b.height)
            return -1;
        else if(a.height==b.height)
            return 0;
        else
            return 1;
    }

}


//比較基準2:年齡

import java.util.Comparator;
//後面那個Student的前面有個小括號,請自行補上,blog秀不出來

public class CompareByAge implements Comparator Student> {

    @Override
    public int compare(Student a, Student b) {
        // TODO Auto-generated method stub
        if(a.age>b.age)
            return -1;
        else if(a.age==b.age)
            return 0;
        else
            return 1;
    }

}


在main中測試:

         System.out.println("排序前:");
         //排序前印出來看看吧
         for(Student i:arrayList)
               System.out.println(i);


         //按身高排
         Collections.sort(arrayList,new CompareByHeight());

         System.out.println("按身高排序後(比較高的在前):");
         //排序完印出來看看吧
         for(Student i:arrayList)
                System.out.println(i);
        
         //按年齡排
         Collections.sort(arrayList,new CompareByAge());
        
         System.out.println("按年齡排序後(比較大的在前):");
         //排序完印出來看看吧
         for(Student i:arrayList)
                System.out.println(i);



以這個例子的設定,
將學生按照年齡、身高排,
看起來似乎有點像是資料庫可以照各種欄位排序,
在此提醒各位正在使用Java DAO、
或是各種Java Framework來存取資料庫的捧友們,
從資料庫拿出來,再排序,這樣的方法是蠻不智的,
請直接再查詢select資料庫時寫好指令即可,
ex:select * from students order by height;
因為DBMS在查詢時通常會加速,
除非你的比較規則很複雜,
像是女神挑男人一樣,
先比年收、財產,再比身高、帥氣指數(誤),
這樣才需要自己寫。

另外還要提醒您,如果你已經繼承了具有Comparable的class,
就直接覆寫就好了,如下例:


import java.util.ArrayList;
import java.util.Collections;


public class ManStudent extends Student {

    public ManStudent(int height, int age, int number) {
        super(height, age, number);
        // TODO Auto-generated constructor stub
    }
    int money;//年收
   
    public ManStudent(int height, int age, int number, int money) {
        super(height, age, number);
        this.money = money;
    }

    @Override
    //因implement Comparable interface所以要寫的compareTo method
    public int compareTo(Object arg0) {
        // TODO Auto-generated method stub
        if(this.money>((ManStudent)arg0).money)
            return -1;
        else if(this.money==((ManStudent)arg0).money)
            return 0;
        else
            return 1;
    }
   
    //覆寫這個method方便我們做列印
    public String toString(){
           return height+" "+age+" "+number+" "+money;
    }
   
    public static void main(String[] args) {
        ManStudent a=new ManStudent(180,19,3,200000);
        ManStudent b=new ManStudent(170,21,2,3000000);
        ManStudent c=new ManStudent(180,19,3,10000);
       
        ArrayList arrayList=new ArrayList();

         arrayList.add(a);
         arrayList.add(b);
         arrayList.add(c);

         System.out.println("排序前:");
         //排序前印出來看看吧
         for(Student i:arrayList)
               System.out.println(i);
        
       //按年收排
         Collections.sort(arrayList);
        
         System.out.println("按年收排序後(比較有錢的在前):");
         //排序完印出來看看吧
         for(Student i:arrayList)
                System.out.println(i);
    }
}

2012年4月16日 星期一

100年警察特考資訊處理三等第五小題解答(上)

轉路人甲之疑問:

五、Collection Framework(即Collection其subclass如ArrayList和LinkedList)都有提供排序的功能(即sort()的method或function),但都只限於數值型態(如Integer或Double等)或String所構成的Collection。請問如何讓一般Class的物件所組成的Collection也可以直接使用Collection所提供的排序功能?(Class需做那些事情?)(15分)(警三100)

路人甲說百查不解,請女神解釋。

這個問題問得很好,我想有用過c的lib者也大概知道要怎麼回答,故可以跳過這篇說明,直接看下篇即可,這邊先針對java到底要怎麼實作這件事情來做個更詳細的介紹。

首先,我們來解釋一下題目的意思。

一般我們想要對一個數字陣列排序,你會怎麼做?

int array[]={1,3,1,5,9};

方法1:

話說我們曾經在資料結構裡面,學過一堆演算法,比如說泡沫、heap等等,當然,你可以自己寫,不過,實際工作時我們可不會這麼.....蠢,這種事情,別人當然寫過,所以你可能的做法是:

1.上網複製別人的sort method

public void heapSort(int arr[]){
...
}

2.每次要用的時候都call他

heapSort(array);



方法2:

事實上,你不必這麼搞剛,物件導向的書裡面有一句名言:別自己創造人家做過的輪子,套句鄉民的話就是:這種事還是交給專業的來吧!

Java有一個類別叫做Arrays,他裡面就有專業的sort會幫你處理:

Arrays.sort(array);

人生就是這麼簡單。
Arrays提供一些簡單的型態(int, double...etc)排序方法,讓你丟進去就可以排序,而且排得很快,請詳見API
你可以比較看看,專業的跟你自己寫的,誰排得比較快,答案當然是專業的。


方法3:

那題目的Collection是在做什麼的?

客官有所不知,一般來說,我們Java使用者,不太喜歡用array,比較喜歡把ArrayList當做array在用。
為什麼要這麼做?因為ArrayList很方便。
他有動態array的優點,你只消丟給他元素即可,不需要去管他現在總共有幾個元素,也不用配置記憶體(雖然Java也不給用),想知道array總共有幾個元素也只要call他的method就可以知道,總之,ArrayList會幫你管理array。

比如說,咱們題目的

int array[]={1,3,1,5,9};


就可以把它變成ArrayList:

ArrayList a=new ArrayList();
a.add(1);
a.add(3);
a.add(1);
a.add(5);
a.add(9);

如果你會看API(你必須同時去看ArrayList跟Arrays的API),自然不需要這麼...蠢,直接用這個
ArrayList a=new ArrayList(Arrays.asList(array));
就可以得到ArrayList a了。

然後你要怎麼排序呢?
題目說要用Collections,你查了API裡面有二個sort,順便教大家怎麼看api:

static void sort(List list)
static void sort(List list, Comparator c)

在大家不會使用2號sort之前,我們先來看1號sort,他說他只能接受List這個class。
我們查一下List的API,會發現他其實是一個抽象的interface,底下有很多實現他的class,包含我們的ArrayList:

java.util
Interface List
All Superinterfaces:
Collection
All Known Implementing Classes:
AbstractList, ArrayList, LinkedList, Vector

所以我們可以很沒有問題的塞ArrayList進去sort(List list) 這個方法,把他排序一番,使用:

Collections.sort(a);

排序就完成了。
不過就像題目說的,他只能排序一些他知道怎麼比大小的類別,比如說int,double等等一些常用的,還有Java本身提供的一些常用比大小的類別,其他你自己訂的類別,當然就要你自己想辦法了。

這個道理很簡單,Java怎麼知道你的class,到底要用什麼來當做比較基準阿?!XD

舉個例子來說,回想一下你小時候學生排隊伍升旗的情形,是不是一開始總有一個指揮者,比如是班長之類的,先按照大家的身高來排隊?

你可以想像那個指揮者就是Collections,每一個同學都是一個Student類別的Object,比較的基準自然就是身高了。

我們先來將這個例子轉化為code:

public class Student {
   
     Student(int h,int a,int n){
              height=h;
              age=a;
              number=n;
     }

     int height;   //身高
     int age;  //年齡
     int number;  //座號
}

public static void main(){
    Student a=new Student(160,20,1);
    Student b=new Student(170,21,2);
    Student c=new Student(180,19,3);

     //弄三個學生物件就好,不然好累=口="
}

現在我們把這三個學生按照身高排,問題是,要怎麼排呢?

當然你可以用方法1,把程式碼內比較的基準改成student.height:

public static void heapSort(Student s[]){
    .....
    if(s[i].height> s[j].height)
     .....
}

恩,我想你也知道,如果按照這種寫法,絕對不夠專業,這種事情讓專業的來就好了,問題是怎麼請出"專業的"Collections來幫你排序呢?

我們剛剛有提到,你把Collections當做那個指揮者,叫他幫你排序,如果你只要告訴他,我要以什麼基準當做排序的標準,讓你去幫你排,那該有多好阿!

比如說,我們告訴他比較的基準如下:

if(studentA.height>studentB.height)    
     return A比較高
else if(studentA.height==studentB.height)

     return A跟B一樣高
else
     return A比較矮

告訴他判斷的標準,然後他就會自己用Collections.sort幫我們排好,事實上,只需要告訴他這個判斷的method:

if(studentA.height>studentB.height)

          return -1; //1表示後面比較大
else if(studentA.height==studentB.height)
          return 0; //0表示相等
else
          return 1; //-1表示後面比較小

他就會自己處理了。
告訴他的方式,首先,你要透過Comparable這個interface去跟Collections溝通,跟他說你準備有一個判斷標準,寫在compareTo這個method中,叫他去用:
public class Student implements Comparable{

     Student(int h,int a,int n){
           height=h;
           age=a;
           number=n;
     }

     int height; //身高
     int age; //年齡
     int number; //座號

     public int compareTo(Object o) {


             if(this.height>((Student)o).height)

                        return -1; //-1表示後面比較大
             else if(this.height==((Student)o).height)
                        return 0; //0表示相等
             else
                        return 1; //1表示後面比較小
       }
}
簡單的說明一下在這裡實現compareTo()這個method的技巧:

1.API裡面寫到
int compareTo(Object o)

所以我們要實現,你就一定要照這個介面寫:

   public int compareTo(Object o) {

   }


2.但是compareTo竟然接受的是Object類別!所以我們只好靠強制轉型((Student)o),以取得他的身高屬性height,所以才會有:

if(this.height>((Student)o).height)



這樣的寫法。
做完這樣的設定後,你只要按照剛剛的ArrayList寫法,就可以讓他們按照身高排序了:

ArrayList arraylist=new ArrayList();
arraylist.add(a);
arraylist.add(b);
arraylist.add(c);


Collections.sort(arraylist);

因為後來作者跑去護膚了,所以你看不到我,有人今天寫信來跟我說我有弄錯,如果你需要完整的程式碼,請洽下方:
import java.util.ArrayList;
import java.util.Collections;


public class Student implements Comparable{

    //學生的屬性
    int height;    //身高
    int age;    //年齡
    int number;    //座號
  
    //建構子,constructor
    public Student(int height, int age, int number) {
        super();
        this.height = height;
        this.age = age;
        this.number = number;
    }

    @Override
    //因implement Comparable interface所以要寫的compareTo method
    public int compareTo(Object arg0) {
        // TODO Auto-generated method stub
        if(this.height>((Student)arg0).height)
            return -1;
        else if(this.height==((Student)arg0).height)
            return 0;
        else
            return 1;
    }
    //覆寫這個method方便我們做列印
    public String toString(){
           return height+" "+age+" "+number;
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Student a=new Student(160,20,1);
        Student b=new Student(170,21,2);
        Student c=new Student(180,19,3);
        ArrayList arrayList=new ArrayList();

         arrayList.add(a);
         arrayList.add(b);
         arrayList.add(c);

         //排序前印出來看看吧
         for(Student i:arrayList)
               System.out.println(i);


         //排序中
         Collections.sort(arrayList);

         //排序完印出來看看吧

         for(Student i:arrayList)
                System.out.println(i);
    }
}
已compile測試過沒問題。
有問題再跟我說,這篇還會有中跟下,上跟中適合java學習使用者,下集會講怎麼寫這個題目,至於更新時間嘛...看我的心情XD。

補充:對了!順道提起一件事情,事實上,c++的得意使用者,可能會跟我說,compareTo()那個這樣寫就好了:
public int compareTo(Object o) {

        return ((Student)o).height-this.height;
}

的確這樣也是有同樣的效果,但除非你是因為要寫driver(有人會用java寫driver?),是效能導向,否則很不建議你做這種事情,因為"可讀性",請體諒一下接你code的人,在沒精神之下還要幫你看code的同事吧!。