如何在C++排序期間監視/顯示進度

Question

我打算編寫一個交互式C++幾何處理插件，該插件將經常對大量數據進行排序。雖然初步跡象表明這種排序只需要一兩秒鐘，但我寧願在那段時間顯示進展 - 即我想每秒更新一次進度指示器。這比打開等待光標並讓程序凍結一段不確定的時間長度（即使只有幾秒鐘）更好。

如果我使用類似std :: sort的東西，我可以使用比較函數來更新進度指示器，但我不知道「完成百分比」。我也可以將排序分解爲子排序，更新子排序之間的進度，然後合併。我最好的辦法可能是編寫自己的排序方法，儘管我不知道爲了獲得性能和std :: sort（並確保正確性）一樣好，需要付出多少努力。在任何情況下，該排序方法偶爾會向回調方法發送「完成百分比」。

我想知道是否有其他人遇到並解決了這個問題 - 我希望可能有一個標準庫中的排序方法，可以做我想做的，或者其他一些我沒有想到的技術。

更新：感謝迄今爲止的出色答案。有幾個非常好的建議，我將暫停選擇接受的答案，直到我有機會在即將到來的項目中測試這些想法。

更新2：我完成我的項目，而這竟然是一個非問題（至少對於客戶因爲它們會被銷售軟件，他們仍然可以從他們的客戶的反饋，將改變。他們的想法）。選擇一個被接受的答案是困難的，因爲有很多好的答案，但最終我選擇了一個關於合併排序的wiki文章，它有一個非常令人回味的動畫。所以如果我需要繼續這樣做，這是我會採取的第一個策略）。

Answer 1

由於std :: sort是基於模板的，所以源代碼應該在標題中可用。您可以複製它並插入進度回調。最大的問題是預測你的完成度有多接近 - 大部分函數都是基於Quicksort，它並不總是進行相同數量的比較。

寫你自己Merge sort將是一種可能性;該算法很容易，並且步驟的數量已被很好地定義。

Answer 2

我會推薦你​​的第二個選項：使用std::sort或其他標準排序功能，如qsort，並讓比較器報告其進度。但不要在每次比較中更新 - 這將是難以忍受的慢 - 而是更新每100ms（比如說）。

Answer 3

使用observer pattern在每個零件完成時發回信號。使用它和需要排序的元素總數可以實時更新進度條。

Answer 4

我認爲，即使您自己編寫了排序，如果您希望進度指示器準確無誤，您也必須進行大量仔細的測量。如果您只需要一個近似的進度指標，那麼您可以使用一些指標，如「比較元素之間的平均距離」或「與快速排序的平均預期數量相比較的比較數量」作爲指標，並實施您已經提到的比較思路。

是的，我認爲你不是一個完全白癡，並且不打算在每次比較中更新進度指示器。如果你這樣做了，你會花費更多的時間來指示進度而不是排序。

作爲一個例子，你通常會期望約n log2 n操作快速排序。涉及多少比較的分析比這個一般性的測量更詳細並且可以更準確，但就本例而言，我們假設。所以你可以計數比較，並報告number_of_comparisons/(n log2 n)作爲你的進展的估計。

由於這只是一個平均指標，我會進行一些實驗，看看您的估計值有多遠，並拋出一些巧妙因素使其與預期平均值相符。你也可以有一個進度條，通過類似「這是我認爲我會完成的事情」來表明不確定性。「指標和指標後的一些空間。

即使您使用自己的排序並提出了一個更加看似精確的測量，進度欄仍然不會平穩更新，效果也會類似。唯一可以確定的方法是，如果您使用較慢但確實可預測的排序，那麼您可以預測元素數量需要多長時間，或者使用非常快速的排序在特定情況下對具有較少可預測行爲的排序進行排序，在這種情況下，沒有真正的方法來獲得完美準確的進度條。

子任務的可預測性和比較總數的可預測性是強烈關聯的。所以我真的不認爲子任務比比較的總數要好。

