Chapter 17 - Exercise 35

(1) Modify MapPerformance.java to include tests of SlowMap.


Test.java

策略对象接口。



package com.ciaoshen.thinkinjava.newchapter17;

// 无状态对象模拟函数指针(策略模式)
// 适合用匿名内部类的形式初始化
interface Test<C> {
    long test(C container, int times);
}


Tester.java

调用策略对象的工具类。可以对给定的某个容器,执行所有单元测试。



package com.ciaoshen.thinkinjava.newchapter17;
import java.util.*;

// 包级私有
final class Tester<C> {
    /**
     * 配置成员域
     */
    private static final int[] defaultParams = new int[]{10,5000,100,5000,1000,500,10000,50};
    private int[] paramList = defaultParams; // 参数
    private final C container; // 被测试容器
    private final Map<String,Test<C>> tests; // 测试策略对象注册表
    private final String header; // 标题

    /**
     * 配置函数
     */
    public C initialize(int size) { // 可以测试前配置。目前此功能没有激活。
        return container;
    }
    // 不公开构造器
    // 没有保护性拷贝,因为只是用来自己测试
    private Tester(C container, Map<String,Test<C>> tests) {
        this.container = container;
        this.tests = tests;
        header = container.getClass().getSimpleName();
    }
    // 静态工厂方法入口应该保证:
    //   参数数组至少有一组(2个)参数,而且数组长度为偶数。
    private Tester(C container, Map<String,Test<C>> tests, int[] paramList) {
        this(container,tests);
        assert paramList.length >= 2;
        assert paramList.length % 2 == 0;
        this.paramList = paramList;
    }

    /**
     * 公开静态工厂方法,方便运行测试
     */
    public static <C> void run(C cntnr, Map<String,Test<C>> tests) {
        new Tester<C>(cntnr,tests).timedTest();
    }
    public static <C> void run(C cntnr, Map<String,Test<C>> tests, int[] paramList) throws IllegalArgumentException {
        if (paramList.length < 2) {
            throw new IllegalArgumentException("Need at least 1 pair(test size and loop times) of paramater!");
        }
        if ( (paramList.length % 2) != 0 ) {
            throw new IllegalArgumentException("Parameters should be in pair!");
        }
        new Tester<C>(cntnr,tests,paramList).timedTest();
    }

    /**
     * 实际测试模块。
     * 调用每个Test的test()方法。
     */
     private static final String SIZE_FIELD = "%5d";
     private static final String RESULT_FIELD = "%10.10s: %10d";
     public void timedTest() { // paramList的长度已经检查过
         Formatter f = new Formatter(System.out);
         for (int i = 0; i < paramList.length/2; i++) {
             int size = paramList[i*2];
             int loops = paramList[i*2+1];
             f.format(SIZE_FIELD, size);
             for (Map.Entry<String,Test<C>> test : tests.entrySet()) {
                 C kontainer = initialize(size);
                 f.format(RESULT_FIELD, test.getKey(), eachTest(test.getValue(),kontainer,size,loops));
             }
             f.format("\n");
         }
     }
     // 为了和Test接口匹配
     private long eachTest(Test<C> test, C kontainer, int size, int loops) {
         assert size > 0;
         assert loops > 0;
         long result = 0;
         for (int i = 0; i < loops; i++) {
             result += test.test(kontainer, size);
         }
         return result / loops;
     }
}


AbstractTesterController.java

Tester工具类的控制器。使用模板模式的骨架实现。



package com.ciaoshen.thinkinjava.newchapter17;
import java.util.*;

