在二維數組中尋找最大值的快速算法

我有一個尺寸爲N×N的二維數組（實際上是一個圖像）。我需要找到數組中M個最大值的索引（M < < N x N ）。線性化索引或2D coords都很好。數組必須保持完整（因爲它是一個圖像）。我可以從頭開始製作副本，但排序數組會擾亂索引。在二維數組中尋找最大值的快速算法

我很好，做了一個完整的數組傳遞（即O（N^2）很好）。任何人都有一個好的算法來儘可能有效地做到這一點？

2011-04-19 wallacer

數據是否存在某種模式，或者我們在談論純粹的隨機分佈？在這種情況下，N^2並不差 - 它與您的數據大小基本上是線性的。 – 2011-04-19 22:10:48

如果您願意執行特定於CPU的緩存行優化，並且您知道數據的寬度和數據的存儲順序，則可以預先獲取循環開頭的「下一個」緩存行的數據值，以便在使用之前將其存儲在CPU L1/L2高速緩存中以進行比較。這可以將算法加快一個或兩個數量級。 – 2011-04-19 22:16:18

至少你可以對數組進行切片並行處理，如果它應該在多核cpu上運行的話。 – BenjaminB 2011-04-19 22:20:38

Selection是排序的嚴峻妹妹（連續重複這十次）。選擇算法不如分類算法已知，但仍然有用。

這裏你不能比O（N^2）（在N中）做得更好，因爲沒有任何信息表明你不能訪問數組中的每個元素。

一個好方法是保留一個由M個最大元素組成的priority queue。這使得O（N x N x log M）。

您遍歷數組，排隊對（元素，索引）。隊列保持其元素按第一個組件排序。

一旦隊列具有M個元素，而不是現在排隊你：

如果M較大，則優先對數組進行排序。

注： @Andy Finkenstadt使得一個好點（在評論你的問題）：你一定要遍歷數組中的「數據局部性的方向」：確保你閱讀連續內存。

此外，這是平凡的並行化，唯一不可並行化的部分是當你加入子進程時合併隊列。

2011-04-19 22:11:36

雅優先級隊列是我玩的主意。我正在尋找一種解決方案，可以有效減少我必須做的排序工作。我想我可以通過使用樹/堆而不是僅僅一個隊列來減少插入步驟。 – wallacer 2011-04-19 23:53:08

@wallacer：請參閱維基百科文章：優先級隊列有許多不同的可能實現。確保你在最少的時間內以最少的價格插入，彈出和偷看。 – 2011-04-20 07:03:36

您可以將數組複製到一個元組（數組，原始X，原始Y）的單維數組中，然後在（O（n）時間）內構建一個基本堆棧，只要您將堆實現爲數組。

然後，您可以檢索O（M lg n）時間中的M個最大元組，並從元組中引用它們的原始x和y。

2011-04-19 22:12:01

如果你要製作一個輸入數組的副本，以便進行排序，這比僅僅通過整個數據挑選數字的方式更加糟糕。

所以問題是你的M有多大？如果它很小，可以將結果（即具有2D索引和值的結構）存儲在一個簡單的數組或向量中。這將盡量減少堆操作，但是當你發現一個比你的矢量更大的值時，你必須改變它。

如果您期望M變得非常大，那麼您可能需要更好的數據結構，如二叉樹（std :: set）或使用排序後的std :: deque。std :: set會減少內存中元素必須移動的次數，而如果使用std :: deque，它會進行一些移位，但會減少你必須顯着移動堆的次數，這可能會給你更好的表現。

2011-04-19 22:17:32 DXM

你的問題沒有以任何有趣的方式使用2維，更容易在2d數組中考慮等價問題。

有解決這個問題2種主要途徑：

十個分量一組M個最大的元素，並通過陣列迭代。（使用堆可以有效地執行此操作）。

這很簡單，很可能是你的情況更好（M < < N）
使用選擇，（下面的算法是快速排序的適應）：
- 創建一個輔助的數組，包含索引[1..N]。
- 選擇一個argitary索引（和相應的值），並對索引數組進行分區，使得對應於元素較少的索引向左移動，較大的元素向右移動。
- 重複這個過程，二進制搜索風格，直到你縮小M個最大的元素。
如果你想避免最壞的情況下問題（同快速排序有），然後看一下更先進的算法，（如中位數選擇的中位數）

2011-04-19 22:18:06 hugomg

這有利於大M.案件你從數組中搜索最大值多少次？如果您只搜索一次，那麼只需掃描一遍，保留M個最大的那個。

如果您多次執行此操作，只需將值插入排序列表（可能最好以平衡樹形式實現）。

2011-04-19 22:26:30

回答