決定實(shí)施方案

2019-11-18 13:22:33

字體：大中小

供稿：網(wǎng)友

　　從早些時(shí)候的那幅示意圖可以看出，實(shí)際上只有三個(gè)集合組件：Map，List和Set。而且每個(gè)接口只有兩種或三種實(shí)施方案。若需使用由一個(gè)特定的接口提供的功能，如何才能決定到底采取哪一種方案呢？
　　為理解這個(gè)問(wèn)題，必須熟悉到每種不同的實(shí)施方案都有自己的特點(diǎn)、優(yōu)點(diǎn)和缺點(diǎn)。比如在那張示意圖中，可以看到Hashtable，Vector和Stack的“特點(diǎn)”是它們都屬于“傳統(tǒng)”類，所以不會(huì)干擾原有的代碼。但在另一方面，應(yīng)盡量避免為新的（java 1.2）代碼使用它們。
　　其他集合間的差異通常都可歸納為它們具體是由什么“后推”的。換言之，取決于物理意義上用于實(shí)施目標(biāo)接口的數(shù)據(jù)結(jié)構(gòu)是什么。例如，ArrayList，LinkedList以及Vector（大致等價(jià)于ArrayList）都實(shí)現(xiàn)了List接口，所以無(wú)論選用哪一個(gè)，我們的程序都會(huì)得到類似的結(jié)果。然而，ArrayList（以及Vector）是由一個(gè)數(shù)組后推得到的；而LinkedList是根據(jù)常規(guī)的雙重鏈接列表方式實(shí)現(xiàn)的，因?yàn)槊總€(gè)單獨(dú)的對(duì)象都包含了數(shù)據(jù)以及指向列表內(nèi)前后元素的句柄。正是由于這個(gè)原因，假如想在一個(gè)列表中部進(jìn)行大量插入和刪除操作，那么LinkedList無(wú)疑是最恰當(dāng)?shù)倪x擇（LinkedList還有一些額外的功能，建立于AbstractSequentialList中）。若非如此，就情愿選擇ArrayList，它的速度可能要快一些。
　　作為另一個(gè)例子，Set既可作為一個(gè)ArraySet實(shí)現(xiàn)，亦可作為HashSet實(shí)現(xiàn)。ArraySet是由一個(gè)ArrayList后推得到的，設(shè)計(jì)成只支持少量元素，非凡適合要求創(chuàng)建和刪除大量Set對(duì)象的場(chǎng)合使用。然而，一旦需要在自己的Set中容納大量元素，ArraySet的性能就會(huì)大打折扣。寫一個(gè)需要Set的程序時(shí)，應(yīng)默認(rèn)選擇HashSet。而且只有在某些非凡情況下（對(duì)性能的提升有迫切的需求），才應(yīng)切換到ArraySet。
　　
　　1. 決定使用何種List
　　
　　為體會(huì)各種List實(shí)施方案間的差異，最簡(jiǎn)便的方法就是進(jìn)行一次性能測(cè)驗(yàn)。下述代碼的作用是建立一個(gè)內(nèi)部基礎(chǔ)類，將其作為一個(gè)測(cè)試床使用。然后為每次測(cè)驗(yàn)都創(chuàng)建一個(gè)匿名內(nèi)部類。每個(gè)這樣的內(nèi)部類都由一個(gè)test()方法調(diào)用。利用這種方法，可以方便添加和刪除測(cè)試項(xiàng)目。
　　
　　//: 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());
　　　}
　　} ///:~
　　
　　內(nèi)部類Tester是一個(gè)抽象類，用于為特定的測(cè)試提供一個(gè)基礎(chǔ)類。它包含了一個(gè)要在測(cè)試開(kāi)始時(shí)打印的字串、一個(gè)用于計(jì)算測(cè)試次數(shù)或元素?cái)?shù)量的size參數(shù)、用于初始化字段的一個(gè)構(gòu)建器以及一個(gè)抽象方法test()。test()做的是最實(shí)際的測(cè)試工作。各種類型的測(cè)試都集中到一個(gè)地方：tests數(shù)組。我們用繼續(xù)于Tester的不同匿名內(nèi)部類來(lái)初始化該數(shù)組。為添加或刪除一個(gè)測(cè)試項(xiàng)目，只需在數(shù)組里簡(jiǎn)單地添加或移去一個(gè)內(nèi)部類定義即可，其他所有工作都是自動(dòng)進(jìn)行的。
　　首先用元素填充傳遞給test()的List，然后對(duì)tests數(shù)組中的測(cè)試計(jì)時(shí)。由于測(cè)試用機(jī)器的不同，結(jié)果當(dāng)然也會(huì)有所區(qū)別。這個(gè)程序的宗旨是揭示出不同集合類型的相對(duì)性能比較。下面是某一次運(yùn)行得到的結(jié)果：
　　
　　類型獲取反復(fù) 插入刪除
　　ArrayList 110 270 1920 4780
　　LinkedList 1870 7580 170 110
　　
　　可以看出，在ArrayList中進(jìn)行隨機(jī)訪問(wèn)（即get()）以及循環(huán)反復(fù)是最劃得來(lái)的；但對(duì)于LinkedList卻是一個(gè)不小的開(kāi)銷。但另一方面，在列表中部進(jìn)行插入和刪除操作對(duì)于LinkedList來(lái)說(shuō)卻比ArrayList劃算得多。我們最好的做法也許是先選擇一個(gè)ArrayList作為自己的默認(rèn)起點(diǎn)。以后若發(fā)現(xiàn)由于大量的插入和刪除造成了性能的降低，再考慮換成LinkedList不遲。
　　
　　2. 決定使用何種Set
　　
　　可在ArraySet以及HashSet間作出選擇，具體取決于Set的大小（假如需要從一個(gè)Set中獲得一個(gè)順序列表，請(qǐng)用TreeSet；注釋⑧）。下面這個(gè)測(cè)試程序?qū)⒂兄诖蠹易鞒鲞@方面的抉擇：
　　
　　//: 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在本書(shū)寫作時(shí)尚未成為一個(gè)正式的特性，但在這個(gè)例子中可以很輕松地為其添加一個(gè)測(cè)試。
　　
　　最后對(duì)ArraySet的測(cè)試只有500個(gè)元素，而不是1000個(gè)，因?yàn)樗恕?br />　　
　　類型測(cè)試大小添加包含反復(fù)
　　　決定實(shí)施方案