目前我們已經涉及了五種不同的緩存實現（SimpleKeyCache、PrefixTreeCache、SortedListCache、HashedListCache和DictionaryCache），如果要從一個已經包含n個表達式樹的存儲中，查找一個有m個節點的表達式樹，根據幾篇文章的分析，從理論上說除了HashedListCache的時間復雜度是O(m * log(n))之外，其它幾種實現的時間復雜度都是O(m)。不過，理論上的結果和實際使用中的效果完全符合嗎？那么我們就寫一個程序，讓數據說話。這是一個控制臺應用程序，接受用戶參數，并由此生成試驗數據，或進行性能比較。

開始還債，因為還有至少兩個可寫的重要話題依賴在這個系列上，不解決就難以前進。

目前我們已經涉及了五種不同的緩存實現，它們分別是：

1. SimpleKeyCache：構造字符串作為Key，使用字典作為存儲。
2. PrefixTreeCache：使用前綴樹進行存儲。
3. SortedListCache：使用排序列表或二叉搜索樹進行存儲。
4. HashedListCache：先對表達式樹取散列值，再從字典中取出二叉搜索樹。
5. DictionaryCache：實現了散列值和表達式樹的比較方法，直接使用字典進行存儲。

如果要從一個已經包含n個表達式樹的存儲中，查找一個有m個節點的表達式樹，根據幾篇文章的分析，從理論上說除了HashedListCache的時間復雜度是O(m * log(n))之外，其它幾種實現的時間復雜度都是O(m)。不過，理論上的結果和實際使用中的效果完全符合嗎？如果完全符合的話，那么我們在構建第一個SimpleKeyCache，獲得了一種既簡單直觀又“高效”（達到了理論上最好的時間復雜度O(m)）的實現之后為什么還要繼續設計剩下的方案呢？如果您看完了文章還沒有想到，這說明您的.NET編程“常識”還需要加強。

那么我們就寫一個程序，讓數據說話。

這是一個控制臺應用程序，接受用戶參數，并由此生成試驗數據，或進行性能比較。

生成試驗數據

需要進行測試，自然要準備試驗數據，而這里所需要的試驗數據自然是大量的表達式樹。

表達式樹的種類非常紛繁，如果要構造各種類型的樹，其代價也是非常昂貴的。因此在這里，我們只構建所謂的“整數的四則運算”表達式進行試驗。對于這樣的表達式，每個運算符占用一個節點，每個數字又會占用另一個節點，因此表達式數的節點個數m便是操作符的個數p，與數字的個數q之和。而由于每個元算符都是二元運算符，因此p等于q - 1。于是我們就可以得出m與p之間的關系：

m = 2p + 1

知道了這個關系，我們便可以獲得一定規模的試驗數據。于是我們寫一個簡單的小程序來隨機輸出一個表達式：

private static void WriteSingleExpression(
    TextWriter writer, Random random, int opCount)
{
    string ops = "+-*/";

    writer.Write(random.Next(100));
    while (opCount-- > 0)
    {
        writer.Write(" ");
        writer.Write(ops[random.Next(4)]);
        writer.Write(" ");
        writer.Write(random.Next(100));
    }
    writer.WriteLine();
}

這個方法的目的是向TextWriter中隨機輸出一個擁有opCount個運算符的表達式（可以得知，這個表達式樹有m = 2 * opCount + 1個節點）。例如，當opCount等于11的時候，它可能就會生成這樣一個表達式：

82 / 6 - 76 * 75 - 33 / 32 * 56 + 47 + 3 + 22 * 5 + 63

然后我們獲取用戶參數輸入，并輸出一系列隨機的表達式：

private static void GenerateExpressions(NameValueCollection args)
{
    string output = args["out"] ?? "expressions.txt";
    int min = Int32.Parse(args["min"] ?? "11");
    int max = Int32.Parse(args["max"] ?? (min + 9).ToString());
    int repeat = Int32.Parse(args["repeat"] ?? "100");

以上代碼的目的是獲取用戶參數，用戶輸入的參數將被解析為NameValueCollection，參數含義如下：

• output：輸出文件
• min：最短表達式中的運算符數量
• max：最長表達式中的運算符數量
• repeat：每種長度的表達式重復次數

向文件輸出所有的隨機表達式便不是難事了：

    Random random = new Random(DateTime.Now.Millisecond);
    using (var stream = File.Open(output, FileMode.Create))
    {
        StreamWriter writer = new StreamWriter(stream);
        for (int opCount = min; opCount <= max; opCount++)
        {
            for (int i = 0; i < repeat; i++)
            {
                WriteSingleExpression(writer, random, opCount);
            }
        }
    }
}

代碼簡單，就不多作分析了。

試驗代碼

首先，自然是獲取用戶輸入參數，方法同上：

