如何二维矩阵的元素映射到一维数组A＆QUOT;指针数组＆QUOT;间接？ [英] How map 2D matrix entries to 1D array with a "pointer array" indirection?

问题描述

注意：我已经编辑了这个问题与基思·兰德尔和有帮助的反馈<一HREF =htt​​p://stackoverflow.com/users/340457/chiyou>蚩尤。

我有一个主意，用一维数组来缓存最常用的二维N×M的矩阵元素在特定的加工环境。现在的问题是，是否有从那里来深入了解存在的工作已经是身体还是有正义的人们的在知道的。我会先勾勒出腿部工作，并提出这样的问题以后了。作为一个附加说明，蚩尤已经提出的空间填充曲线，这一下概念，我以后的事，但不会轻易回答我的具体问题（即我不能找到一条曲线，它会做什么我以后）。

的腿工作： 目前的最常用的条目的定义为循环和一个特殊的组合 pointer_array （见下面code），该组合产生指数，最常用的矩阵元素。该pointer_array包含数字范围内 [0，最大值（N ，M）] （见上文定义为N×M的矩阵尺寸）。

的code的目的是生产指标的合适（在程序的上下文中）的组合来处理一些所述矩阵条目。这是可能的N = M，即一个方阵。在code（C ++）遍历矩阵看起来像下面的

 的for（int i = 0; I＆n种;我++）
{
    对于（INT J = I + 1; J＆LT;米; J ++）
    {
        自动指针1 = pointer_array [I]
        自动指针2 = pointer_array [I + 1];
        汽车pointer3 = pointer_array [J]。
        汽车pointer4 = pointer_array [J + 1];

        自动取值范= some_matrix [指针1] [pointer3]
        汽车entry2 = some_matrix [指针2] [pointer4]
        汽车entry3 = some_matrix [pointer3] [pointer4]
        汽车entry4 = some_matrix [指针1] [指针2];

        //计算与项...
    }
}
 

有些东西值得单独的说明：

1. 为了使这个缓存是值得的，我觉得应该是密集。即，可以在随机访问和被布置在contiguosly存储器东西。即没有空间浪费（也许除了如果有许多单独的块）和复杂度是O（1）。这将意味着高速缓存不能是相同的2D矩阵下令在其作为一维行/列为主有序阵列整体。我觉得它应该融入了具有长数组的 MAX（N，M）（见矩阵维度定义如上）。

2. 许多循环过程中会被忽略。在 some_matrix 条目

3. 在pointer_array顺序记录的通过矩阵的路线，所以它在别处使用了。

4. 我遇到这方面的需求在不同的场合，但这次我写了一个的 2-OPT 的算法，而我正在寻找，以提高内存访问模式。我知道还有其他方法写的算法（但看到这一点有我遇到这个，我现在想知道是否有一个通用的解决方案其他设置）。

5. 盒子思维之外会产生一种类似的一种指标相结合的的东西，是概念上就像访问一个二维矩阵，但只有更聪明。一种选择是将缓存矩阵的行/列的循环过程中。

6. 由于条目中使用的很多，所以它会比较理想通过缓存some_matrix调用替换 pointer_array 间接使收购的在循环进入* 值将更快，即从可能相当大矩阵的pre加载缓存来代替。这里其他的一点是，它会保存在存储，这反过来又意味着经常使用的值可以很好地适应更快的缓存

问：是否有可能到设备的索引方案，使矩阵索引将基本上成为

  //将二维矩阵的元素使用pointer_array到some_1d_cache
//使得循环索引，可直接使用...

的for（int i = 0; I＆n种;我++）
{
    对于（INT J = I + 1; J＆LT;米; J ++）
    {
        //该some_1d_cache（（X，Y）的调用将计算索引的一维数组缓存...
        自动取值范= some_1d_cache（I，J）;
        自动entry2 = some_1d_cache第（i + 1，J + 1）;
        自动entry3 = some_1d_cache（J，J + 1）;
        汽车entry4 = some_1d_cache（I，I + 1）;

        //计算与项...
    }
}
 

也许像下面会做太多

 的for（int i = 0; I＆n种;我++）
{
    对于（INT J = I + 1; J＆LT;米; J ++）
    {
        自动指针1 = pointer_array [I]
        自动指针2 = pointer_array [I + 1];
        汽车pointer3 = pointer_array [J]。
        汽车pointer4 = pointer_array [J + 1];

        //该some_1d_cache（（X，Y）的调用将计算索引的一维数组缓存...
        自动取值范= some_1d_cache（指针1，pointer3）;
        汽车entry2 = some_1d_cache（指针2，pointer4）;
        汽车entry3 = some_1d_cache（pointer3，pointer4）;
        汽车entry4 = some_1d_cache（指针1，指针2）;

        //计算与项...
    }
}
 

