BinarySearchST计算成本的测试代码

---

下面是在原有BinarySearchST类上的修改，增加了两个成员（visitTimes与visitTime）和一个方法（getComparisionTimes），查找的成本主要体现在rank方法中的“cmp=key.compareTo(keys[m])”，在这一句后面加上visitTime++来标记访问次数增加了一次；写入的成本体现在put方法的两个位置，当key已经在keys中时，本次put的总成本是visitTime+1，当key不在keys数组中时（增加一个新元素），每移动一个元素，visitTime要加1，注意每次put操作记录结束后，除了要将次数存入visitTimes数组，还要将visitTime清零。

另外下面的代码省略了与原BinarySearchST类相同的成员和方法。

public class BinarySearchST, Value> { private final List visitTimes = new ArrayList(); // 每次put访问数组的次数的集合 int visitTime = 0; // 一次put操作中访问数组的次数计数器 public Value get(Key key) { if (isEmpty()) return null; int i = rank(key); visitTime++; if (i < N && keys[i].compareTo(key) == 0) return vals[i]; return null; } public int rank(Key key) { int lo = 0, hi = N - 1; while (lo <= hi) { int m = lo + (hi - lo) / 2; int cmp = key.compareTo(keys[m]); visitTime++; 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) { vals[i] = val; visitTimes.add(visitTime + 1); // 查找了visitTime次，写入的成本是1 visitTime = 0; 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]; visitTime++; } keys[i] = key; vals[i] = val; N++; visitTimes.add(visitTime); visitTime = 0; assert check(); } public List getComparisionTimes() { return visitTimes; } }

计算成本的图像演示代码FrequencyCounter类见笔记 SequentialSearchST算法成本的图形演示 。

---

---