Изпечатай

[appmaster]

Днес се хванах да ровя за имплементация решаваща проблема със завъртане на NxN матрица с 90°
Питах чичо Гошо, но намерих само два вида решения - чрез xor или чрез временна променлива.
Понеже знаем, че алгоритъма решаващ това In-place_matrix_transposition#Square_matrices е доста неприятен за кеша на процесорите, а и най-добрия случай е big O(n²).
Та се питах дали няма някакъв, така да се каже, логаритмичен начин за решаване на този проблем?
Ако сте запознати с някаква имплементация от рода на разделяне на проблема на две при всяка стъпка, моля да го споделите.

ПС: Намерих нещо елегантно, но все още се чудя дали няма нещо по-добро:

Код

GeSHi (C):
    int tmp, l;
    for(int i = 0; i < M_SIZE/2; i++)
    {
        for(int j = i, k = M_SIZE - i - 1; j < k; j++)
        {
            tmp = m[i][j];
            l = M_SIZE - j - 1;
 
            m[i][j] = m[l][i];
            m[l][i] = m[k][l];
            m[k][l] = m[j][k];
            m[j][k] = tmp;
        }
    }

[arda_kj]

Най-елегантния метод е да не транспонираш нищо. Просто маркираш матрицата като транспонирана и когато достъпваш съответния елемент разменяш индексите.

Пример:

Код:

вместо m[i][j] взимаш m[j][i]

Аз по елегантно и бързо от това не мога да измисля. Естествено всяко предимство си има недостатъци - в случая трябва да помниш, че трябва да разменяш индексите, когато достъпиш транспонираната матрица. Предимство е очевадно - няма никакви излишни операции, а оттам бързодействието е максимално.

Ако наистина искаш реално да транспонираш матрицата, просто правейки си някакви тестове, тогава това, което предложих не е за теб.

[zxz]

Е то с два цикъла може да презапише самата матрица със "вместо m[j] взимаш m[j]". По интересно е да я завъртиш на 45 градуса