c++ - 重新排序 vector 数据的有效方法(解释为 3D 数组)

Question

我正在开发一个用 C++ 编写的应用程序，它必须处理存储在连续内存空间中的一些数据，这些数据被解释为 3D 数组。为了高效的数据处理，我不得不改变内存中的数据顺序。

举个例子:原始数据位于内存中，我可以通过数据指针 (uint16_t*) 访问数据，它被解释为 3D 数组并具有以下维度:
xSize=4, ySize=4, zSize=3
在内存中，数据位于如下位置:(d_x,y,z)

d_0,0,0 | d_1,0,0 | d_2,0,0 | d_3,0,0 | d_0,1,0 | d_1,1,0 | d_2,1,0 | d_3,1,0 | .... | d_3,0,2 | d_3,1,2 | d_3,2,2 | d_3,3,2 |

现在我想按 z,y,x 的顺序获取数据:

d_0,0,0 | d_0,0,1 | d_0,0,2 | d_0,1,0 | d_0,1,1 | d_0,1,2 | .... | d_2,3,2 | d_3,3,0 | d_3,3,1 | d_3,3,2 |

我用以下循环做了一个实现:

for (uint32_t z = 0; z < zSize; z++) {
    for (uint32_t y = 0; y < ySize; y++) {
        for (uint32_t x = 0; x < xSize; x++) {
            uint32_t readPos = z * xSize * ySize + y * xSize + x;
            uint32_t outPos = y * xSize * zSize + x * zSize + z;
            *(dataOutPtr + outPos) = *(dataInPtr + readPos);
        }
    }
}

有谁知道如何加速这个算法？是否可以在并发执行中执行某些部分，或者有人知道用于重新排序 3D 数据的另一种解决方案吗？

Answer 1

这必然是一个野蛮的算法。您的循环要么在源中具有良好的缓存位置，要么在目标中具有良好的缓存位置，但不能同时具有两者。具有讽刺意味的是，这可能也是您重新排列数据的原因，以便在您使用它时获得更合适的缓存位置，但在您真正完成之前，重新排列原始布局会减慢您的速度。

很明显，您必须访问每个元素，并且您的最内层循环体的性能与它即将获得的性能差不多。

也许可以将其并行化 — 其他人将不得不探索它，因为我不具备这方面的知识 — 但从基本的 C++ 角度来看，我认为您已经尽力而为。至少，除非您可以预处理或修复源数据，或者除非您可以完全不重新安排(例如，如果您实际上不关心缓存位置，因此可以简单地将您的索引方案更改为外观)。