3.1.32

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

编码实现即可,实验结果如下:

对于保持键有序的 BinarySearchST 来说,逆序输入是最坏情况,顺序输入则是最好情况。
而对于键无序的 SequentialSearchST 来说,输入顺序对于性能的影响不大。
只有一种键的时候,每次 Put 都只需要比较一次,值一直在被替换。
只有两种值对性能的影响不大,性能主要由输入的键决定。

代码

测试方法,IST 代表一个符号表。

static void Test(IST<string, int>[] sts, int n)
{
    Stopwatch sw = new Stopwatch();
    string[] data = SearchCompare.GetRandomArrayString(n, 3, 10);
    string item1 = "item1";
    Array.Sort(data);

    // 有序的数组
    Console.Write("Sorted Array: ");
    sw.Start();
    for (int 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 (int 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 (int i = 0; i < n; i++)
    {
        sts[2].Put(item1, i);
    }
    sw.Stop();
    Console.WriteLine(sw.ElapsedMilliseconds);

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

另请参阅

SymbolTable 库

上一题 下一题