// 使用了模板模式的骨架实现
abstract class AbstractTesterController<C> {
    /**
     * 抽象primitive method
     * 以下的骨架实现大部分依赖于testRegistry()方法返回的测试策略对象的注册表。
     */
    public abstract Map<String,Test<C>> testRegistry();
    /**
     * 向用户开放待测试容器类Class对象的注册
     * 所以ListTesterInBook不是不可变类
     */
    private final Set<String> containers = new LinkedHashSet<>(Arrays.asList(new String[]{"java.util.ArrayList","java.util.LinkedList"}));
    public Set<String> containerRegistry() { // 向用户暴露私有域对象的引用。不安全,但测试框架不是API的一部分,仅供包内使用。
        return containers;
    }
    /**
     * 主方法
     * 根据所有注册对象进行测试
     */
    public void run() {
        for (String name : containers) {
            C container = classForName(name);
            System.out.println(">>>>>>>>>>> " + name + " <<<<<<<<<<<");
            TesterInBook.run(container,testRegistry());
        }
    }
    public void run(int[] paramList) {
        for (String name : containers) {
            C container = classForName(name);
            System.out.println(">>>>>>>>>>> " + name + " <<<<<<<<<<<");
            TesterInBook.run(container,testRegistry(),paramList);
        }
    }
    /**
     * 利用反射,根据类型名称,构造容器实例。
     * 前提是容器基本都有无参数的构造函数。
     */
    @SuppressWarnings("unchecked")
    private C classForName(String name) {
        Class<?> klass = null;
        try {
            klass = Class.forName(name); // 获取Class对象
        } catch(ClassNotFoundException e) {
            System.err.println(name + " Class not found.");
            System.exit(1);
        }

        C object = null;
        try {
            object = (C) klass.newInstance(); //用newInstance()构造实例,赋值给接口
        } catch (IllegalAccessException e) {
            System.err.println(klass.getSimpleName() + " Class not accessible.");
            System.exit(1);
        } catch (InstantiationException e) {
            System.err.println(klass.getSimpleName() + " Class not instantiable.");
            System.exit(1);
        }
        return object;
    }
}


Generator.java

数据生成器接口。



package com.ciaoshen.thinkinjava.newchapter17;
import java.util.*;

// 无状态对象模拟函数指针(策略模式)
// 适合用匿名内部类的形式初始化
interface Generator<T> {
    public T next();
}


StringGenerator.java



package com.ciaoshen.thinkinjava.newchapter17;
import java.util.*;

final class StringGenerator implements Generator<String> {
    private static final int DEFAULT_LENGTH = 7;
    private static Generator<String> GEN = null;
    private final char[] UPPER = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
    private final char[] LOWER = "abcdefghijklmnopqrstuvwxyz".toCharArray();
    private final Random R = new Random();
    private final int STR_LENGTH;
    private StringGenerator(int size) { STR_LENGTH = size; }
    public static Generator<String> newInstance() { // pre-charge Singleton
        if (GEN == null) {
            GEN = new StringGenerator(DEFAULT_LENGTH);
        }
        return GEN;
    }
    public static Generator<String> newInstance(int size) { // the only public factory return Generator interface
        return new StringGenerator(size);
    }
    public String next() {
        StringBuilder sb = new StringBuilder();
        sb.append(UPPER[R.nextInt(UPPER.length)]);
        for (int i = 0; i < STR_LENGTH-1; i++) {
            sb.append(LOWER[R.nextInt(LOWER.length)]);
        }
        return sb.toString();
    }
}


Exercise35.java



package com.ciaoshen.thinkinjava.newchapter17;
import java.util.*;

final class Exercise35 {
    private static final class MapPerformance extends AbstractTesterController<Map<String,String>> {
        private final Generator<String> gen = StringGenerator.newInstance();
        private Map<String,String> randomFill(Map<String,String> map, int size) {
            for (int i = 0; i < size; i++) {
                map.put(gen.next(),gen.next());
            }
            return map;
        }
        public Map<String,Test<Map<String,String>>> testRegistry() {
            Map<String,Test<Map<String,String>>> tests = new HashMap<>();
            tests.put("Put", new Test<Map<String,String>>() {
                public long test(Map<String,String> map, int size) {
                    String str = gen.next();
                    long start = System.nanoTime();
                    for (int i = 0; i < size; i++) {
                        map.put(str,str);
                    }
                    long end = System.nanoTime();
                    return end - start;
                }
            });
            tests.put("Get", new Test<Map<String,String>>() {
                public long test(Map<String,String> map, int size) {
                    map = randomFill(map,size);
                    String str = gen.next();
                    long start = System.nanoTime();
                    for (int i = 0; i < size; i++) {
                        map.get(str);
                    }
                    long end = System.nanoTime();
                    return end - start;
                }
            });
            tests.put("Iterate", new Test<Map<String,String>>() {
                public long test(Map<String,String> map, int size) {
                    map = randomFill(map,size);
                    long start = System.nanoTime();
                    for (Map.Entry<String,String> entry : map.entrySet()) {
                        // do nothing
                    }
                    long end = System.nanoTime();
                    return end - start;
                }
            });
            return tests;
        }
        private static void test(String... args) {
            MapPerformance controller = new MapPerformance();
            controller.containerRegistry().clear();
            controller.containerRegistry().addAll(Arrays.asList(args));
            controller.run(new int[]{10,50,100,50,1000,25,10000,10});
        }
    }
    public static void main(String[] args) {
        MapPerformance.test("java.util.HashMap", "java.util.LinkedHashMap", "com.ciaoshen.thinkinjava.newchapter17.Exercise17$SlowMap");
    }
}


