Транспонирование 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} 
}; 

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

Answer 1

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

Для транспозиции стандартная идея заключается в том, что вы используете инструкции «shuffle», которые позволяют создавать новый вектор данных из двух существующих векторов в любом порядке. Вы работаете с блоками 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) и последние два, чтобы создать новый набор векторов с каждым 2х2 блоком транспонированным:

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 не имеет точно команд перетасовки, но вы можете синтезировать то, что вам нужно, с помощью сдвигов и команды SEL (select), а второй набор тасов может выполнять одну команду с помощью PKHBT (верхняя половина нижнего края пакета) и инструкции PKHTB (верхняя половина нижнего индекса).

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

Answer 2

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

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

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

Answer 3

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

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

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

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

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

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

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

Answer 4

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

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

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

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

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

Answer 5

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

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++; 
    } 
} 

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

Answer 6

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

// 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 
    } 
} 

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

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