3.1.33

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

解答

概率分布的实现方式:
假设存有键的数组为 keys,对 keys 排序。
然后再建立一个长度为 10N 的数组 querys
前 1/2 置为 keys[0],1/2 到 3/4 置为 keys[1],以此类推,直到数组填满。
然后遍历 query 数组,对符号表进行 Get() 操作。

实验结果如下:

代码

static void Main(string[] args)
{
    int n = 1000;
    int multiplyBy10 = 3;
    for (int i = 0; i < multiplyBy10; i++)
    {
        Console.WriteLine("n=" + n);
        // 构造表
        BinarySearchST<string, int> bst = new BinarySearchST<string, int>(n);
        MoveToFrontArrayST<string, int> mst = new MoveToFrontArrayST<string, int>(n);
        string[] keys = SearchCompare.GetRandomArrayString(n, 3, 20);
        for (int j = 0; j < n; j++)
        {
            bst.Put(keys[j], j);
            mst.Put(keys[j], j);
        }
        // 构造查询
        Array.Sort(keys);
        string[] querys = new string[10 * n];
        int queryIndex = 0, keyIndex = 0;
        while (queryIndex < querys.Length)
        {
            int searchTimes = (int)Math.Ceiling((Math.Pow(0.5, keyIndex + 1) * querys.Length));

            for (int j = 0; j < searchTimes && queryIndex < querys.Length; j++)
            {
                querys[queryIndex++] = keys[keyIndex];
            }
            keyIndex++;
        }
        Shuffle(querys);

        Stopwatch sw = new Stopwatch();
        // 测试 MoveToFrontArrayST
        sw.Start();
        for (int j = 0; j < querys.Length; j++)
        {
            mst.Get(querys[j]);
        }
        sw.Stop();
        Console.WriteLine("MoveToFrontArrayST: " + sw.ElapsedMilliseconds);

        // 测试 BinarySearchST
        sw.Restart();
        for (int j = 0; j < querys.Length; j++)
        {
            bst.Get(querys[j]);
        }
        sw.Stop();
        Console.WriteLine("BinarySearchST: " + sw.ElapsedMilliseconds);

        n *= 10;
    }
}

static void Shuffle<T>(T[] data)
{
    for (int i = 0; i < data.Length; i++)
    {
        int r = i + random.Next(data.Length - i);
        T temp = data[r];
        data[r] = data[i];
        data[i] = temp;
    }
}

另请参阅

SymbolTable 库

上一题 下一题