3.1.36

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

解答

实验结果如下,增长级为 O(N) ,但速度很快。

其实只要列出《双城记》不同长度的单词数目,原因就一目了然了。

大部分单词都集中在中间长度,因此大部分访问也集中在数组中部。
二分查找在访问数组中部的元素时速度很快,因此结果好于预期。

代码

static void Main(string[] args)
{
    int n = 8000;
    int multiplyBy2 = 5;
    int repeatTimes = 5;
    double lastTime = -1;
    Console.WriteLine("n\ttime\tratio");
    for (int i = 0; i < multiplyBy2; i++)
    {
        Console.Write(n + "\t");
        long timeSum = 0;
        for (int j = 0; j < repeatTimes; j++)
        {
            BinarySearchST<string, int> st = new BinarySearchST<string, int>();
            Stopwatch sw = Stopwatch.StartNew();
            FrequencyCounter.MostFrequentlyWord("tale.txt", n, 0, st);
            sw.Stop();
            timeSum += sw.ElapsedMilliseconds;
        }
        timeSum /= repeatTimes;
        Console.Write(timeSum + "\t");
        if (lastTime < 0)
            Console.WriteLine("--");
        else
            Console.WriteLine(timeSum / lastTime);
        lastTime = timeSum;
        n *= 2;
    }
}

另请参阅

SymbolTable 库

上一题 下一题