Транспонируйте 2D массив

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

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

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

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

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

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

{
  {1, 4},
  {2, 5},
  {3, 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
   }
}

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

Теперь,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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