解决方案

您可以索引一个二维矩阵，一维空间填充曲线。数学上这是H（X，Y）=（H（X）* H（γ））。他们也是有用的，因为他们基本上细分，存储一些当地信息，并重新安排了飞机。

Note: I've edited this question with the helpful feedback of Keith Randall and Chiyou.

I have an idea to use 1D array to cache most used 2D NxM matrix entries in a particular processing context. The question is that does there exist already a body of work from where to gain insight or is there just people in the know. I will outline the leg-work first and ask the question later too. As an additional note, Chiyou already proposed space filling curves, which look conceptually the thing I'm after, but won't readily answer to my specific question (i.e. I can't find a curve that would do what I'm after).

The leg-work: Currently the most used entries are defined as a combination of loops and a special pointer_array (see code below), which in combination produce the indices to the most used matrix elements. The pointer_array contains numbers in range [0, max(N, M)] (see above matrix dimensions defined as NxM).

The purpose of the code is to produce a suitable (in context of the program) combination of indices to process some of the matrix entries. It's possible N = M, i.e. a square matrix. The code (C++) traversing the matrix would look like the following

for(int i = 0; i < N; i++)
{        
    for(int j = i + 1; j < M; j++)
    {
        auto pointer1 = pointer_array[i];
        auto pointer2 = pointer_array[i + 1];
        auto pointer3 = pointer_array[j];
        auto pointer4 = pointer_array[j + 1];

        auto entry1 = some_matrix[pointer1][pointer3];
        auto entry2 = some_matrix[pointer2][pointer4];
        auto entry3 = some_matrix[pointer3][pointer4];
        auto entry4 = some_matrix[pointer1][pointer2];

        //Computing with the entries...
    }
}

Some things worth of separate note:

1. To make this caching worthwhile, I think it should be dense. That is, something that can be accessed in random and is laid out contiguosly in memory. I.e. no space "wasted" (except maybe if there are many separate chunks) and complexity is in O(1). It would mean the cache can't be the same 2D matrix ordered in its entirety as a 1D row/column-major ordered array. I feel it should fit into an array having length max(N, M) (see above matrix dimension definition).

2. Many of the entries in some_matrix will be ignored during the loops.

3. The pointer_array ordering records a route through the matrix, so it's used elsewhere too.

4. I've come across this need in various occasions, but this time I've written a 2-opt algorithm, memory access pattern of which I'm seeking to improve. I'm aware there are other ways to write the algorithm (but see the point there are other settings I've come across this and am now wondering if there were a general solution).

5. Outside of the box thinking would be to produce a similar kind of combination of indices to something that is conceptually like accessing a 2D matrix, but only smarter. One option would be to cache matrix rows/columns during looping.

6. As the entries will be used a lot, so it would be more ideal to replace the pointer_array indirection by caching the some_matrix calls so that acquiring the entry* values in the loops would be faster, i.e. from a pre-loaded cache instead of possibly rather big matrix. Other point here is that it would save in storage, which in turn means the often used values could very well fit a faster cache.

Question: Is it possible to device an indexing scheme so that the matrix indexing would essentially become

//Load the 2D matrix entries to some_1d_cache using the pointer_array
//so that the loop indices can be used directly...

for (int i = 0; i < N; i++)
{        
    for (int j = i + 1; j < M; j++)
    {           
        //The some_1d_cache((x, y) call will calculate an index to the 1D cache array...
        auto entry1 = some_1d_cache(i, j);
        auto entry2 = some_1d_cache(i + 1, j + 1);
        auto entry3 = some_1d_cache(j, j + 1);
        auto entry4 = some_1d_cache(i, i + 1);

        //Computing with the entries...
    }
}

Or maybe something like following would do too

for (int i = 0; i < N; i++)
{        
    for (int j = i + 1; j < M; j++)
    {            
        auto pointer1 = pointer_array[i];
        auto pointer2 = pointer_array[i + 1];
        auto pointer3 = pointer_array[j];
        auto pointer4 = pointer_array[j + 1];

        //The some_1d_cache((x, y) call will calculate an index to the 1D cache array...
        auto entry1 = some_1d_cache(pointer1, pointer3);
        auto entry2 = some_1d_cache(pointer2, pointer4);
        auto entry3 = some_1d_cache(pointer3, pointer4);
        auto entry4 = some_1d_cache(pointer1, pointer2);

        //Computing with the entries...
    }
}

解决方案

You can index a 2d matrix with a 1d space filling curve. Mathematically it's H(x,y) = (h(x) * h(y)). They are also useful because they basically subdivide, store some locality information and reorder the plane.

这篇关于如何二维矩阵的元素映射到一维数组A＆QUOT;指针数组＆QUOT;间接？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！