1

注意：我已经根据Keith Randall和Chiyou的有用反馈编辑了这个问题。

我有一个想法，使用 1D 数组在特定处理上下文中缓存最常用的 2D NxM 矩阵条目。问题是，是否已经有大量的工作可以从中获得洞察力，或者是否只有知道的人。我将首先概述腿部工作，然后再提出问题。作为补充说明，Chiyou已经提出了空间填充曲线，它在概念上看起来是我所追求的东西，但不会轻易回答我的具体问题（即我找不到可以做我所追求的曲线） .

腿部工作： 目前最常用的条目被定义为循环和特殊的组合pointer_array（见下面的代码），它们组合产生最常用矩阵元素的索引。pointer_array 包含范围 [0, max(N, M)]中的数字（参见上面定义为 NxM 的矩阵维度）。

代码的目的是产生一个合适的（在程序的上下文中）索引组合来处理一些矩阵条目。有可能N = M，即方阵。遍历矩阵的代码 (C++) 如下所示

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...
    }
}

一些值得单独注意的事情：

  1. 为了使这种缓存有价值，我认为它应该是密集的。也就是说，可以随机访问并在内存中连续布局的东西。即没有空间“浪费”（除非有许多单独的块）并且复杂性在 O(1) 中。这意味着缓存不能是与 1D 行/​​列主要有序数组完全排序的相同 2D 矩阵。我觉得它应该适合长度为max(N, M)的数组（参见上面的矩阵维度定义）。

  2. some_matrix在循环期间将忽略其中的许多条目。

  3. pointer_array 排序记录了通过矩阵的路线，因此它也用于其他地方。

  4. 我在各种场合都遇到过这种需求，但这次我编写了一个2-opt算法，我正在寻求改进它的内存访问模式。我知道还有其他方法可以编写算法（但请参阅我遇到的其他设置，现在想知道是否有通用解决方案）。

  5. 跳出框框的想法是产生一种类似的索引组合，在概念上类似于访问 2D 矩阵，但更智能。一种选择是在循环期间缓存矩阵行/列。

  6. 由于条目将被大量使用，因此pointer_array通过缓存 some_matrix 调用来替换间接会更理想，这样获取entry*循环中的值会更快，即从预加载的缓存而不是可能相当大的矩阵。这里的另一点是它会节省存储空间，这反过来意味着经常使用的值可以很好地适应更快的缓存。

问题：是否可以设计一种索引方案，使矩阵索引本质上变成

//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...
    }
}

或者也许像下面这样的东西也可以

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...
    }
}
4

1 回答 1

1

您可以索引具有 1d 空间填充曲线的 2d 矩阵。数学上它是 H(x,y) = (h(x) * h(y))。它们也很有用，因为它们基本上可以细分、存储一些位置信息并重新排列平面。

于 2012-08-27T00:06:01.187 回答