快速访问包装在二维矩阵中的单元格

我有一个环绕的矩阵。快速访问包装在二维矩阵中的单元格

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，我们不需要特殊的代码来读取邻居。支持更遥远的邻居变得更加昂贵。 –

快速访问包装在二维矩阵中的单元格

回答

相关问题