決定實施方案

2019-11-18 13:22:33

字體：大中小

來源：轉載

供稿：網友

　　從早些時候的那幅示意圖可以看出，實際上只有三個集合組件：Map，List和Set。而且每個接口只有兩種或三種實施方案。若需使用由一個特定的接口提供的功能，如何才能決定到底采取哪一種方案呢？
　　為理解這個問題，必須熟悉到每種不同的實施方案都有自己的特點、優點和缺點。比如在那張示意圖中，可以看到Hashtable，Vector和Stack的“特點”是它們都屬于“傳統”類，所以不會干擾原有的代碼。但在另一方面，應盡量避免為新的（java 1.2）代碼使用它們。
　　其他集合間的差異通常都可歸納為它們具體是由什么“后推”的。換言之，取決于物理意義上用于實施目標接口的數據結構是什么。例如，ArrayList，LinkedList以及Vector（大致等價于ArrayList）都實現了List接口，所以無論選用哪一個，我們的程序都會得到類似的結果。然而，ArrayList（以及Vector）是由一個數組后推得到的；而LinkedList是根據常規的雙重鏈接列表方式實現的，因為每個單獨的對象都包含了數據以及指向列表內前后元素的句柄。正是由于這個原因，假如想在一個列表中部進行大量插入和刪除操作，那么LinkedList無疑是最恰當的選擇（LinkedList還有一些額外的功能，建立于AbstractSequentialList中）。若非如此，就情愿選擇ArrayList，它的速度可能要快一些。
　　作為另一個例子，Set既可作為一個ArraySet實現，亦可作為HashSet實現。ArraySet是由一個ArrayList后推得到的，設計成只支持少量元素，非凡適合要求創建和刪除大量Set對象的場合使用。然而，一旦需要在自己的Set中容納大量元素，ArraySet的性能就會大打折扣。寫一個需要Set的程序時，應默認選擇HashSet。而且只有在某些非凡情況下（對性能的提升有迫切的需求），才應切換到ArraySet。
　　
　　1. 決定使用何種List
　　
　　為體會各種List實施方案間的差異，最簡便的方法就是進行一次性能測驗。下述代碼的作用是建立一個內部基礎類，將其作為一個測試床使用。然后為每次測驗都創建一個匿名內部類。每個這樣的內部類都由一個test()方法調用。利用這種方法，可以方便添加和刪除測試項目。
　　
　　//: ListPerformance.java
　　// Demonstrates performance differences in Lists
　　package c08.newcollections;
　　import java.util.*;
　　
　　public class ListPerformance {
　　　PRivate static final int REPS = 100;
　　　private abstract static class Tester {
　　String name;
　　int size; // Test quantity
　　Tester(String name, int size) {
　　　this.name = name;
　　　this.size = size;
　　}
　　abstract void test(List a);
　　　}
　　　private static Tester[] tests = {
　　new Tester("get", 300) {
　　　void test(List a) {
　　　　for(int i = 0; i < REPS; i++) {
　　　　　for(int j = 0; j < a.size(); j++)
　　　　　　a.get(j);
　　　　}
　　　}
　　},
　　new Tester("iteration", 300) {
　　　void test(List a) {
　　　　for(int i = 0; i < REPS; i++) {
　　　　　Iterator it = a.iterator();
　　　　　while(it.hasNext())
　　　　　　it.next();
　　　　}
　　　}
　　},
　　new Tester("insert", 1000) {
　　　void test(List a) {
　　　　int half = a.size()/2;
　　　　String s = "test";
　　　　ListIterator it = a.listIterator(half);
　　　　for(int i = 0; i < size * 10; i++)
　　　　　it.add(s);
　　　}
　　},
　　new Tester("remove", 5000) {
　　　void test(List a) {
　　　　ListIterator it = a.listIterator(3);
　　　　while(it.hasNext()) {
　　　　　it.next();
　　　　　it.remove();
　　　　}
　　　}
　　},
　　　};
　　　public static void test(List a) {
　　// A trick to print out the class name:
　　System.out.println("Testing " +
　　　a.getClass().getName());
　　for(int i = 0; i < tests.length; i++) {
　　　Collection1.fill(a, tests[i].size);
　　　System.out.print(tests[i].name);
　　　long t1 = System.currentTimeMillis();
　　　tests[i].test(a);
　　　long t2 = System.currentTimeMillis();
　　　System.out.println(": " + (t2 - t1));
　　}
　　　}
　　　public static void main(String[] args) {
　　test(new ArrayList());
　　test(new LinkedList());
　　　}
　　} ///:~
　　
　　內部類Tester是一個抽象類，用于為特定的測試提供一個基礎類。它包含了一個要在測試開始時打印的字串、一個用于計算測試次數或元素數量的size參數、用于初始化字段的一個構建器以及一個抽象方法test()。test()做的是最實際的測試工作。各種類型的測試都集中到一個地方：tests數組。我們用繼續于Tester的不同匿名內部類來初始化該數組。為添加或刪除一個測試項目，只需在數組里簡單地添加或移去一個內部類定義即可，其他所有工作都是自動進行的。
　　首先用元素填充傳遞給test()的List，然后對tests數組中的測試計時。由于測試用機器的不同，結果當然也會有所區別。這個程序的宗旨是揭示出不同集合類型的相對性能比較。下面是某一次運行得到的結果：
　　
　　類型獲取反復插入刪除
　　ArrayList 110 270 1920 4780
　　LinkedList 1870 7580 170 110
　　
　　可以看出，在ArrayList中進行隨機訪問（即get()）以及循環反復是最劃得來的；但對于LinkedList卻是一個不小的開銷。但另一方面，在列表中部進行插入和刪除操作對于LinkedList來說卻比ArrayList劃算得多。我們最好的做法也許是先選擇一個ArrayList作為自己的默認起點。以后若發現由于大量的插入和刪除造成了性能的降低，再考慮換成LinkedList不遲。
　　
　　2. 決定使用何種Set
　　
　　可在ArraySet以及HashSet間作出選擇，具體取決于Set的大小（假如需要從一個Set中獲得一個順序列表，請用TreeSet；注釋⑧）。下面這個測試程序將有助于大家作出這方面的抉擇：
　　
　　//: SetPerformance.java
　　package c08.newcollections;
　　import java.util.*;
　　
　　public class SetPerformance {
　　　private static final int REPS = 200;
　　　private abstract static class Tester {
　　String name;
　　Tester(String name) { this.name = name; }
　　abstract void test(Set s, int size);
　　　}
　　　private static Tester[] tests = {
　　new Tester("add") {
　　　void test(Set s, int size) {
　　　　for(int i = 0; i < REPS; i++) {
　　　　　s.clear();
　　　　　Collection1.fill(s, size);
　　　　}
　　　}
　　},
　　new Tester("contains") {
　　　void test(Set s, int size) {
　　　　for(int i = 0; i < REPS; i++)
　　　　　for(int j = 0; j < size; j++)
　　　　　　s.contains(Integer.toString(j));
　　　}
　　},
　　new Tester("iteration") {
　　　void test(Set s, int size) {
　　　　for(int i = 0; i < REPS * 10; i++) {
　　　　　Iterator it = s.iterator();
　　　　　while(it.hasNext())
　　　　　　it.next();
　　　　}
　　　}
　　},
　　　};
　　　public static void test(Set s, int size) {
　　// A trick to print out the class name:
　　System.out.println("Testing " +
　　　s.getClass().getName() + " size " + size);
　　Collection1.fill(s, size);
　　for(int i = 0; i < tests.length; i++) {
　　　System.out.print(tests[i].name);
　　　long t1 = System.currentTimeMillis();
　　　tests[i].test(s, size);
　　　long t2 = System.currentTimeMillis();
　　　System.out.println(": " +
　　　　((double)(t2 - t1)/(double)size));
　　}
　　　}
　　　public static void main(String[] args) {
　　// Small:
　　test(new TreeSet(), 10);
　　test(new HashSet(), 10);
　　// Medium:
　　test(new TreeSet(), 100);
　　test(new HashSet(), 100);
　　// Large:
　　test(new HashSet(), 1000);
　　test(new TreeSet(), 1000);
　　　}
　　} ///:~
　　
　　⑧：TreeSet在本書寫作時尚未成為一個正式的特性，但在這個例子中可以很輕松地為其添加一個測試。
　　
　　最后對ArraySet的測試只有500個元素，而不是1000個，因為它太慢了。
　　
　　類型測試大小添加包含反復
　　　決定實施方案