時代的自定義排序函數被調用

我有與自定義功能sortproc分類物體V的向量數：時代的自定義排序函數被調用

std::sort(v.begin(), v.end(), sortproc);

之前排數組，我想事先怎麼知道很多時候sortproc會被調用。

我試過了什麼？我嘗試克隆矢量，然後對拷貝進行排序並計算sortproc被調用的次數。我通過增加一個計數器來做到這一點。然後，在對複製進行排序後，我讀取計數器的值並再次對原始向量進行排序。這可行，但效率很低，因爲它整個工作都是兩次。是否有可能以更有效的方式做到這一點？

來源

2013-12-07 TyMarin

O（N日誌N）次？ –

我聞到一個XY，更好的是，這裏是一個AZ問題。（這個嘗試的解決方案大概與真實的解決方案相似，因爲A是來自Z.） – 2013-12-07 21:45:01

真正無法確切知道'sortproc'在不知道'std :: sort'確切實現的情況下會被調用多少次，就像以及向量中數據的實際排列。這似乎是一個奇怪的事情，要預測。根據C++標準中的算法保證（即O（N log N）），您可以確定在一個長度爲N的隨機化向量上調用sortproc的次數的增長率，但不是絕對的。即使是大哦，只會給漸近的趨勢，而不是絕對的。 –

幾乎肯定不是。想到的兩個障礙是：

1）該標準沒有定義什麼算法std::sort使用，所以便攜式代碼不能確切地知道除了僅僅嘗試它以外，還要執行多少次比較。 2）即使你確實知道算法，我認爲對於明智的分類算法來說，找出所需比較的數量並不比找出倒數的數量更容易，它本身具有與排序相同的複雜性。所以你不會得到更高效的解決方案。

2的解決方法是如果sort算法是這樣的，即比較次數不取決於數據的有序接近程度，而只取決於數據的大小。這也不是很難設計具有該屬性的排序算法。它可能比「真正的」排序算法效率低，但可能比排序兩次更有效。

因此，舉例來說，在合併排序中，通常當合並的一邊用盡時，將另一邊的剩餘部分直接複製到目標中。如果在那時你做了一堆額外的冗餘比較來補足數字，那麼比較的數量將不取決於輸入的順序。而無意義比較的數量最差的情況是總數的一半，所以它不應該比分類兩次更糟糕。不過，這與std::sort不是一個「公平的」比較，因爲合併排序不是std::sort的有效算法：它使用了太多的額外內存。

排序網絡使用比較固定數量太多，但也沒有良好的std::sort，因爲你需要知道的項目來設計網絡的數...

來源

2013-12-07 21:45:56

時代的自定義排序函數被調用

回答

相關問題