如何比較兩個數據結構操作的運行時間

Question

我想比較兩個整數搜索樹（AVL樹與RedBlack樹）的性能。那麼，我應該如何設計/設計測試來實現這一目標呢？例如，讓我們考慮插入的操作，我應該遵循哪些步驟來說明平均情況下該操作在RB情況下更快？我是否應該只插入一個元素（假定樹是預先填充的），還是應該計算一系列插入？我應該考慮如何正確測量CPU時間？

在此先感謝。

Answer 1

這是一個非常廣泛的問題，因此，我認爲你不應該希望任何人能夠在這裏得到關於如何衡量表現的最終正確答案。這就是說...

首先，你應該開發一套測試。現在有兩種流行的技術可以做到這一點：監視應用程序完成的真實世界的操作序列（因此，找到一些使用AVL或RB樹的開源應用程序，並添加一些代碼以打印它執行的操作序列）或以分析（或綜合）方式創建此類操作流，以針對任意數量的案例（平均使用情況，特定種類的異常或其他異常使用情況，隨機使用情況等）。這些類型的痕跡越多，你就可以測試，越好。

一旦你有你的一套痕跡測試，你需要開發一個驅動程序來進行評估。對於AVL和RB樹，驅動程序應該很簡單（我認爲在這種情況下，這不應該是一個問題;兩者都呈現與用戶相同的接口，僅在內部實現細節方面有所不同）。驅動程序應該能夠有效地重現記錄在跟蹤集中的使用情況，並使跟蹤的操作在您的數據結構上執行。我喜歡做的一件事就是包括第三個「虛擬」候選人什麼都不做;這樣，我可以看到痕跡處理對整體性能的影響有多大。

每條痕跡應執行很多次。您可以將其稍微形式化（將統計不確定性降低到已知範圍內），但根據經驗法則，您的錯誤順序將根據1/sqrt（n）縮小，其中n是試驗次數。換句話說，通過每次運行10000次而不是100次，平均出現10倍的誤差。記錄所有值;要查找的內容是平均值，中位數，模式等。對於每次運行，嘗試保持系統條件相同;沒有其他程序正在運行等。爲了幫助消除由於外部因素變化造成的虛假結果，您可以挑選最低和最高的10％異常值...

現在，簡單比較數據集。也許你最關心的是跟蹤所需的平均時間？也許是最糟糕的？也許你真正關心的是一致性;標準差是大還是小？您應該有足夠的數據來比較兩個測試結構上執行的給定跟蹤的結果;並針對不同的痕跡，它可能會更有意義來看待不同的數字（例如，如果你創建了一個人工合成的基準，應該是對RB樹最壞的情況下，你可能會問RB和AVL樹有多嚴重做到了，而你可能不關心這個用於表示AVL樹最好的情況下另一個跟蹤等）

定時在CPU上可以在自己的權利的挑戰。您需要確保計時器的分辨率足以測量您的事件。 clock（）和gettimeofday（）函數 - 以及其他函數 - 是記錄事件時間的流行選擇。如果你的痕跡完成得太快，你可以得到幾個試驗的總時間（所以，如果你的計時器支持微秒的時間和你的痕跡在10微秒完成，可以測量跟蹤的100個執行，而不是1，並獲取時間值10s毫秒，這應該是準確的）。

另一個潛在的缺陷是每次都提供相同的執行環境。在跟蹤運行之間，至少，您可以考慮確保您以乾淨的緩存開始的技術。要麼是這樣，要麼沒有計算第一次執行的時間，也不知道在消除異常值時可能會調整這個結果。重置緩存可能更安全（通過操縱某個大型數組的每個元素，例如在執行跟蹤之間），因爲代碼A可能受益於緩存中的某些值，而代碼B可能受到影響。

這些是您在進行自己的績效評估時可能考慮的一些事情。其他工具 - 例如PAPI和其他分析器 - 可以測量某些事件 - 緩存命中/未命中，指令等 - 並且與簡單比較壁鐘運行時間相比，此信息可以進行更豐富的比較。

Answer 2

準確測量CPU時間可能非常棘手，具體取決於您的特定編程語言，實現等。例如，使用Java的JIT編譯，結果可能會有很大的不同，這取決於您之前運行代碼的次數！

你能給出更多關於你的情況的細節嗎？