После проведения некоторых экспериментов с квадратными матрицами разных размеров, возникла закономерность. Неизменно,transposing a matrix of size 2^n is slower than transposing one of size 2^n+1, Для небольших значенийnРазница несущественная.

Однако большие различия возникают по значению 512. (по крайней мере, для меня)

Disclaimer: I know the function doesn't actually transpose the matrix because of the double swap of elements, but it makes no difference.

Следует за кодом:

#define SAMPLES 1000
#define MATSIZE 512

#include <time.h>
#include <iostream>
int mat[MATSIZE][MATSIZE];

void transpose()
{
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
   {
       int aux = mat[i][j];
       mat[i][j] = mat[j][i];
       mat[j][i] = aux;
   }
}

int main()
{
   //initialize matrix
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
       mat[i][j] = i+j;

   int t = clock();
   for ( int i = 0 ; i < SAMPLES ; i++ )
       transpose();
   int elapsed = clock() - t;

   std::cout << "Average for a matrix of " << MATSIZE << ": " << elapsed / SAMPLES;
}

измененияMATSIZE давайте изменим размер (дух!). Я отправил две версии на Ideone:

size 512 - average 2.46 ms - http://ideone.com/1PV7m size 513 - average 0.75 ms - http://ideone.com/NShpo

В моей среде (MSVS 2010, полная оптимизация) разница похожа:

size 512 - average 2.19 ms size 513 - average 0.57 ms

Why is this happening?