將大型排序陣列與小型未排序陣列合并的最佳演算法是什么？
我將從我的特定用例中舉例說明我的意思，但不要被它們束縛：我主要是試圖對問題給出一種感覺。
8 MB 排序陣列和 92 kB 未排序陣列（快取內排序）
2.5 GB 排序陣列和 3.9 MB 未排序陣列（記憶體排序）
34 GB 排序陣列和 21 MB 未排序陣列（記憶體不足排序）
uj5u.com熱心網友回復：
您可以實作基于塊的演算法來有效地解決此問題（無論陣列的輸入大小如何，只要其中一個比另一個小得多）。
首先，您需要對小陣列進行排序（可能使用基數排序或雙調排序如果您不需要自定義比較器）。然后的想法是將大陣列切成完全適合 CPU 快取的塊（例如 256 KiB）。對于每個塊，使用二進制搜索找到小陣列中最后一項的索引 <= 到塊的最后一項。這是相對較快的，因為小陣列可能適合快取，并且如果陣列很大，則在連續塊之間獲取二分搜索的相同專案。該索引使您能夠知道在寫入之前需要與塊合并的專案數。對于塊中要合并的每個值，在塊中使用二進制搜索找到該值的索引。這很快，因為塊適合快取。一旦知道要插入塊中的值的索引，您可以在每個塊中逐塊有效地移動專案（可能從結尾到開頭就地移動）。這種實作比傳統的合并演算法，由于二進制搜索和塊插入的專案數量很少，因此所需的比較次數要少得多。
對于比較大的輸入，可以使用并行實作. 這個想法是同時處理一組多個塊（即超級塊）。超級塊比經典塊大得多（例如 >=2 MiB）。每個執行緒一次處理一個超級塊。對小陣列執行二分查找，以了解每個超級塊中插入了多少個值。這個數字在執行緒之間共享，以便每個執行緒知道它可以安全地獨立于其他執行緒寫入輸出的位置（可以使用并行掃描演算法在大規模并行架構上執行此操作）。然后將每個超級塊拆分為經典塊，并使用先前的演算法在每個執行緒中獨立解決問題。
演算法的（攤銷）時間復雜度O(n (1 log(m) / c) m (1 log(c)))與m大陣列n的長度，小陣列的長度和c塊大小（為了清楚起見，這里忽略了超級塊，但它們只改變了一個常數因子的復雜度就像常數c一樣）。
替代方法/優化：如果您的比較運算子很便宜并且可以使用 SIMD 指令進行矢量化，那么就可以優化傳統的合并演算法。傳統方法由于分支（在一般情況下很難預測）以及無法輕松/有效地矢量化而非常慢。但是，由于大陣列比小陣列大得多，傳統演算法會從大陣列中選取小陣列之間的大量連續值。這意味著您可以選擇大陣列的 SIMD 塊并將值與小陣列之一進行比較。如果所有 SIMD 項都小于從小陣列中選取的項，那么您可以非常有效地一次寫入整個 SIMD 塊。否則需要寫一部分SIMD chunk，然后寫小陣列的item，切換到下一個。最后一個操作顯然效率較低，但它應該很少發生，因為小陣列比大陣列小得多。注意小陣列還是需要先排序的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/360321.html