Почему матрицы перестановок используются для замены строк массива?

Question

Каковы преимущества использования матрицы перестановок для замены строк? Почему нужно создать матрицу перестановок, а затем применить матричное умножение, это проще и эффективнее, чем просто поменять местами строки с циклом for?

Answer 1

Матрицы перестановок представляют собой полезную математическую абстракцию, поскольку они позволяют проводить анализ с использованием обычных правил матричной алгебры без необходимости вводить другой тип операции.

В программном обеспечении хорошие реализации не хранят матрицу перестановок какполная матрица, они хранят массив перестановок и применяют его напрямую (без полного умножения матрицы).

В зависимости от размеров матриц, используемых операций и шаблонов доступа, может быть дешевле не применятьперестановка данных в памяти вообще, но только для использования в качестве дополнительного косвенного обращения.Таким образом, когда вы запрашиваете (P * M)(i,j), где P - это матрица перестановок, а M - какая-то другая матрица, которую вы переставляете, данные вообще не нужно переупорядочивать, скорее, операция доступа к элементу будет искатьперестановочная строка при доступе к элементу.

Answer 2

Первое, что приходит мне в голову, это проблема, называемая «пространственная локальность».Технологии кэширования предполагают, что при доступе к ячейке памяти возможно получить доступ к ближайшим ячейкам памяти.В некоторых языках программирования элементы в строках являются соседями, тогда как элементы в столбцах являются соседями в других.Это зависит от реализации.Я предполагаю, что матрицы перестановок предназначены для решения этой проблемы, поскольку оптимизация умножения матриц является одной из проблем, над которыми в основном работают алгоритмы.Простая структура цикла не сможет использовать технологии кэширования для повышения производительности.