2017-03-24 62 views
1

我怎麼能算排序與正整數的向量時發生在標準C++ STL排序函數比較的數量做比較的次數?中的std ::排序()

+6

您可以提供自己的功能,執行標準比較並計算調用次數。 –

回答

6

一種快速,非侵入性的方法是使用lambda函數。你可以,如果你使用的是C++ 11或以上,所以像下面使用lambda:

unsigned int numComparisons = 0U; 
std::vector<unsigned int> someContainer; 
// Fill container, etc. 
std::sort( 
    std::begin(someContainer), 
    std::end(someContainer), 
    [&numComparisons](unsigned int lhs, unsigned int rhs) 
    { 
     ++numComparisons; 
     return lhs < rhs; 
    } 
); 

std::cout << numComparisons << " comparisons were performed in std::sort" << std::endl; 
+0

注意:觀察方法對於查看真正發生的情況非常有用,但它也意味着您正在測量*您的*標準庫的「排序」以用於*您的*特定輸入。如果其他標準庫決定採用Python中的TimSort算法,並且您的輸入已經大部分/完全排序,那麼這種自適應特性可能會減少與O(n)的比較工作,即使正常情況下的工作將會是'O(n log n)',所以你的觀察會給出一個總體誤導性的觀察結果。瞭解記錄的*保證*可能很重要。 – ShadowRanger

+0

我完全同意ShadowRanger,並鼓勵讀者也閱讀他的答案。這有點取決於*你爲什麼測量這個!與分析一樣,使用真實的數據和環境來完成這一點很重要。 –

2

爲了補充觀測的方法,你可以閱讀the documentation。在複雜度上,std::sort必須是:

O(N·log(N)),其中N = std ::距離(第一次,最後一次)平均比較。 (直到C++ 11)

O(N·log(N)),其中N = std :: distance(first,last)比較。 (因爲C++ 11)

顯然,大O符號可以掩蓋某些恆定的因素,但一般地,希望它是相稱N·日誌(N)(其中對數是基體2,像所有優秀的CS日誌)。

+0

我沒有得到「直到」和「自從」之間的區別。總是不是很大的上限?那麼「平均」(或缺少)的含義是什麼? – user463035818

+0

@ tobi303大O符號確實描述了N增長時的上限漸近極限。然而,在這種情況下,輸入的*次數很重要,當對可能的排序進行平均時,算法可以是O(N log(N)),但是具有例如O(N^2)的破壞性情況。 C++ 11的限制更加嚴格,併爲所有可能的輸入順序指定O(N log(N))。 –

+0

@ThomasRussell thx,我將不得不考慮一下。 – user463035818