3.1.33

3.1.33 #

解答 #

概率分布的实现方式：

假设存有键的数组为 keys，对 keys 排序。

然后再建立一个长度为 10N 的数组 querys，

前 1/2 置为 keys[0]，1/2 到 3/4 置为 keys[1]，以此类推，直到数组填满。

然后遍历 query 数组，对符号表进行 Get() 操作。

实验结果如下：

代码 #

var n = 1000;
var multiplyBy10 = 4;
for (var i = 0; i < multiplyBy10; i++)
{
    Console.WriteLine("n=" + n);
    // 构造表
    var bst = new BinarySearchSt<string, int>(n);
    var mst = new MoveToFrontArraySt<string, int>(n);
    var keys = SearchCompare.GetRandomArrayString(n, 3, 20);
    for (var j = 0; j < n; j++)
    {
        bst.Put(keys[j], j);
        mst.Put(keys[j], j);
    }

    // 构造查询
    Array.Sort(keys);
    var querys = new string[10 * n];
    int queryIndex = 0, keyIndex = 0;
    while (queryIndex < querys.Length)
    {
        var searchTimes = (int)Math.Ceiling((Math.Pow(0.5, keyIndex + 1) * querys.Length));

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

        keyIndex++;
    }

    Shuffle(querys);

    var sw = new Stopwatch();
    // 测试 MoveToFrontArrayST
    sw.Start();
    for (var j = 0; j < querys.Length; j++)
    {
        mst.Get(querys[j]);
    }

    sw.Stop();
    Console.WriteLine("MoveToFrontArrayST: " + sw.ElapsedMilliseconds);

    // 测试 BinarySearchST
    sw.Restart();
    for (var 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 (var i = 0; i < data.Length; i++)
    {
        var r = i + new Random().Next(data.Length - i);
        var temp = data[r];
        data[r] = data[i];
        data[i] = temp;
    }
}

另请参阅 #

SymbolTable 库