static void PerfTest(NameValueCollection args)
{
    string intput = args["in"] ?? "expressions.txt";
    int repeat = Int32.Parse(args["repeat"] ?? "100");

現在便要讀入表達式了。解析表達式不是一件容易的事情，我們這里使用ScottGu所提過的Dynamic Query Library，解析一個表達式就再容易不過了：

    List<Expression> expressions = File.ReadAllLines(intput).Select(
        s => DynamicExpression.Parse(null, s)).ToList();

接著，準備5種緩存容器：

    var caches = new SortedDictionary<string, IExpressionCache<object>>()
    {
        { "1. SimpleKeyCache", new SimpleKeyCache<object>() },
        { "2. PrefixTreeCache", new PrefixTreeCache<object>() },
        { "3. SortedListCache", new SortedListCache<object>() },
        { "4. HashedListCache", new HashedListCache<object>() },
        { "5. DictionaryCache", new DictionaryCache<object>() },
    };

初始化CodeTimer：

    CodeTimer.Initialize();

遍歷字典中的每個緩存對象，將其放入緩存容器中。這段代碼還有一個作用便是“熱身”——請注意，對.NET中任意代碼作性能測試時，都需要讓它預運行一下。由于JIT的存在，一個方法第一次運行時所花時間總是較長的，這不應該統計在內：

    var value = new object();
    foreach (var pair in caches)
    {
        var cache = pair.Value;
        expressions.ForEach(exp => cache.Get(exp, (_) => value));

最后，則是使用CodeTimer對當前緩存容器進行性能測試：

        CodeTimer.Time(pair.Key, repeat,
            () => expressions.ForEach(exp => cache.Get(exp, null)));
    }
}

PerfTest編寫完畢，我們最后還需要指定一個函數的入口，如下：

static void Main(string[] args)
{
    var arguments = ParseArguments(args);

    if (arguments["task"] == "test")
    {
        PerfTest(arguments);
    }
    else
    {
        GenerateExpressions(arguments);
    }
}

如果直接執行程序，便會創建一個expression.txt文件，其中包括操作符數量在11到20之間，每種表達式各100個。如果加上了task參數，并指定test字符串，便會進行性能比較。

比較結果

輸入命令，便會使用expression.txt中的每個表達式各調用100次：

Benchmark.exe /task:test

對于運算符數量為11到20的表達式各100個（即總共1000個表達式），各調用100次的結果如下（不過，請不要直接看結果，再想想，再想想）：

1. SimpleKeyCache
        Time Elapsed:   2,807ms
        CPU Cycles:     7,090,489,283
        Gen 0:          412
        Gen 1:          0
        Gen 2:          0

2. PrefixTreeCache
        Time Elapsed:   2,391ms
        CPU Cycles:     6,039,211,085
        Gen 0:          142
        Gen 1:          0
        Gen 2:          0

3. SortedListCache
        Time Elapsed:   1,939ms
        CPU Cycles:     4,903,538,425
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

4. HashedListCache
        Time Elapsed:   1,237ms
        CPU Cycles:     3,129,685,287
        Gen 0:          0
        Gen 1:          0
        Gen 2:          0

5. DictionaryCache
        Time Elapsed:   1,219ms
        CPU Cycles:     3,076,107,042
        Gen 0:          3
        Gen 1:          1
        Gen 2:          0

結果和您想象的是否一樣？在老趙的機器上，這個結果還是相當穩定的，每次測試只差十幾毫秒，而垃圾收集次數則完全一樣。從這個數據中您看出什么來了嗎？或者說，您能否回答以下幾個問題呢？

1. SimpleKeyCache的垃圾收集次數為什么明顯較多？PrefixTreeCache為什么也有不少垃圾收集？
2. SimpleKeyCache和PrefixTreeCache的時間復雜度都是理論最優值O(m)，但是為什么它們卻比不過SortedListCache這個理論上時間復雜度是O(m * log(n))的容器呢？
3. 您能否設定一種用例，讓SortedListCache的耗時超過PrefixTreeCache或SimpleKeyCache呢？
4. HashedListCache為什么會超過SortedListCache，DictionaryCache的性能為什么也那么好呢（與HashedListCache不分伯仲，多次測試互有“勝負”）？
5. DictionaryCache有一次1代的垃圾收集，這說明DictionaryCache消耗內存超過前些容器嗎？
6. SimpleKeyCache從時間和空間上看全面落后，那么他有什么好處嗎？
7. 您能為每種容器提出改進意見嗎？

您是否還能提出更多問題？您能夠在老趙發布下一篇文章討論這些問題之前，在這里留言給出您對這些問題的看法呢？

 

完整代碼下載：http://code.msdn.microsoft.com/ExpressionCache

相關文章：

• 談表達式樹的緩存（1）：引言
• 談表達式樹的緩存（2）：由表達式樹生成字符串
• 談表達式樹的緩存（3）：使用前綴樹
• 談表達式樹的緩存（4）：使用二叉搜索樹（AVL樹）
• 談表達式樹的緩存（5）：引入散列值
• 談表達式樹的緩存（7）：五種緩存方式的總體分析及改進方案