Транспонирование прямоугольной матрицы c

Транспонирование прямоугольной матрицы c

Rivass

Задача:
Вводится матрица целых чисел A размерами N × M (N — количество строк, M — ко-личество столбцов). Вывести транспонированную матрицу. Динамическое выделе-ние памяти для матрицы и освобождение выделенной памяти реализовать в виде двух функций.

Подскажите пожалуйста в чем ошибка моего кода?

DarkKnight

Динамики действительно тут нет. А как я понимаю это главная суть задания.

Вот, посмотри код, должен разобратся, если будут вопросы то пиши.
А вообще задания такого рода решаются на уровне классов. Посмотри на форуме, я описывал класс TMatrix.

Вложения

Araneus

to DarkKnight125
скажи пожалуйста, в какой среде ты компилишь проги. Просто уже не первый пост от тебя, где есть такая строчка:

DarkKnight

Нет, просто в Borland C++ Builder действительно есть проблемы с реализацией локали. У них свое собственное интересное определение идет какое то, далекое от стандарта, так что если хочешь получить кириллицу в консоле все же придется юзать:
#include
CharToOem();
Ну или для консольных приложений выбрать другую среду.

Предположим, что у нас есть матрица размеров m * n, которая хранится в одномерном массиве. Как ее транспонировать?

3 ответа 3

Транспонировать прямоугольную матрицу, сохранённую в одномерном массиве, без создания дополнительных массивов можно с помощью следующего алгоритма.

Для примера рассмотрим прямоугольную матрицу размера 3 x 5 :

В транспонированном виде она имеет вид:

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

Таким образом, для транспонирования матрицы можно действовать по следующему алгоритму:

  1. Если количество столбцов матрицы равно 1, стоп;
  2. Перемещаем элементы последнего столбца текущей матрицы так, чтобы они следовали непосредственно за элементами всех остальных столбцов текущей матрицы. При этом порядок следования элементов последнего столбца по отношению друг к другу должен быть сохранён. Также, порядок следования элементов в текущей матрице "без последнего столбца" по отношению друг к другу должен быть сохранён.
  3. Считаем, что количество столбцов в матрице уменьшилось на 1.
  4. Переходим к п. 1.
Читайте также:  Как проверить компьютер на скрытый майнинг

У меня есть матрица (относительно большая), которую мне нужно транспонировать. Например предположим, что моя матрица

Я хочу, чтобы результат был следующим:

Какой самый быстрый способ сделать это?

Решение

Это хороший вопрос. Есть много причин, по которым вы захотите переставить матрицу в памяти, а не просто поменять координаты, например, в умножении матриц и размытии по Гауссу.

Сначала позвольте мне перечислить одну из функций, которые я использую для транспонирования (РЕДАКТИРОВАТЬ: см. Конец моего ответа, где я нашел гораздо более быстрое решение)

Теперь давайте посмотрим, почему транспонирование полезно. Рассмотрим умножение матриц C = A * B. Мы могли бы сделать это таким образом.

Таким образом, однако, будет много пропусков кэша. Намного более быстрое решение состоит в том, чтобы сначала взять транспонирование B

Умножение матриц — O (n ^ 3), а транспонирование — O (n ^ 2), поэтому использование транспонирования должно оказывать незначительное влияние на время вычислений (для больших n ). В матричном умножении циклическое разбиение даже более эффективно, чем использование транспонирования, но это намного сложнее.

Хотелось бы знать более быстрый способ сделать транспонирование (Изменить: я нашел более быстрое решение, см. Конец моего ответа). Когда через несколько недель выйдет Haswell / AVX2, у него будет функция сбора. Я не знаю, будет ли это полезно в этом случае, но я мог бы представить, собирая столбец и записывая строку. Может быть, это сделает ненужным транспонирование.

Для смазывания по Гауссу то, что вы делаете, это смазывание по горизонтали, а затем смазывание по вертикали. Но смазывание по вертикали имеет проблему с кешем, так что вы делаете

Наконец, то, что я на самом деле делаю в умножении матриц (и в размазывании по Гауссу), — это не просто транспонирование, а транспонирование по ширине определенного размера вектора (например, 4 или 8 для SSE / AVX). Вот функция, которую я использую

