3.1.32

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.Restart();
    for (var i = n - 1; i >= 0; i--)
    {
        sts[1].Put(data[i], i);
    }

    sw.Stop();
    Console.WriteLine(sw.ElapsedMilliseconds);

    // 只有一种键
    Console.Write("One Distinct Key: ");
    sw.Restart();
    for (var i = 0; i < n; i++)
    {
        sts[2].Put(item1, i);
    }

    sw.Stop();
    Console.WriteLine(sw.ElapsedMilliseconds);

    // 只有两种值
    Console.Write("Two Distinct Values: ");
    sw.Restart();
    for (var i = 0; i < n; i++)
    {
        sts[3].Put(data[i], i % 2);
    }

    sw.Stop();
    Console.WriteLine(sw.ElapsedMilliseconds);
}

另请参阅 #

SymbolTable 库