决定实施方案

　2008-01-05 09:51:03　来源：WEB开发网　　　

核心提示：从早些时候的那幅示意图可以看出，实际上只有三个集合组件：Map，决定实施方案，List和Set，而且每个接口只有两种或三种实施方案，而且性能明显与元素的多寡关系不大，一般编写程序的时候，若需使用由一个特定的接口提供的功能，如何才能决定到底采取哪一种方案呢？为理解这个问题

　　从早些时候的那幅示意图可以看出，实际上只有三个集合组件：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个，因为它太慢了。
　　
　　类型测试大小添加包含反复
　　　决定实施方案