Транспонировать 2D массив

Question

Как вы эффективно транспонируете матрицу? Есть ли для этого библиотеки или какой алгоритм вы бы использовали?

например:.

short src[W*H] = {
  {1,2,3},
  {4,5,6}
};
short dest[W*H];


rotate_90_clockwise(dest,src,W,H); //<-- magic in here, no need for in-place

//dest is now:

{
  {4, 1},
  {5, 2},
  {6, 3}
};

(В моем конкретном случае его массив src представляет собой необработанные данные изображения, а местом назначения является кадровый буфер, и я встроен в ARM на цепочке инструментов, которая не поддерживает сборку)

Answer 1

Одним из очень простых решений, которое работает в O (1), является сохранение дополнительного логического значения для матрицы, сообщающего, является ли оно «транспонированным» или нет. Тогда доступ к массиву будет производиться в соответствии с этим логическим значением (строка / столбец или столбец / ряд).

Конечно, это будет препятствовать использованию вашего кэша.

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

Answer 2

В некоторых случаях для этого есть библиотеки. И, в частности, есть приемы, которые вы можете играть с векторизованными данными (например, четыре 32-битных элемента в 128-битном векторе, но это также относится к четырем 8-битным байтам в 32-битном регистре), чтобы работать быстрее, чем отдельные доступ к элементам.

Для транспонирования стандартная идея состоит в том, что вы используете «перемешивающие» инструкции, которые позволяют вам создавать новый вектор данных из двух существующих векторов в любом порядке. Вы работаете с 4x4 блоками входного массива. Итак, начиная, у вас есть:

v0 = 1 2 3 4
v1 = 5 6 7 8
v2 = 9 A B C
v3 = D E F 0

Затем вы применяете команды тасования к первым двум векторам (чередование их нечетных элементов, A0B0 C0D0 -> ABCD и чередование их четных элементов, 0A0B 0C0D -> ABCD) и к последним двум, чтобы создать новый набор векторов с каждым транспонированным блоком 2x2:

1 5 3 7
2 6 4 8
9 D B F
A E C 0

Наконец, вы применяете инструкции перемешивания к нечетной паре и четной паре (объединяя их первые пары элементов, AB00 CD00 -> ABCD и их последние пары, 00AB 00CD -> ABCD), чтобы получить:

1 5 9 D
2 6 A E
3 7 B F
4 8 C 0

И там 16 элементов, транспонированных в восьми инструкциях!

Теперь, для 8-битных байтов в 32-битных регистрах, ARM не имеет точно инструкций тасования, но вы можете синтезировать то, что вам нужно, с помощью Shift и инструкции SEL (выборки), а второй набор тасовок вы можете выполнять в одной инструкции с инструкциями PKHBT (упаковать верхнюю часть наполовину) и PKHTB (упаковать верхнюю часть наполовину).

Наконец, если вы используете большой ARM-процессор с NEON-векторизацией, вы можете сделать что-то подобное с 16-элементными векторами в 16x16 блоках.

Answer 3

В Википедии есть вся статья о транспонировании матрицы на месте. Для неквадратных матриц это нетривиальная, довольно интересная задача (при использовании памяти меньше, чем O (N x M)). Статья содержит ссылки на довольно много статей с алгоритмами, а также некоторые исходные коды.

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

(Стандартная функция транспонирования даст этот результат для данных вашего примера:)

{
  {1, 4},
  {2, 5},
  {3, 6}
};

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

Answer 4

• Если матрица квадратная или вы не ищете транспозицию по месту, это действительно просто:

По сути, вы перебираете строки и меняете каждый элемент на соответствующий элемент столбца. Вы получаете соответствующий элемент, обмениваясь индексами строк и столбцов. Когда вы обработали все столбцы, транспонирование закончено. Вы также можете пойти другим путем и перебирать столбцы.

Если вы хотите повысить производительность, вы можете скопировать полную строку во временный массив и полный соответствующий столбец в другой, а затем скопировать их обратно. Должно быть немного быстрее (даже если эта стратегия предполагает еще одно присвоение переменной), если вы используете memcopy для переносов, включающих самые внутренние элементы.

• Если матрица не квадратная (как в вашем примере), это действительно сложно сделать на месте. Поскольку транспонирование не меняет потребности в памяти, все равно представляется возможным сделать это на месте, но если вы сделаете это небрежно, вы в конечном итоге перезапишите элементы другой строки или столбца.

Если память не является узким местом, я рекомендую использовать временную матрицу. Это действительно проще и, вероятно, все равно будет быстрее.

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

Но в некоторых случаях я понимаю, что это будет невозможно, как правило, если данные готовятся для доступа к существующему оборудованию или библиотеке.

Answer 5

Наиболее эффективное решение здесь - это вращение данных во время их копирования из ОЗУ в кадровый буфер. Вращение источника в ОЗУ и последующее копирование результата в кадровый буфер, в лучшем случае, будет вдвое медленнее, чем версия копирования и поворота. Итак, вопрос в том, является ли более эффективным читать последовательно и писать случайно или читать случайно и последовательно. В коде это будет выбор между:

// read sequential
src = { image data }
dest = framebuffer
for (y = 0 ; y < H ; ++y)
{
   for (x = 0 ; x < W ; ++x)
   {
     pixel = *src++
     dest [y,x] = pixel
   }
}

или

// write sequential
src = { image data }
dest = framebuffer
for (x = 0 ; x < W ; ++x)
{
   for (y = 0 ; y < H ; ++y)
   {
     pixel = src [x,y]
     *dest++ = pixel
   }
}

Ответ на этот вопрос может быть определен только путем профилирования кода.

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

Answer 6

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

char temp[W*H];
char* ptemp = temp;
memcpy(temp, array, sizeof(char)*W*H);
for (i = 0; i < H; i++){
    char* parray = &array[i];
    for (j = 0; j+8 <= W; j += 8, ptemp += 8){
        *parray = ptemp[0]; parray += H;
        *parray = ptemp[1]; parray += H;
        *parray = ptemp[2]; parray += H;
        *parray = ptemp[3]; parray += H;
        *parray = ptemp[4]; parray += H;
        *parray = ptemp[5]; parray += H;
        *parray = ptemp[6]; parray += H;
        *parray = ptemp[7]; parray += H;
    }
    for (; j < W; j++, parray += H){
        *parray = *ptemp++;
    }
}

Я не знаю, как избежать проблемы локальности кэша из-за характера проблемы.