在我的程式的關鍵路徑中，我需要對一個陣列進行排序（特別是一個 C std::vector<int64_t>，使用 gnu c 標準庫）。我正在使用標準庫提供的排序演算法（std::sort），在這種情況下是 introsort。
我很好奇這個演算法的性能如何，并且在對不同標準和第三方庫使用的各種排序演算法進行一些研究時，幾乎所有人都關心“n”往往是主導因素的情況。
不過，在我的具體情況下，“n”將是 2-20 個元素的數量級。因此，常數因素實際上可能占主導地位。當我們正在排序的整個陣列適合幾個快取行時，快取效果之類的事情可能會非常不同。
對于像這種常數因子可能壓倒漸近因子的情況，最好的排序演算法是什么？這些演算法是否存在任何經過??審查的 C 實作？
uj5u.com熱心網友回復：
對于小型陣列（即少于 10-20 個元素），插入排序或選擇排序通常都更快。
uj5u.com熱心網友回復：
Introsort 會考慮您的顧慮，并切換到短序列的插入排序實作。
由于您的 STL 已經提供了它，您可能應該使用它。
uj5u.com熱心網友回復：
如果不確切知道“任何事情”是什么，就不可能知道做任何事情的最快方法。
這是一組可能的假設：
- 除了元素具有可比性外，我們對元素結構一無所知。我們沒有有用的方法將它們分組到 bin 中（用于基數排序），我們必須實作基于比較的排序，并且比較以不透明的方式進行。
- 我們沒有關于輸入初始狀態的資訊；任何輸入順序都是同樣可能的。
- 我們不必關心排序是否穩定。
- 輸入序列是一個簡單的陣列。訪問元素是恒定時間的，交換它們也是如此。此外，我們將純粹根據預期的比較次數對函式進行基準測驗，而不是交換次數、掛鐘時間或其他任何內容。
有了這組假設（可能還有其他一些假設），少量元素的最佳演算法將是手工排序網路，根據輸入陣列的確切長度進行定制。（這些總是執行相同數量的比較；有條件地“短路”這些演算法是不可行的，因為“條件”將取決于檢測已經部分排序的資料，這仍然需要比較。）
對于排序四個元素的網路（在已知的最佳五個比較中），這可能看起來像（我沒有測驗這個）：
template<class RandomIt, class Compare>
void _compare_and_swap(RandomIt first, Compare comp, int x, int y) {
if (comp(first[x], first[y])) {
auto tmp = first[x];
arr[x] = arr[y];
arr[y] = tmp;
}
}
// Assume there are exactly four elements available at the `first` iterator.
template<class RandomIt, class Compare>
void network_sort_4(RandomIt first, Compare comp) {
_compare_and_swap(2, 0);
_compare_and_swap(1, 3);
_compare_and_swap(0, 1);
_compare_and_swap(2, 3);
_compare_and_swap(1, 2);
}
當然，在現實世界的環境中，我們會有不同的假設。對于少量元素，使用真實資料（但仍然假設我們必須進行基于比較的排序），很難擊敗已經編譯好的插入排序（或冒泡排序，實際上是同一件事）的幼稚實作優化。考慮到硬體級別的復雜性（例如，流水線指令所需的步驟，然后補償分支錯誤預測）和軟體級別（例如執行交換與執行比較，以及對性能常數因子分析的影響）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/496600.html
下一篇：根據條件獲取最小值