缓存不经意矩阵转置在 C++ 中的实现

Question

我已经在 C++ 中实现了一个就地缓存不经意的矩阵转置算法，如下所示：

void CacheObliviousTransposition(int x, int delx, int y, int dely, int N, int* matrix) {
    if ((delx == 1) && (dely == 1)) {
        int tmp = matrix[(N*y) + x];
        matrix[(N*y) + x] = matrix[(N*x) + y];
        matrix[(N*x) + y] = tmp;
        return;
    }

    if (delx >= dely) {
        int xmid = delx / 2;
        CacheObliviousTransposition(x, xmid, y, dely, N, matrix);
        CacheObliviousTransposition(x + xmid, delx - xmid, y, dely, N, matrix);
        return;
    }

    int ymid = dely / 2;
    CacheObliviousTransposition(x, delx, y, ymid, N, matrix);
    CacheObliviousTransposition(x, delx, y + ymid, dely - ymid, N, matrix);
}

但是，当我在转置后调用以下方法以确保其正常工作时，进入了 if 循环，因此我假设实现一定有问题。

void CheckTransposition(int N, int* matrix)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (matrix[(i*N) + j] != (j*N) + i + 42)
            {
                cout << "Transposition failed at i=" << i << ", j=" << j << "\n";
            } 
        }
    }
}

谁能帮我找出问题所在？

注意：变量矩阵是动态分配的整型数组如下，因为矩阵是逐行存储在N*N个连续的内存位置

int* MatrixInit(int N)
{

    int* matrix = new int[N*N];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            matrix[(i*N) + j] = (i*N) + j + 42;
        }
    }

    return matrix;
}

Answer 1

以上代码会将您的元素转置两次。例如，一旦 CacheObliviousTransposition 到达单个元素 [0,1]，它会将其转置为 [1,0]。然而，一个单独的递归稍后将到达 [1,0]，并再次将其转置为 [0,1]。最终，所有元素都会回到原来的位置。

为了确保元素只转置一次，您可以在切换前检查 x 是否小于 y：

void CacheObliviousTransposition(int x, int delx, int y, int dely, int N, int* matrix) {
    if ((delx == 1) && (dely == 1)) {
        if(x<y)
        {
            int tmp = matrix[(N*y) + x];
            matrix[(N*y) + x] = matrix[(N*x) + y];
            matrix[(N*x) + y] = tmp;
        }
        return;
    }

    if (delx >= dely) {
        int xmid = delx / 2;
        CacheObliviousTransposition(x, xmid, y, dely, N, matrix);
        CacheObliviousTransposition(x + xmid, delx - xmid, y, dely, N, matrix);
        return;
    }

    int ymid = dely / 2;
    CacheObliviousTransposition(x, delx, y, ymid, N, matrix);
    CacheObliviousTransposition(x, delx, y + ymid, dely - ymid, N, matrix);
}

缓存不经意矩阵转置在 C++ 中的实现

Cache Oblivious Matrix Transposition Implementation in C++

c++

transpose

matrix