爲什麼置換矩陣用於交換數組的行？

Question

使用置換矩陣交換行有什麼好處？爲什麼要創建置換矩陣，然後應用矩陣乘法，比用for循環交換行更容易，更高效？

Answer 1

置換矩陣是一種有用的數學抽象，因爲它們允許使用矩陣代數的正規規則進行分析，而不必引入其他類型的操作。在軟件中，良好的實現不會將置換矩陣存儲爲完整矩陣，它們存儲置換數組，並且它們直接應用（沒有全矩陣乘法）。

根據矩陣大小以及涉及的操作和訪問模式，根本不會將置換應用於內存中的數據，而只是將其用作額外的間接尋址。因此，當您請求(P * M)(i,j)時，其中P是置換矩陣，而M是您正在置換的某個其他矩陣，因此根本不需要重新排列數據，而是在您訪問時元素訪問操作將查找置換行元素。

Answer 2

我首先想到的是「空間局部性」問題。緩存技術假定如果訪問內存位置，則可能訪問內存的附近位置。在一些編程語言中，行中的元素是鄰居，而列中的元素是其他元素中的鄰居。這取決於實施。我猜想，置換矩陣是爲了解決這個問題而設計的，因爲矩陣乘法的優化是學術界最主要的改進之一。簡單的循環結構將無法利用緩存技術來提高性能。