我在 GF(2) 上实现了高斯消元法。我使用二维 64 位整数数组以行优先表示形式存储矩阵(矩阵的行存储在连续数组中)。我通过以下方式对矩阵的行进行高斯消去:
其中 (A)^i 表示 A 的第 i 行。然后我意识到，如果我按如下方式在第 5-6 行分割循环，我会获得稍微更好的性能:
我预计性能会稍差一些，因为我再次迭代整个外循环......有人对此行为有解释吗？编译器是否做了一些棘手的优化工作，这在分割变体上更容易执行？ (使用 g++ -O3 编译)
(如果伪代码不能得出答案，我可以提供一个最小的代码示例)
最佳答案
没有理由期望第二个解决方案的性能会更差 - 两种算法都在中，它们甚至具有相同的常量:在第一个解决方案中，您的外循环位于
中，在第二个中，
有两个循环.
实际上，您的第二个解决方案可能具有更好的 CPU 缓存特性或更适合编译器优化。特别是，由于您的操作是在 GF(2)/Z(2) 上进行的，因此它们可以表示为单词上的二进制操作 - 这将导致大幅加速。根据您的实现(以及n的限制)，算法可能会优化为 到底。不过，如果不看一下您的代码，我们就无法真正判断:)。
关于c++ - 循环分割性能问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38563860/