algorithm - 为什么使用置换矩阵来交换数组的行？

Question

使用置换矩阵交换行有什么好处？为什么要创建一个置换矩阵然后应用矩阵乘法，它是否比仅使用 for 循环交换行更容易和更有效？

Answer 1

置换矩阵是一种有用的数学抽象，因为它们允许使用矩阵代数的正常规则进行分析，而不必引入另一种类型的运算。

在软件中，好的实现不会将置换矩阵存储为完整矩阵，它们存储置换数组并直接应用它（无需完整矩阵乘法）。

根据矩阵的大小以及所涉及的操作和访问模式，根本不将排列应用于内存中的数据可能会更便宜，而只是将其用作额外的间接。因此，当您请求(P * M)(i,j)whereP是一个置换矩阵并且M是您正在置换的某个其他矩阵时，数据根本不需要重新排列，而是元素访问操作将在您访问元素时查找置换的行。

Answer 2

我首先想到的是一个叫做“空间局部性”的问题。缓存技术假设如果访问内存位置，则很可能访问内存的附近位置。在某些编程语言中，行中的元素是邻居，而列中的元素在其他语言中是邻居。这取决于实施。我想排列矩阵就是为了解决这个问题而设计的，因为矩阵乘法的优化是算法学术界主要致力于改进的问题之一。简单的循环结构将无法利用缓存技术来提高性能。