給定一個大小為 10 5的陣列A。
然后給定m（m很大，m>>A的大小）操作，每次操作都是針對位置p，增加t。
A[p] =t
最后，我輸出整個陣列的每個位置的值。
是否有任何不斷的優化來加快中間修改操作？
例如，如果我對位置進行排序，我可以按順序修改它們以避免隨機訪問。但是，此操作會產生額外的排序成本。有沒有其他方法可以加快速度？
在排序后嘗試重新執行所有操作可能比直接執行它們快一個數量級。但是分揀成本太高了。
uj5u.com熱心網友回復：
在多核架構上，最好的解決方案當然是并行執行原子訪問A[p]。這假設內核的數量足夠大，可以使并行性不僅減輕原子操作的開銷，而且比串行實作更快。使用 OpenMP 或使用本機 C 執行緒/原子可以很容易地做到這一點。核心的數量不需要太大，否則沖突的數量可能會顯著增加，從而導致爭用，從而降低性能。這應該沒問題，因為專案的數量很大。該解決方案還假設訪問是非常均勻隨機的。如果它們不是（例如正態分布），那么爭用可能太大，以至于方法效率不高。
另一種解決方案是在空間上拆分 N 個執行緒之間的訪問。陣列范圍可以靜態拆分為 N（相對相等）部分。所有執行緒都讀取輸入，但只有擁有輸出陣列目標范圍的執行緒寫入其中。然后可以組合陣列部分。如果資料分布均勻，此方法適用于少數執行緒。當分布根本不均勻時（例如，正態分布），則可能需要一個預計算步驟來調整執行緒擁有的陣列范圍。例如，可以計算中位數或四分位數，以便更好地平衡執行緒之間的作業。計算四分位數可以使用像Floyd Rivest (std::partition應該不會太糟糕，盡管我希望它使用一種通常會慢一點的 IntroSelect 演算法）。預計算可能很昂貴，但這應該比進行排序要快得多。使用 OpenMP 無疑是實作這一點的好主意。
另一種替代實作是簡單地在每個執行緒中單獨執行歸約，然后在全域陣列中總結每個執行緒的最終陣列。假設核心數量不太大，此解決方案在您的情況下效果很好（因為“m >> A 的大小”）。如果是這樣，則需要將此方法與第一種方法混合使用。最后一種方法可能是最簡單有效的方法。
uj5u.com熱心網友回復：
此外，@Jér?me Richard 的回答針對并行執行緒計算。
我將命名部分排序的想法，例如“合并排序只是少數迭代”或“桶排序僅在桶中”（注意，它們是不同的）。最好將塊大小設定為頁面大小，以便在作業系統級別方面具有更好的整體性能。尤其是考慮m的特別大。部分排序的成本將通過節省快取未命中和頁面交換來分攤。
如果這是一個面試問題，我會詢問更多關于資料稀疏性m、分布p、t硬體、CPU、記憶體、功耗、延遲等細節的細節。并且針對每個新條件，相應地定制更詳細的設計。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/519867.html
標籤：C 数组表现优化记忆
上一篇：XYZ坐標到XY網格
下一篇：連接和分組熊貓資料幀的有效方法