SequentialSearchST算法成本的图形演示

---

中文版238页图3.1.3演示了SequentialSearchST算法中每次写入单词数量（put方法中）时需要进行的比较次数，也就是此算法的成本，但书中没有生成此图的代码，下面是我自己的实现（第一个是新增的类，后两个是修改的类）：

package edu.princeton.cs.algs4; public class VisualAccumulator { private double total; private int N; public VisualAccumulator(int trials, double max) { StdDraw.setXscale(0, trials); StdDraw.setYscale(0, max); StdDraw.setPenRadius(.005); } public void addDataValue(double val) { N++; total += val; StdDraw.setPenColor(StdDraw.DARK_GRAY); StdDraw.point(N, val); StdDraw.setPenColor(StdDraw.RED); StdDraw.point(N, total / N); StdOut.println("Red point value:" + total / N);// 平均比较次数 } public double mean() { return total / N; } @Override public String toString() { return "Mean (" + N + " values): " + String.format("%7.5f", mean()); } public static void main(String[] args) { int T = 300; VisualAccumulator a = new VisualAccumulator(T, 1.0); for (int t = 0; t < T; t++) { a.addDataValue(StdRandom.random()); } StdOut.println(a); } }

public class SequentialSearchST { private final List compareTimes = new ArrayList(); public List getComparisionTimes() { return compareTimes; } public void put(Key key, Value val) { int compareTime = 0; if (val == null) { compareTimes.add(1); delete(key); return; } for (Node x = first; x != null; x = x.next) { compareTime++; if (key.equals(x.key)) { x.val = val; compareTimes.add(compareTime); return; } } first = new Node(key, val, first); N++; compareTimes.add(compareTime); } public static void main(String[] args) { StdIn2.setInputFile("data/tale.txt"); SequentialSearchST st = new SequentialSearchST(); for (int i = 0; !StdIn2.isEmpty(); i++) { String key = StdIn2.readString(); st.put(key, i); } List comparisionTimes = st.getComparisionTimes(); VisualAccumulator va = new VisualAccumulator(comparisionTimes.size(), 1.0); for (int t = 0; t < comparisionTimes.size(); t++) { va.addDataValue(comparisionTimes.get(t)); } for (String s : st.keys()) StdOut.println(s + " " + st.get(s)); } }

public class FrequencyCounter { public static void main(String[] args) { StdIn2.setInputFile("data/tale.txt"); int distinct = 0, words = 0; int minlen = 8; // this is the first parameter SequentialSearchST st = new SequentialSearchST(); while (!StdIn2.isEmpty()) { String key = StdIn2.readString(); if (key.length() < minlen) continue; words++; if (st.contains(key)) { st.put(key, st.get(key) + 1); } else { st.put(key, 1); distinct++; } } String max = ""; st.put(max, 0); for (String word : st.keys()) { if (st.get(word) > st.get(max)) max = word; } StdOut.println(max + " " + st.get(max)); StdOut.println("distinct = " + distinct); StdOut.println("words = " + words); // 以上是原始版本的代码，修改了获取输入的方法 List comparisionTimes = st.getComparisionTimes(); // 获取原始成本数据 int maxComp = 0; for (Integer i : comparisionTimes) { if (i > maxComp) { maxComp = i; } } // 获得原始成本最大值，以确定画布的Y轴高度 VisualAccumulator va = new VisualAccumulator(comparisionTimes.size(), maxComp); for (int t = 0; t < comparisionTimes.size(); t++) { va.addDataValue(comparisionTimes.get(t)); } // 画图 } }

以上VisualAccumulator是完整的类，SequentialSearchST只写出了新增的属性compareTimes及其get方法，和修改后的put和main方法；FrequencyCounter类中修改后的main方法，

---

---