Мне нужно сделать перестановку строк и столбцовв матрице. Как это сделать оптимально?
У меня есть перестановка, например
6 5 4 9 0 1 2 3 6 8 7
Это значит, что нулевая строка должна находиться на 6 месте, 1 строка на пятом, 2 на четвертомб третья на девятом и т.д.
Т.к. двумерный массив это массив указателей на массив указателей(динамически мне нужно выделить), то я просто меняю эти указатели.
void changeRowOrder(int *computation,int **matr) {
fprintf(wFile,"Make row permutation\n");
int i,k;
for (i = 0,k = 0; i < N; ++i) {
fprintf(wFile,"%d ",k);
orderOfRows[computation[i]] = matr[i];
}
fputs("\n",wFile);
}
Вот так меняю столбцы:
void makeColumsnPermutation(int **arr,int *permutation,int arrOrRowOrder) {
int i,j,k,tmp;
int **destMatrix = NULL;
destMatrix = (int**) malloc(N * sizeof(int *));
if ((destMatrix == NULL)) {
fprintf(stderr, "out of memory\n");
exit(2);
}
if(arrOrRowOrder) {
if ((destMatrix == NULL)) {
fprintf(stderr, "out of memory\n");
exit(2);
}
for(i = 0; i < N; ++i) {
destMatrix[i] = arr[i];
}
for(i = 0; i < N; ++i) {
for(j = 0; j < N; ++j) {
for(k = 0; k < N; ++k) {
if(j == permutation[k]) {
destMatrix[i][j] = arr[i][k];
fprintf(wFile,"%d ",arr[i][k]);
break;
}
}
}
fputs("\n",wFile);
}
//free(arr);
//arr=NULL;
arr = destMatrix;
}
else {
for (i = 0; i < N; i++) {
destMatrix[i] = (int*) malloc(N * sizeof(int));
if (destMatrix[i] == NULL) {
fprintf(stderr, "out of memory\n");
exit(2);
}
}
for(i = 0; i < N; ++i) {
for(j = 0; j < N; ++j) {
for(k = 0; k < N; ++k) {
if(j == permutation[k]) {
destMatrix[i][j] = arr[i][k];
break;
}
}
}
}
for(i = 0; i < N; ++i) {
free(arr[i]);
}
free(arr);
arr = destMatrix;
}
//fputs("\n",wFile);
}
Но дело в том, что я могу сделать сначала перестановку по строкм, затем мне опять захочется сделать по строкам. Но у меня есть отдельный 2-мерный массив (статический указатель) и массив указателей, чтобы хранить перестановку строк.
static int N = 2,**orderOfRows,**sourceMatrix;
void allocation {
// локально выделяю в функции
sourceMatrix = (int**) malloc(N * sizeof(int *));
orderOfRows = (int**) malloc(N * sizeof(int*));
if ((sourceMatrix == NULL) || (orderOfRows == NULL)) {
fprintf(stderr, "out of memory\n");
exit(2);
}
}
for (i = 0; i < N; i++) {
sourceMatrix[i] = (int*) malloc(N * sizeof(int));
if ((sourceMatrix[i] == NULL) ) {
fprintf(stderr, "out of memory\n");
exit(2);
}
}
Поэтому когда я делаю меняю порядок строк,то возникает 2 случаю, когда я обычную матрицу передаю и только массив указателей. РАссмотрим 2 соучай(когда передаю только массив указатлей, массив, указывающий на строки, rowOrder). Если при этом я уже сделал перестановку по строкам, то у меня уже есть массив orderOFrows, поэтому я должен его удалить и перезаписать новые значения. Но orderOfRows ссылается на элементы из sourceMAtrix, если я перезапишу orderOfrows и очищу память, затем присвою новые указатели, то связь с sourceMatrix потеряется (у меня выскакивает access violation). Если не буду очищать, тогда будет возникать утечка, хотя утечкой это назвать сложно, т.к. мне эти указатели нужны, они косвенно ссылаются на нужную матрицу. Только будет такой "паровозик": чтобы найти элемент в матрице(взять по индексу), нужно будет переходить сначала по одному, затем по второму, затем по третьему и т.д. столько раз, сколько я делал перестановок по строкам ,т.е. будет неочевидная длинная индексация. Это плохо, т.к. это буду делать много раз. Очищение памяти я закомментарил вверху в программе.
//free(arr);
//arr=NULL;
arr = destMatrix;
Как мне сделать оптимально быстро перестановку строк и столбцов(особенно строк)? Причем у меня возникает при таком походе перетирание памяти (когда очищаю память, разкомментировать код), потому что перестановка по столбцам делается неправильно. Перестановка по строкам делается, вроде, правильно, а по столбцам нет (проверял на симметричной матрице).
Т.е. может быть 2 варианта:
1)
changeRowOrder(rowPermutation,sourceMatrix);
printMatrix(orderOfRows);
makeColumsnPermutation(orderOfRows,rowPermutation,1);
changeRowOrder(rowPermutation,orderOfRows);
printMatrix(orderOfRows);
makeColumsnPermutation(orderOfRows,rowPermutation,1);
2)
makeColumsnPermutation(sourceMatrix,rowPermutation,0);
Все память выделенаЮ, см выше.
Здравствуйте, Jorik12, Вы писали:
J>Мне нужно сделать перестановку строк и столбцовв матрице. Как это сделать оптимально?
J>У меня есть перестановка, например 6 5 4 9 0 1 2 3 6 8 7
J>Это значит, что нулевая строка должна находиться на 6 месте, 1 строка на пятом, 2 на четвертомб третья на девятом и т.д.
J>Т.к. двумерный массив это массив указателей на массив указателей(динамически мне нужно выделить), то я просто меняю эти указатели.
J>J>void changeRowOrder(int *computation,int **matr) {
J> fprintf(wFile,"Make row permutation\n");
J> int i,k;
J> for (i = 0,k = 0; i < N; ++i) {
J> fprintf(wFile,"%d ",k);
J> orderOfRows[computation[i]] = matr[i];
J> }
J> fputs("\n",wFile);
J>}
J>
J>Вот так меняю столбцы:
J>J>void makeColumsnPermutation(int **arr,int *permutation,int arrOrRowOrder) {
J> int i,j,k,tmp;
J> int **destMatrix = NULL;
J> destMatrix = (int**) malloc(N * sizeof(int *));
J> if ((destMatrix == NULL)) {
J> fprintf(stderr, "out of memory\n");
J> exit(2);
J> }
J> if(arrOrRowOrder) {
J> if ((destMatrix == NULL)) {
J> fprintf(stderr, "out of memory\n");
J> exit(2);
J> }
J> for(i = 0; i < N; ++i) {
J> destMatrix[i] = arr[i];
J> }
J> for(i = 0; i < N; ++i) {
J> for(j = 0; j < N; ++j) {
J> for(k = 0; k < N; ++k) {
J> if(j == permutation[k]) {
J> destMatrix[i][j] = arr[i][k];
J> fprintf(wFile,"%d ",arr[i][k]);
J> break;
J> }
J> }
J> }
J> fputs("\n",wFile);
J> }
J> //free(arr);
J> //arr=NULL;
J> arr = destMatrix;
J> }
J> else {
J> for (i = 0; i < N; i++) {
J> destMatrix[i] = (int*) malloc(N * sizeof(int));
J> if (destMatrix[i] == NULL) {
J> fprintf(stderr, "out of memory\n");
J> exit(2);
J> }
J> }
J> for(i = 0; i < N; ++i) {
J> for(j = 0; j < N; ++j) {
J> for(k = 0; k < N; ++k) {
J> if(j == permutation[k]) {
J> destMatrix[i][j] = arr[i][k];
J> break;
J> }
J> }
J> }
J> }
J> for(i = 0; i < N; ++i) {
J> free(arr[i]);
J> }
J> free(arr);
J> arr = destMatrix;
J> }
J> //fputs("\n",wFile);
J>}
J>
J>Но дело в том, что я могу сделать сначала перестановку по строкм, затем мне опять захочется сделать по строкам. Но у меня есть отдельный 2-мерный массив (статический указатель) и массив указателей, чтобы хранить перестановку строк.
J>J>static int N = 2,**orderOfRows,**sourceMatrix;
J> void allocation {
J> // локально выделяю в функции
J> sourceMatrix = (int**) malloc(N * sizeof(int *));
J> orderOfRows = (int**) malloc(N * sizeof(int*));
J> if ((sourceMatrix == NULL) || (orderOfRows == NULL)) {
J> fprintf(stderr, "out of memory\n");
J> exit(2);
J> }
J> }
J> for (i = 0; i < N; i++) {
J> sourceMatrix[i] = (int*) malloc(N * sizeof(int));
J> if ((sourceMatrix[i] == NULL) ) {
J> fprintf(stderr, "out of memory\n");
J> exit(2);
J> }
J> }
J>
J>Поэтому когда я делаю меняю порядок строк,то возникает 2 случаю, когда я обычную матрицу передаю и только массив указателей. РАссмотрим 2 соучай(когда передаю только массив указатлей, массив, указывающий на строки, rowOrder). Если при этом я уже сделал перестановку по строкам, то у меня уже есть массив orderOFrows, поэтому я должен его удалить и перезаписать новые значения. Но orderOfRows ссылается на элементы из sourceMAtrix, если я перезапишу orderOfrows и очищу память, затем присвою новые указатели, то связь с sourceMatrix потеряется (у меня выскакивает access violation). Если не буду очищать, тогда будет возникать утечка, хотя утечкой это назвать сложно, т.к. мне эти указатели нужны, они косвенно ссылаются на нужную матрицу. Только будет такой "паровозик": чтобы найти элемент в матрице(взять по индексу), нужно будет переходить сначала по одному, затем по второму, затем по третьему и т.д. столько раз, сколько я делал перестановок по строкам ,т.е. будет неочевидная длинная индексация. Это плохо, т.к. это буду делать много раз. Очищение памяти я закомментарил вверху в программе.
J>J>//free(arr);
J> //arr=NULL;
J> arr = destMatrix;
J>
J>Как мне сделать оптимально быстро перестановку строк и столбцов(особенно строк)? Причем у меня возникает при таком походе перетирание памяти (когда очищаю память, разкомментировать код), потому что перестановка по столбцам делается неправильно. Перестановка по строкам делается, вроде, правильно, а по столбцам нет (проверял на симметричной матрице).
J>Т.е. может быть 2 варианта:
J>1)
J>J>changeRowOrder(rowPermutation,sourceMatrix);
J>printMatrix(orderOfRows);
J>makeColumsnPermutation(orderOfRows,rowPermutation,1);
J>changeRowOrder(rowPermutation,orderOfRows);
J>printMatrix(orderOfRows);
J>makeColumsnPermutation(orderOfRows,rowPermutation,1);
J>
J>2)
J>
J>makeColumsnPermutation(sourceMatrix,rowPermutation,0);
J>
J>Все память выделенаЮ, см выше.
Для начала хотелось бы разобраться в некоторых вещах. Первое, может ли в перестановке дублироваться строки, как в вашем примере
6 5 4 9 0 1 2 3 6 8 7, где т 0 строка и 8-ая строка должны поменяться с 6-ой строкой?
Второе — в вашем первом коде
for (i = 0,k = 0; i < N; ++i) {
fprintf(wFile,"%d ",k);
orderOfRows[computation[i]] = matr[i];
}
в который, честно признаюсь, особо не вникал, похоже нет перестановок строк, так как перестановка обычно связывается с операцией
swap, а у вас лишь одно присваивание. Если конечно в это кусек кода имеет место перестановка строк.
J>Мне нужно сделать перестановку строк и столбцовв матрице. Как это сделать оптимально?
оптимально — это переопределить только оператор доступа к ячейке
Здравствуйте, rm822, Вы писали:
J>>Мне нужно сделать перестановку строк и столбцовв матрице. Как это сделать оптимально?
R>оптимально — это переопределить только оператор доступа к ячейке
Причем если используется std::valarray, то у него ровно для этой цели уже есть indirect_array.
Во первых не может быть у меня одинаковых элементов в перестановке.
Во-вторых, если не заметно, то я меняю УКАЗАТЕЛИ. Зачем мне все элементы копировать? Просто потом я использую другой массив указателей.