Exercise17.java

SlowMap类在练习17写过。



package com.ciaoshen.thinkinjava.newchapter17;
import java.util.*;

public class Exercise17 {
     public static class SlowMap<K,V> extends AbstractMap<K,V> {
        private List<K> keys = new ArrayList<K>();
        private List<V> values = new ArrayList<V>();
        public V put(K key, V value) {
            V oldValue = get(key); // The old value or null
            if(!keys.contains(key)) {
                keys.add(key);
                values.add(value);
            } else {
                values.set(keys.indexOf(key), value);
            }
            return oldValue;
        }
        public V get(Object key) { // key is type Object, not K
            if(!keys.contains(key)) {
                return null;
            }
            return values.get(keys.indexOf(key));
        }
        private class MapEntry implements Map.Entry<K,V> {
            private K key;
            private V value;
            public MapEntry() {}
            public MapEntry(K key, V value) {
                this.key = key;
                this.value = value;
            }
            public K getKey() { return key; }
            public V getValue() { return value; }
            public K setKey(K k) { // not included in interface Map.Entry
                K result = key;
                key = k;
                return result;
            }
            public V setValue(V v) {
                V result = value;
                value = v;
                return result;
            }
            public int hashCode() {
                return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode());
            }
            public boolean equals(Object o) {
                if(!(o instanceof Map.Entry)) {
                    return false;
                }
                @SuppressWarnings({"unckeked","rawtypes"})
                Map.Entry me = (Map.Entry)o;
                return (key == null ? me.getKey() == null : key.equals(me.getKey())) && (value == null ? me.getValue()== null : value.equals(me.getValue()));
            }
            public String toString() { return key + "=" + value; }
        }
        private class ViewSet extends AbstractSet<Map.Entry<K,V>> { // 明白为什么内部类是闭包了吗孩子? 外部类的数据随便用,连泛型都和外部类保持一致。其实闭包的名字起得很好!就是外部类的一个可选组件,不用的时候不初始化。
            public int size() {
                return keys.size();
            }
            public Iterator<Map.Entry<K,V>> iterator() {
                return new Iterator<Map.Entry<K,V>>() {
                    private int index = 0;
                    Iterator<K> iteKey = keys.iterator();
                    Iterator<V> iteValue = values.iterator();
                    MapEntry entry = new MapEntry();
                    public boolean hasNext() {
                        return iteKey.hasNext();
                    }
                    public Map.Entry<K,V> next() {
                        entry.setKey(iteKey.next());
                        entry.setValue(iteValue.next());
                        return entry;
                    }
                    // 这里是关键!
                    public void remove() { // AbstractMap的remove()方法,调用这个Set的Iterator的remove()方法,来删除元素。必须直接删除SlowMap的两个List里的元素。
                        iteKey.remove();
                        iteValue.remove();
                    }
                };
            }
        }
        public Set<Map.Entry<K,V>> entrySet() { // entrySet()要提供视图,而不是副本。
            return new ViewSet();
        }
    }
}



Need Java Developers? Hire Me »

I know Java. Talk is cheap, watch my code.

I live in CANADA now.