如果您想使用自己的排序和可預測性是您的最高目標，請轉到heapsort。它仍然是一個排序，它接近於最小比較排序（或者我從閱讀Knuth時記得）。無論數據集是何種數據集，也需要花費相當可預測的時間才能完成。這是較慢的O(n log2 n)種類之一，但仍然是。

作爲您提到的評論者之一，您可能正在解決一個實際上並不存在的問題。首先運行一些實驗。儘管如此，這個問題仍然是一個有趣的智力挑戰。 :-)

Answer 5

我看到你的問題如下所示：

1. 你想在一個連續過程中被解僱離散事件。
2. 這個細分只是告訴用戶正在進行的事情。

我的建議是：

1. 從一些使用加載圖標像http://ajaxload.info/，或者如果它不是一個基於GUI的環境，只是拼出加載。由於事件不到2秒，這不成問題。如果等待時間超過10秒，則預計掛起。

2. 編寫自己的排序方法確實會帶來很多線程安全問題，如果您的代碼使用多線程或將來會這樣做，可能會導致問題。你應該考慮如何嚴重無序將數據是每次要排序，所以實際上你會衡量隨機性存在的程度

3.Another的重要信息，計算的預計數你可能需要這樣做。您可以使用這些信息作爲需要多少次掉期的指標，當您迭代時，這些數據又可以被計算在內。玩弄數據。

Answer 6

用蠻力:)

int elem_num = raw_data.size(); 
int percentage_delta = 100/(elem_num/20); 
int percentage = 0; 
int i = 0; 
std::multiset<Elem*> sorted_data(&compareElemFunc); 
foreach(Elem& elem, raw_data) 
{ 
    sorted_data.insert(&elem); 
    if(i%20) 
    { 
     updateProgressBar(percentage); 
     percentage += percentage_delta; 
    } 
    i++; 
} 
//now, your data is perfectly sorted, iterate through sorted_data 

（如果你不想實現自己的std ::排序（），因爲我缺乏完整的需求正在）

Answer 7

我不建議嘗試破解std :: sort。這通常是用introsort實現的，並且是非常快的NLogN操作。構建你要排序的容器通常比排序數據更昂貴。

但是，如果您要實施進度條，我建議您將排序放在單獨的線程中。通常多線程應用程序比單線程應用程序更難編寫和維護，但您可以通過某種方式實現，而不是針對此進度條的情況。您的應用程序仍然可以主要是單線程的，沒有任何併發​​操作，除了這個進度條以外，可能還有一些事件處理來保持UI的響應。當您準備對數據進行排序時，只需發出另一個線程來執行此操作，並將主線程置於一個等待循環中，直到排序線程完成，在此處進行睡眠並在此期間進行進度條升級。

您可以將此非侵入式方法概括爲任何類型的耗時操作，而無需在代碼中遍歷update_progress_bar（）類型調用或挖掘std :: sort的實現或嘗試重新創建輪子。由於主線程將處於等待/更新進度欄狀態，因此在您的工作線程完成之前在某種意義上阻塞，因此您沒有任何與多線程相關的問題（需要線程同步來訪問您的整個共享資源應用程序，除了進度計數器，競爭條件，死鎖等）。它也將是您可以實現的最流暢的進度計數器，因爲它會同時更新。

如果您擔心與鎖定進度計數器相關的效率，只需使用原子操作來增加它。

至於確定排序算法進展的程度，有幾種方法可以做到這一點。一種是讓它以您所擁有的數據大小運行一次，並嘗試預測後續運行需要的時間。這是完全非侵入式的，但有點難以做到，但是，如果做得對，它會比定期遞增計數器更準確地監控進度（忽略間隔可能不需要偶數時間的事實）。第二種方法比較簡單，但有一點惡意是修改比較器謂詞以增加進度計數器。用狀態來製作謂詞通常是不被接受的，但它並不像僅僅因爲想要一個進度計數器而試圖實現自己的插入式那樣邪惡。

另外，如果您的插畫需要這麼長時間，我不得不懷疑，您的容器是否存儲這些三角形對象或指向它們的指針？如果是前者，你可能需要考慮後者，因爲它會大幅度提高速度。