快速訪問包裝在二維矩陣中的單元格

我有一個環繞的矩陣。快速訪問包裝在二維矩陣中的單元格

m_matrixOffset指向纏繞矩陣的第一個單元（0,0）。因此，要訪問一個單元格，我們在GetCellInMatrix.Logic函數的下面執行環繞操作（在while循環中），每次有人訪問單元格時都會執行該操作。這是在一秒鐘內執行數千次。有沒有什麼方法可以使用某種查找或其他方式來優化它。 MAX_ROWS和MAX_COLS未必是2

struct Cell 
{ 
    Int rowId; 
    Int colId; 
} 
int matData[MAX_ROWS][MAX_COLS]; 


int GetCellInMatrix(const Cell& cellIndex) 
{ 
     Cell newCellIndex = cellIndex + m_matrixOffset ; 

     while (newCellIndex.rowId > MAX_ROWS) 
     { 
      newCellIndex.rowId -= MAX_ROWS; 
     } 

     while (newCellIndex.colId > MX_COLS) 
     { 
      newCellIndex.y -= MAX_COLS; 
     } 

    return data[newCellIndex.rowId][newCellIndex.colId]; 
}

來源

2016-12-15 Poorna

功率您可能會感興趣的除法的餘數的概念，通常作爲a % b的剩餘執行。

因此

return data[newCellIndex.rowId % MAX_ROWS][newCellIndex.colId % MAX_COLS];

之前沒有它需要的while循環。

根據註釋，如果在每個查詢中完成，餘數計算中隱含的整數除法代價太大。假設m_matrixOffset在大量查詢中是恆定的，則使用餘數操作減少其座標。然後newCellIndex小於最大值的兩倍，因此最多隻需要減少一次。因此，用if代替while是安全的，省去一個比較。

如果您可以犧牲內存空間，然後加倍矩陣尺寸並填充重複矩陣元素的多餘條目。更新矩陣時，必須確保這種模式成立。

然後，再次假設m_matrixOffset和CellIndex在行和列的最大值內，您可以訪問擴展矩陣的單元格，而無需進一步減少。這將是「查找表」想法的變體。

或者使用真正的查找表，但你執行像

return data[repeatedRowIndex[newCellIndex.rowId]][repeatedColIndex[newCellIndex.colId]];

來源

2016-12-15 10:35:59 LutzL

我們之前就是這麼做的，但是這導致了性能問題，因爲這對CPU來說代價很高。由於我們訪問單元數千甚至數百萬次，因此它不是最佳的 – Poorna

然後，您需要驗證resp。量化矩陣偏移量。如果你可以保證矩陣偏移量也小於矩陣維數（通過計算餘數一次），你有最大值。一個減少，並可以用'if'來代替'while'，從而減少一個比較的工作量。 – LutzL

這取決於如果包裝是相對於基體或大或小3陣列單元查找。

最常見的情況是，你需要的只是最近的鄰居。所以用M + 2製作矩陣N + 2並複製包裝。這使得讀取速度快，但寫入有點煩瑣（通常是一個很好的折衷）。

如果這樣做不好，請專業化功能。計算出哪些單元格是邊緣單元格並專門處理（您必須能夠做到這一點，而不是簡單地將邏輯硬編碼到訪問中，當然，如果只有一個或兩個單元格會更改每次傳遞，而不是如果您每一次產生一個隨機列表）。

來源

2016-12-15 10:58:46

你的意思是如果有一個矩陣（512,512），我需要一個環繞矩陣（1024,10234）？ – Poorna

通常這種模式是我們在矩陣上有一個隨機點，我們需要所有的鄰居。因此，如果我們使矩陣514 x 514而不是512 x 512，我們不需要特殊的代碼來讀取鄰居。支持更遙遠的鄰居變得更加昂貴。 –

快速訪問包裝在二維矩陣中的單元格

回答

相關問題