時間測試
因為這本書采用了一種實踐的方法進行對要研究數據結構及算法進行分析，我們避開使用大O分析，寧願使用運行簡單的基准測試的方法來代替。這個測試將告訴我們運行一個代碼段花費了多少秒（或其它時間單位），我們的基准測試時時間測試，衡量運行完成一個算法所花費的時間。基准測試是一門科學更是一門藝術而且你必須小心你對一段代碼計時的方式以獲得一個正確的分析結果。讓我們更詳細的了解一下。
一個太簡單化的時間測試
首先，我們需要一些代碼來及時。為了簡單的說明問題，我們先對一個將一個數組的內容輸出到控制台的子程序來計時。下面是代碼：
static void DisplayNums(int[] arr)
{
for (int i = 0; i <= arr.GetUpperBound(0); i++)
Console.Write(arr[i] + " ");
}
這個數組在程序的另一部分初始化，這個我們將在稍後研究。要對這個子函數計時，我們需要創建一個變量，並把子函數被調用時的系統時間賦給這個變量，另外我們需要存儲一個子函數返回時的時間。如下是我們實現這些功能的方法：
DateTime startTime;
TimeSpan endTime;
startTime = DateTime.Now;
endTime = DateTime.Now.Subtract(startTime);
在我的筆記本電腦（1.4mHz運行Windows XP專業版）上運行這段代碼，這個子程序運行了大約5秒鐘（4.9917秒）。雖然看起來這段代碼適合執行一個耗時測試，但對於計算.Net環境下代碼的運行是完全不夠的。為什麼呢？
首先，這段代碼測試了由子函數被調用直到子函數返回到主程序的耗時。與C#程序同時運行的其它進程占用的時間也記到了時間測試的結果中。
其次，這些計時代碼沒有考慮.Net環境執行垃圾回收的時間。在如.Net這種運行環境中，系統可能在任何時間暫停來執行垃圾回收。這種簡單的代碼沒有做任何處理來承認垃圾回收的存在且計時結果很容易受到垃圾回收的影響。所以我們應該怎樣處理這種問題呢？
.Net環境下的耗時測試
在.Net環境中，我們需要考慮我們的程序所運行的線程及任何時候垃圾回收都可能發生的事實。我們需要在設計我們的計時代碼時將這些因素考慮在內。
讓我們先來看一下怎樣控制垃圾回收。首先，我們討論一下垃圾回收的作用。在C#中，引用類型（如字符串，數組及類的實例對象）的內存空間是在被稱作堆的空間中分配的。堆是一片用來保存數據項（之前提到的類型）的內存空間。值類型，如普通的變量，被存儲在棧上。到引用類型數據的引用也是存儲在棧上，但是引用類型中實際存儲的數據被保存在棧中。
存儲在棧上的變量當聲明它的子程序執行完成時被釋放。另一方面，存儲在托管堆上的變量一直存在堆中直到垃圾回收過程被調用。堆數據只有在沒有對它的動態引用時通過垃圾回收被移除。
垃圾回收可以並且將會發生在程序執行的任意時刻。然而，我們要盡我們可能的確保垃圾回收器在我們計時代碼執行的過程中不運行。我們可以通過強制調用垃圾回收器來阻止任意執行的垃圾回收。.Net環境中提供了與個特殊的對象 – GC供調用垃圾回收使用。要通知系統執行垃圾回收。我們簡單的寫：
GC.Collect();
然而，這不是全部我們必須做的。存儲在堆中的每一個對象有一個成為終結器的特殊方法。終結器方法在對象被刪除前的最後一步執行。終結器方法存在的問題是它們不以一種規律的方式執行。事實上，你甚至根本不能確定一個對象的終結器是否已經運行了。但是我們知道，在我們確定一個對象被刪除之前，它的終結器方法一定會運行。要確保這一點，我們添加一行代碼來告訴程序等待所有堆上的對象的終結器方法運行後再繼續執行。這行代碼如下：
GC.WaitForPendingFinalizers();
我們已經清除了一個障礙並且只剩一個待解決 – 使用適當的線程。在.Net環境中，一個程序運行在一個線程中，也被稱作應用程序域。這允許操作系統將每一個不同的程序分開在其上同時運行。在一個進程中，程序或者程序的一部分在一個線程內運行。一個程序的執行時間被操作系統通過線程進行分配。當我們為一個程序的代碼計時時，我們想要確保我們計的時間只是進程分配給我的程序的代碼所占用的時間，而不是操作系統執行的其他任務的時間。
我們可以使用.NET類庫中的Process類來實現這個功能。Process類的方法允許我們選擇當前進程（我們的程序正運行的進程），程序正運行的線程，及一個計時器來存儲線程開始執行的時間。所有這些方法可合並入一次調用，並指定這個調用函數的返回值為存儲線程開始執行的時間（一個TimeSpan對象）的變量。如下是代碼（共有兩行）。
TimeSpan startingTime;
startingTime = Process.GetCurrentProcess().Threads[0]
.UserProcessorTime;
剩下的我們只需捕獲我們計時的代碼段停止的時間。代碼示例如下：
duration = Process.GetCurrentProcess().Threads[0].UserProcessorTime
.Subtract(startingTime);
現在，讓我們把所有這些合並到一個程序中來測試我們之前測試過的相同代碼。
using System;
using System.Diagnostics;
class chapter1
{
static void Main()
{
int[] nums = new int[100000];
BuildArray(nums);
TimeSpan startTime;
TimeSpan duration;
startTime = Process.GetCurrentProcess().Threads[0].UserProcessorTime;
DisplayNums(nums);
duration = Process.GetCurrentProcess().Threads[0].UserProcessorTime.Subtract(startTime);
Console.WriteLine("Time: " + duration.TotalSeconds);
}
static void BuildArray(int[] arr)
{
for (int i = 0; i <= 99999; i++)
arr[i] = i;
}
static void DisplayNums(int[] arr)
{
for (int i = 0; i <= arr.GetUpperBound(0); i++)
Console.Write(arr[i] + " ");
}
}
使用新的改進的計時代碼，程序返回0.2526。這與第一次計時代碼返回的將近5秒的結果有很大反差。很顯然，這兩種計時技術之間有很大差異，所以在.NET環境中對代碼計時時，你應該使用適合.NET的技術。
計時測試類
雖然我們不需要一個類來運行我們的時間測試代碼，但將代碼重寫成一個類很有意義，主要是因為我們可以降低我們測試的代碼的行數來保持我們代碼的清晰。
一個計時類需要下面的數據成員：
startingTime – 保存我們正測試的代碼的起始時間。
duration – 我們正測試的代碼的結束時間
我們選擇使用TimeSpan數據類型存儲startingtTime與duration這兩個保存了時間的數據成員。我們將只使用一個構造函數，一個默認的構造函數來將這兩個數據成員初始化為0。
我們需要一個方法通知一個計時類對象什麼時候開始計時，什麼時候停止。我們同樣需要一個方法來返回duration數據成員中存儲的數據。
就像你看到的，這個Timing類相當小，僅僅需要幾個方法，如下是其定義：
public class Timing
{
TimeSpan startingTime;
TimeSpan duration;
public Timing()
{
startingTime = new TimeSpan(0);
duration = new TimeSpan(0);
}
public void StopTime()
{
duration = Process.GetCurrentProcess().Threads[0]
.UserProcessorTime.Subtract(startingTime);
}
public void startTime()
{
GC.Collect();
GC.WaitForPendingFinalizers();
startingTime = Process.GetCurrentProcess().Threads[0]
.UserProcessorTime;
}
public TimeSpan Result()
{
return duration;
}
}
下面的程序使用重寫後的Timing類測試了DisplayNames子函數
using System;
using System.Diagnostics;
public class Timing
{
TimeSpan startingTime;
TimeSpan duration;
public Timing()
{
startingTime = new TimeSpan(0);
duration = new TimeSpan(0);
}
public void stopTime()
{
duration = Process.GetCurrentProcess().Threads[0].UserProcessorTime.Subtract(startingTime);
}
public void startTime()
{
GC.Collect();
GC.WaitForPendingFinalizers();
startingTime = Process.GetCurrentProcess().Threads[0].UserProcessorTime;
}
public TimeSpan Result()
{
return duration;
}
}
class chapter1
{
static void Main()
{
int[] nums = new int[100000];
BuildArray(nums);
Timing tObj = new Timing();
tObj.startTime();
DisplayNums(nums);
tObj.stopTime();
Console.WriteLine("time (.NET): " + tObj.Result().TotalSeconds);
}
static void BuildArray(int[] arr)
{
for (int i = 0; i &l
