---

本文在笔记 BinarySearchST计算成本的测试代码 的基础上，尝试将成本计算和图像演示等功能封装在一个单独的类中，尽量降低对被测试类的改动。

测试方法

1. 在被测类中增加一个成员及其getter；

2. 在FrequencyCounter类中增加：st.getVisitTimes().drawCostCurve();

两个实例

BinarySearchST

public class BinarySearchST, Value> { private final VisitTimeCounter vtc = new VisitTimeCounter(); public VisitTimeCounter getVisitTimes() { return vtc; } public int rank(Key key) { int lo = 0, hi = N - 1; while (lo <= hi) { int m = lo + (hi - lo) / 2; vtc.addVisitTimes(); int cmp = key.compareTo(keys[m]); if (cmp < 0) hi = m - 1; else if (cmp > 0) lo = m + 1; else return m; } return lo; } public void put(Key key, Value val) { if (val == null) { delete(key); return; } int i = rank(key); if (i < N && keys[i].compareTo(key) == 0) { vtc.putComplete(); vals[i] = val; return; } if (N == keys.length) resize(2 * keys.length); for (int j = N; j > i; j--) { keys[j] = keys[j - 1]; vals[j] = vals[j - 1]; vtc.addVisitTimes(); } keys[i] = key; vals[i] = val; N++; vtc.putComplete(); assert check(); } }

对原版BinarySearchST类的修改包括增加了一个成员（vtc）和它的getter，在rank和put中各加了一个vtc.addVisitTimes()表示查询和插入操作中对数组的访问，以及put中两处vtc.putComplete()，表示在命中和未命中两种情况下将本次put的访问次数存入数组记录中。

下面是VisitTimeCounter类：

public class VisitTimeCounter { private int visitTimesInsidePut = 0; // 一次put操作当中的数组访问次数 private final List visitTimesInAllPut = new ArrayList(); // 各次put的访问次数汇总保存在这里 public void addVisitTimes() { visitTimesInsidePut++; } public void putComplete() { visitTimesInAllPut.add(visitTimesInsidePut); visitTimesInsidePut = 0; } public void drawCostCurve() { int maxComp = 0; for (Integer i : visitTimesInAllPut) { if (i > maxComp) { maxComp = i; } } StdOut.println("matrix scale: " + visitTimesInAllPut.size() + ", " + maxComp); VisualAccumulator va = new VisualAccumulator(visitTimesInAllPut.size(), maxComp); for (int t = 0; t < visitTimesInAllPut.size(); t++) { va.addDataValue(visitTimesInAllPut.get(t)); } } }

FrequencyCounter类中演示成本只需要一条语句：

BinarySearchST st = new BinarySearchST(); // copy from original codes

st.getVisitTimes().drawCostCurve();

BST

即二叉查找树（binary search tree），原版代码见algs4-package.jar的BST.java类。

public class BST, Value> { private final VisitTimeCounter vtc = new VisitTimeCounter(); public VisitTimeCounter getVisitTimes() { return vtc; } public void put(Key key, Value val) { if (val == null) { delete(key); return; } root = put(root, key, val); vtc.putComplete(); assert check(); } private Node put(Node x, Key key, Value val) { if (x == null) return new Node(key, val, 1); int cmp = key.compareTo(x.key); vtc.addVisitTimes(); if (cmp < 0) x.left = put(x.left, key, val); else if (cmp > 0) x.right = put(x.right, key, val); else x.val = val; x.N = 1 + size(x.left) + size(x.right); return x; } private int rank(Key key, Node x) { if (x == null) return 0; int cmp = key.compareTo(x.key); vtc.addVisitTimes(); if (cmp < 0) return rank(key, x.left); else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right); else return size(x.left); } }

查找成本体现在rank方法中，插入时每次访问的记录体现在private Node put方法中，总次数的记录体现在public void put方法中。

---

---