2019-3-7
3.1.31 # 解答 # 性能测试方法构造如下：
先编写一个随机字符串方法，生成一个长度大于 50 的字符串（作为未命中访问）。
然后随机生成符合要求的字符串数组，将它们全部放入符号表中。
然后遍历 10 次生成的字符串数组，对于数组中的每个元素都进行一次命中查询。
同时在每次命中查询的同时都进行一次未命中查询即可。
测试结果：
代码 # 按照要求编写代码，在 SearchCompare 类里添加一个 Random random 成员，并添加如下方法： 随机字符串发生器：
public static string GetRandomString(int minLength, int maxLength) { var length = Random.Next(minLength, maxLength); var sb = new StringBuilder(); for (var i = 0; i < length; i++) { var choice = Random.NextDouble(); if (choice < 0.333) sb.Append((char)Random.Next('A', 'Z')); else if (choice < 0.666) sb.Append((char)Random.Next('a', 'z')); else sb.
...
2019-3-8
3.1.32 # 解答 # 编码实现即可，实验结果如下：
对于保持键有序的 BinarySearchST 来说，逆序输入是最坏情况，顺序输入则是最好情况。
而对于键无序的 SequentialSearchST 来说，输入顺序对于性能的影响不大。
只有一种键的时候，每次 Put 都只需要比较一次，值一直在被替换。
只有两种值对性能的影响不大，性能主要由输入的键决定。
代码 # 测试方法，IST 代表一个符号表。
static void Test(ISt<string, int>[] sts, int n) { var sw = new Stopwatch(); var data = SearchCompare.GetRandomArrayString(n, 3, 10); var item1 = "item1"; Array.Sort(data); // 有序的数组 Console.Write("Sorted Array: "); sw.Start(); for (var i = 0; i < n; i++) { sts[0].Put(data[i], i); } sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds); // 逆序的数组 Console.Write("Sorted Array Reversed: "); sw.
...
2019-3-9
3.1.33 # 解答 # 概率分布的实现方式：
假设存有键的数组为 keys，对 keys 排序。
然后再建立一个长度为 10N 的数组 querys，
前 1/2 置为 keys[0]，1/2 到 3/4 置为 keys[1]，以此类推，直到数组填满。
然后遍历 query 数组，对符号表进行 Get() 操作。
实验结果如下：
代码 # var n = 1000; var multiplyBy10 = 4; for (var i = 0; i < multiplyBy10; i++) { Console.WriteLine("n=" + n); // 构造表 var bst = new BinarySearchSt<string, int>(n); var mst = new MoveToFrontArraySt<string, int>(n); var keys = SearchCompare.GetRandomArrayString(n, 3, 20); for (var j = 0; j < n; j++) { bst.
...
2019-3-10
3.1.34 # 解答 # 在上一题的基础上进行修改即可。
调和级数 $H_n = 1+\frac{1}{2}+\frac{1}{3} + \cdots+\frac{1}{n}$ 。
查询数组变为前 1/2 为 key[0]，随后的 1/3 为 key[1]，以此类推。
和上一题中的序列进行比较即可，注意删除最后的打乱步骤。
实验结果如下：
代码 # 首先建立一个数组计算调和级数，就像这样：
// 调和级数 var harmonicNumber = new double[n * (int)Math.Pow(10, multiplyBy10)]; harmonicNumber[0] = 1; for (var i = 1; i < harmonicNumber.Length; i++) { harmonicNumber[i] = harmonicNumber[i - 1] + 1 / (i + 1); } 然后修改构造查询的代码：
// 构造查询 Array.Sort(keys); var queryZipf = new string[10 * n]; int queryIndex = 0, keyIndex = 0; while (queryIndex < queryZipf.
...
2019-3-10
3.1.35 # 解答 # 实验结果：
由于包含重复单词，因此结果会比 4 略低一些。
需要对 FrequencyCounter 做一些修改，令其只取前 n 个单词。
代码 # var n = 8000; var multiplyBy2 = 5; var repeatTimes = 5; double lastTime = -1; Console.WriteLine("n\ttime\tratio"); for (var i = 0; i < multiplyBy2; i++) { Console.Write(n + "\t"); long timeSum = 0; for (var j = 0; j < repeatTimes; j++) { var st = new SequentialSearchSt<string, int>(); var sw = Stopwatch.StartNew(); FrequencyCounter.
...
2019-3-10
3.1.36 # 解答 # 实验结果如下，增长级为 O(N) ，但速度很快。 其实只要列出《双城记》不同长度的单词数目，原因就一目了然了。 大部分单词都集中在中间长度，因此大部分访问也集中在数组中部。
二分查找在访问数组中部的元素时速度很快，因此结果好于预期。
代码 # var n = 8000; var multiplyBy2 = 5; var repeatTimes = 5; double lastTime = -1; Console.WriteLine("n\ttime\tratio"); for (var i = 0; i < multiplyBy2; i++) { Console.Write(n + "\t"); long timeSum = 0; for (var j = 0; j < repeatTimes; j++) { var st = new BinarySearchSt<string, int>(); var sw = Stopwatch.StartNew(); FrequencyCounter.MostFrequentlyWord("tale.txt", n, 0, st); sw.
...
2019-3-10
3.1.37 # 解答 # 实验结果如下：
M=10 的时候随机的数字集中在 1024 到 2048 之间，重复值较多，因此 Put 耗时较少。
随着重复值的减少 Put 的耗时会大幅度提高，和实验结果显示的一样。
M=20 的时候数字在 1048576~2097152 之间随机，基本上没有重复值了。
M=30 的时候和 M=20 的情况类似，都是重复值几乎没有的情况。
随机数可以通过如下的方式产生：
result[i] = min + (long)(random.NextDouble() * (max - min)); 代码 # 这里构造了 BinarySearchSTAnalysis 类，在类中声明了两个 Stopwatch 对象，
一个在 Put 方法的开始和结束部分进行计时，
另一个在 Get 方法的开始和结束部分进行计时。
var n = 1000000; var m = 10; var addBy10 = 3; for (var i = 0; i < addBy10; i++) { var bst = new BinarySearchStAnalysis<long, int>(n); var data = SearchCompare.
...
2019-3-18
3.1.38 # 解答 # 实验结果如下：
BinarySearchST SequentialSearchST 对于 BinarySearchST ，每次比较之后以及移动元素时令 Cost 增加。
对于 SequentialSearchST，统计每次的查找次数即可。 然后绘制成散点图即可。
代码 # 有关绘图的函数，传入的参数为第 i 次 Put() 的开销。
public void Draw(int[] data) { Graphics panel = this.CreateGraphics(); float unitX = (float)this.ClientRectangle.Width / data.Length; float unitY = (float)this.ClientRectangle.Height / data.Max(); int accumulation = 0; for (int i = 0; i < data.Length; i++) { // Gray panel.FillEllipse(Brushes.Gray, (i + 1) * unitX, this.ClientRectangle.Bottom - data[i] * unitY, 2, 2); // Red panel.
...
2019-3-19
3.1.39 # 解答 # 实验结果如下：
BinarySearchST SequentialSearchST 图像分为两段，分别代表不断向符号表中加入单词和寻找频率最大的单词两个部分。
第一段两个图像的形状类似（注意它们的 y 轴比例不同）。
第二段中 BinarySearchST 的表现要比 SequentialSearchST 稳定的多。
代码 # 绘图部分代码：
public void Draw(int[] x, long[] y) { Graphics panel = this.CreateGraphics(); float unitX = (float)this.ClientRectangle.Width / x.Max(); float unitY = (float)this.ClientRectangle.Height / y.Max(); for (int i = 0; i < x.Length; i++) { panel.FillEllipse( Brushes.Black, x[i] * unitX, this.ClientRectangle.Height - y[i] * unitY, 2, 2); } } 另请参阅 # SymbolTable 库
2019-3-24
3.1.40 # 解答 # 顺序查找平均需要进行 $N/2$ 次比较，二分查找则是 $\lg N$ 次。
列出方程可以解出 N 的大小
$$ \begin {eqnarray*} 1000 \log_2 N &=& N / 2 \newline \log_2 N &=& N / 2000\newline \frac{\ln N}{\ln 2} &=& N/2000 \newline N &=& e^{\frac{\ln 2}{2000}N}\newline 1 &=& Ne^{-\frac{\ln 2}{2000}N}\newline N_1 = e^{-W(-\frac{\ln 2}{2000})}=1 &\ & N_2= e^{-W_{-1}(-\frac{\ln 2}{2000})}=29718\newline \newline \end {eqnarray*} $$
这个方程是一个超越方程，最后的结果中出现了朗伯 W 函数。
同理可以求得 10000 倍的 N=369939。
实验结果如下：
由于存在缓存优化，每次比较的耗时并不相同。
因此实际耗时并未达到预期，但比较次数是符合预期的。
另请参阅 # 朗伯 W 函数-维基百科