Читайте также:  Узнать версию oracle запросом

РЕДАКТИРОВАТЬ:

Я попробовал несколько функций, чтобы найти самую быструю транспонирование для больших матриц. В конце концов, самый быстрый результат заключается в использовании блокировки цикла с block_size=16 (Изменить: я нашел более быстрое решение, используя SSE и блокировку цикла — см. Ниже). Этот код работает для любой матрицы NxM (то есть матрица не обязательно должна быть квадратной).

Ценности lda а также ldb ширина матрицы. Они должны быть кратны размеру блока. Чтобы найти значения и выделить память, например, для матрица 3000×1001 я делаю что-то вроде этого

Для 3000×1001 это возвращает ldb = 3008 а также lda = 1008

Редактировать:

Я нашел еще более быстрое решение с использованием встроенных функций SSE:

Другие решения

Это будет зависеть от вашего приложения, но в целом самый быстрый способ транспонировать матрицу — это инвертировать ваши координаты, когда вы просматриваете, тогда вам не нужно фактически перемещать какие-либо данные.

Некоторые подробности о транспонировании квадратов с плавающей запятой 4×4 (я расскажу о 32-битном целом позже) с аппаратным обеспечением x86. Здесь полезно начать с того, чтобы транспонировать большие квадратные матрицы, такие как 8×8 или 16×16.

_MM_TRANSPOSE4_PS(r0, r1, r2, r3) реализуется по-разному в разных компиляторах. GCC и ICC (я не проверял Clang) используют unpcklps, unpckhps, unpcklpd, unpckhpd тогда как MSVC использует только shufps , На самом деле мы можем объединить эти два подхода вместе, как это.

Одним интересным наблюдением является то, что два шаффла могут быть преобразованы в один шаффл и два смешения (SSE4.1), как это.

Это эффективно преобразовало 4 шаффла в 2 шаффла и 4 смеси. При этом используется на 2 инструкции больше, чем в GCC, ICC и MSVC. Преимущество состоит в том, что оно уменьшает давление в порте, что может иметь преимущество в некоторых обстоятельствах.
В настоящее время все тасования и распаковки могут идти только на один конкретный порт, тогда как смеси могут идти на любой из двух разных портов.

Читайте также:  Игра для двоих для iphone

Я попытался использовать 8 перемешиваний, таких как MSVC, и преобразовать их в 4 перемешивания + 8 смесей, но это не сработало. Мне все еще пришлось использовать 4 распаковки.

Я использовал эту же технику для транспонирования поплавка 8×8 (см. В конце этого ответа).
https://stackoverflow.com/a/25627536/2542702 . В этом ответе мне все еще пришлось использовать 8 распаковок, но мне удалось преобразовать 8 перемешиваний в 4 перемешивания и 8 смесей.

Для 32-разрядных целых чисел ничего подобного shufps (за исключением 128-битных перемешиваний с AVX512), поэтому он может быть реализован только с распаковками, которые, я не думаю, могут быть преобразованы в смеси (эффективно). С AVX512 vshufi32x4 действует эффективно, как shufps за исключением 128-битных дорожек с 4 целыми числами вместо 32-битных с плавающей точкой, так что этот же метод может быть возможно с vshufi32x4 в некоторых случаях. При использовании Knights Landing шаффлы в четыре раза медленнее (пропускная способность), чем смеси.

Рассматривайте каждую строку как столбец, а каждый столбец — как строку .. используйте j, i вместо i, j

транспонирование без каких-либо накладных расходов (класс не завершен):

можно использовать так:

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

Я думаю, что самый быстрый способ не должен брать больше, чем O (n ^ 2), и таким образом вы можете использовать только O (1) пробел:
способ сделать это — поменяться парами, потому что когда вы перемещаете матрицу, то вы делаете следующее: M [i] [j] = M [j] [i], поэтому сохраняйте M [i] [j] в temp, тогда M [i] [j] = M [j] [i], и последний шаг: M [j] [i] = темп. это может быть сделано за один проход, поэтому это должно занять O (n ^ 2)

Ссылка на основную публикацию
Adblock detector