Создание более эффективного преобразования матрицы в C

Question

Я работаю над созданием более эффективной версии этого C-кода, используя арифметику указателя, но я застрял.

Это исходный код:

(я звоню тип массива Marray_t, внутр M)

void transpose(Marray_t A){ 
    int i, j; 
    for(i=0; i<M; i++){ 
     for(j=0; j<M; j++){ 
      int t = A[i][j]; 
      A[i][j] = A[j][i]; 
      A[j][i] = t; 
     } 
    } 
} 

Без использования таНоса, я хочу, чтобы создать более эффективный способ сделать транспонировать на квадратной матрице размерности MxM.

Это то, что я пытался:

void transpose(Marray_t A, int M){ 
int i, j; 
for (i=0; i<M; i++){ 
    int *row = A[i]; 
    for(j=0; j<M; j++){ 
    int *col = &A[i][j]; 
      int t1 = *(row+i); 
    int t2 = *(col + M*i)+(i*4); 
    *row = t2; 
     } 
    } 
} 

Если я запускаю мой код на матрицу 2х2, он не работает.

Если у меня есть матрица = {{2,3}, {4,5}}, моя транспозиция должна дать мне {{2,4}, {3,5}}, но я получаю {{3,2 }, {4,5}}

Я очень новичок в использовании указателей, поэтому любые советы/помощь будут высоко оценены. Спасибо.

Answer 1

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

Как только вы это сделаете, вы сможете легко найти свою ошибку.

Например, если у вас есть следующий код:

int* row = A[i]; 

Нарисуйте свою матрицу A с ее строками и столбцами, а затем нарисовать отдельную коробку и назовите его «строку». Нарисуйте стрелку из окна в строку A [0], так как строка сначала укажет на 0-ю строку.

Всегда используйте поверхность для рисования при работе с указателями и ссылками!

Answer 2

Моя любимая трюка для этого - ничего не двигать.

Сохраните флаг в своей структуре, если вы хотите получить доступ по строкам или столбцам кулаком, и измените ваш get/set, чтобы это уважать. Тогда транспонирование просто переворачивает этот флаг.

Answer 3

Существует несколько проблем с обоими вашими кодами.

Первый один:

• Как drahnr также отметил, своп выпускается дважды в ячейке для каждой ячейки для тех, которые имеют i == j исключением. Те, у которых i == j, вообще не меняются, а остальные дважды меняются местами, практически ничего не делая.

Второй один:

• переменной t1 полностью неиспользованными.
• Вы выходите за границы, которые ваш массив охватывает для всех 2i >= M, обращаясь к области памяти, с которой вы должны возиться.

Посмотрите:

int t2 = *(col + M*i)+(i*4); 

точно так же, как:

int t2 = A[i + i][j] + (i*4); 

со вторым i, поступающим с + M*i. В словах:

• col показывал ячейку [i][j],
• тогда вы хотели ячейку, которая M * i после этого.
• каждого M клетки дальше, приведет вас к следующему колонку (или строкам, в зависимости от того, как вы себе представляли на уме, не имеет значения)
• так, M * i будет означать i столбец/строку дальнейшего

И A[2i][j] будет за пределами верхнего предела M, что вы не должны превышать 2i >= M.

То, что + (i*4) не оказывает влияния на используемую ячейку, из-за operator precedence. Операторы разыменования * получают оценку перед добавлением, требуя, чтобы вы использовали круглые скобки в случае, если вы хотите, чтобы сложение произошло раньше; но в этом случае все будет не так хорошо, даже если вы их используете.

Такой подход не будет в любом случае оптимизировать процесс. Путь Michael был бы интересным и, вероятно, самым быстрым. Но вы можете просто исправить первый код для правильной работы (т. Е. Не поменять местами дважды), а также не выпускать своп для i == j, и это должно быть достаточно хорошим. Я не скажу вам, как это сделать, вы, безусловно, сможете это сделать.

Я могу дать вам один намек на обмен, хотя ... Вместо того, чтобы:

int t = A[i][j]; 
    A[i][j] = A[j][i]; 
    A[j][i] = t; 

можно было бы написать:

A[i][j] ^= A[j][i]; 
    A[j][i] ^= A[i][j]; 
    A[i][j] ^= A[j][i]; 

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