3.1.37

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.GetRandomArrayLong(n, (long)Math.Pow(2, m), (long)Math.Pow(2, m + 1));
    FrequencyCounter.MostFrequentlyKey(bst, data);
    Console.WriteLine(
        "m="
        + m
        + "\t"
        + bst.GetTimer.ElapsedMilliseconds
        + "\t"
        + bst.PutTimer.ElapsedMilliseconds
        + "\t"
        + bst.PutTimer.ElapsedMilliseconds / (double)bst.GetTimer.ElapsedMilliseconds);
    m += 10;
}

var st = new BinarySearchStAnalysis<string, int>();
FrequencyCounter.MostFrequentlyWord("tale.txt", 0, st);
Console.WriteLine(
    "tales\t"
    + st.GetTimer.ElapsedMilliseconds
    + "\t"
    + st.PutTimer.ElapsedMilliseconds
    + "\t"
    + st.PutTimer.ElapsedMilliseconds / (double)st.GetTimer.ElapsedMilliseconds);
Console.ReadLine();

另请参阅 #

SymbolTable 库