我有一个二维数组SomeData* data[4096][4096]。在这里，数据沿最后一个坐标是连续的，因此由于内存位置的原因，在y坐标上进行迭代比在x坐标上进行迭代要快。但是，我拥有的访问模式是先查看一个条目，然后再查看两个坐标中的相邻邻居，即data [x] [y]以及data [x-1] [y-1]，data [x +1] [y + 1]，等等。
如果我可以分配此数组以使较小的2d子块在内存中连续，那将加快处理速度。
我说分配，但是我怀疑这里的解决方案是正常分配2d数组，然后对索引做一些技巧，这样我就可以连续访问2d块。换句话说，我想要一些可以转换坐标的查找功能，但是我无法立即看到它应该是什么。
SomeData* data[4096][4096];
SomeData* lookup(size_t x,size_t y) {
//??? Some logic to translate x,y such that 2d blocks are accessed contiguously.
}
保证数据数组的两个维度均为2的幂。
让我们说我们有一个nxm-grid。我们想将网格细分为bxb块。必需n％b = 0和m％b = 0。
让我们称整体指数为I = 0，...，n-1和J = 0，...，m-1和块i = 0，...，b-1和j中的指数= 0，...，b-1。
我尝试绘制布局here。
给定I，块的列索引为（I / b），块内索引i = I％b。块的行索引为（J / b），块内索引j = J％b。
每个完整块都包含b * b个元素。因此，整行的块包含（n / b） b b = n * b个元素。
将元素（I，J）的线性索引放在一起是：
运行时大小的blocked-grid-class的草图：
template <typename T,std::size_t N,std::size_t M,std::size_t B>
class Block_Grid
{
static_assert(N % B == 0);
static_assert(M % B == 0);
public:
Block_Grid() = default;
T & operator()(std::size_t i,std::size_t j)
{
return _elements[index(i,j)];
}
protected:
private:
std::size_t index(std::size_t i,std::size_t j) const
{
return (i % B) + (j % B) * B + (i / B) * B * B + (j / B) * N * B;
}
std::array<T,N * M> _elements;
};
或编译时大小的类
{{1}}