I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.
Can I extend it to work on a matrix of any size (or even any type, not
just integers) for the logic may be the same when it applies to a
matrix of different size?
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
/*Rotate a 4*4 matrix of integers by 90 degrees clockwise.*/
void rotate(void *matrix, const int width){
int (*array)[4] = matrix;
int (*tmp)[4];
int i, j;
size_t n = width * width * sizeof **array;
if(tmp = malloc(n)){
for (i = 0; i < width; ++i)
for (j = 0; j < width; ++j)
*(*(tmp + i) + j) = *(*(array + i) + j);
for (i = 0; i < width; ++i)
for (j = 0; j < width; ++j)
*(*(array + j) + (width - 1 - i)) = *(*(tmp + i) + j);
free(tmp);
}
}
/*test*/
#include <stdio.h>
/*print the content of a matrix*/
void printa(void *matrix, const int width){
int (*array)[4] = matrix;
int i, j;
for (i = 0; i < width; ++i){
for (j = 0; j < width; ++j)
printf("%2d ", *(*(array + i) + j));
printf("\n");
}
}
#define WTH 4
int main(void){
int a[][WTH] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}};
printa(a, WTH);
printf("\n");
rotate(a, WTH);
printa(a, WTH);
printf("\n");
rotate(a, WTH);
printa(a, WTH);
printf("\n");
rotate(a, WTH);
printa(a, WTH);
printf("\n");
rotate(a, WTH);
printa(a, WTH);
printf("\n");
return 0;
}
$ cc -ansi -pedantic -Wall -W rotate.c
rotate.c: In function `rotate':
rotate.c:13: warning: suggest parentheses around assignment used as
truth value
$ ./a.out
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1
4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
$ 8 10654
lovecreatesbeauty wrote:
I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.
It's OT but ...
"rotate by 90 degrees" is called a transposition. You don't need a
temp, hint: the new location for a value at x,y is the new destination
for a value at y,x.
Tom
Tom St Denis wrote:
lovecreatesbeauty wrote:
I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.
It's OT but ...
"rotate by 90 degrees" is called a transposition. ...
You mean Outright Tripe? They're not even in the same equivalence
class. ;-)
--
Peter
lovecreatesbeauty wrote:
I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency?
Can the copy be saved?
Not sure what that means.
Comments on it are welcome.
Can I extend it to work on a matrix of any size (or even any type, not
just integers) for the logic may be the same when it applies to a
matrix of different size?
Yes.
#include <stddef.h>
You don't need this as size_t is supplied by both of the following
headers.
#include <stdlib.h>
#include <string.h>
/*Rotate a 4*4 matrix of integers by 90 degrees clockwise.*/
void rotate(void *matrix, const int width){
int (*array)[4] = matrix;
int (*tmp)[4];
int i, j;
size_t n = width * width * sizeof **array;
size_t n = width * sizeof *array;
if(tmp = malloc(n)){
Given that the matrix is relatively small, just create a temp locally.
for (i = 0; i < width; ++i)
for (j = 0; j < width; ++j)
*(*(tmp + i) + j) = *(*(array + i) + j);
Much clearer is...
tmp[i][j] = array[i][j];
But you can replace that whole thing with...
memcpy(tmp, array, n);
>
for (i = 0; i < width; ++i)
for (j = 0; j < width; ++j)
*(*(array + j) + (width - 1 - i)) = *(*(tmp + i) + j);
array[j][width - 1 -i] = tmp[i][j];
free(tmp);
}
}
Just an alternative...
#include <stddef.h>
#define countof(x) ((size_t) (sizeof (x) / sizeof *(x)))
void rotate(int array[][4])
{
size_t i, mi;
size_t j, mj;
size_t width = countof(array[0]);
for (i = 0, mi = width; i < mi--; i++)
for (j = 0, mj = width; j < mj--; j++)
{
int tmp = array[ i][ j];
array[ i][ j] = array[mj][ i];
array[mj][ i] = array[mi][mj];
array[mi][mj] = array[ j][mi];
array[ j][mi] = tmp;
}
}
--
Peter
Tom St Denis wrote:
lovecreatesbeauty wrote:
>>I write a function to rotate a matrix by 90 degrees clockwise, this function works on a matrix of specific size, for example, it rotates a 4*4 matrix of integers in the following code. The function makes one more copy of the original matrix, how is the efficiency? Can the copy be saved? Comments on it are welcome.
It's OT but ...
"rotate by 90 degrees" is called a transposition. [...]
Well, I can't say "No, it's not" because the very fact
that you describe the maneuver as a transposition demonstrates
that the maneuver "is called" a transposition by at least one
person, to wit, you.
"Is *correctly* called" would be a different matter.
Myself, I call it "Haddocks' Eyes."
--
Eric Sosman es*****@acm-dot-org.invalid
Peter Nilsson wrote:
Just an alternative...
#include <stddef.h>
#define countof(x) ((size_t) (sizeof (x) / sizeof *(x)))
void rotate(int array[][4])
{
size_t i, mi;
size_t j, mj;
size_t width = countof(array[0]);
for (i = 0, mi = width; i < mi--; i++)
for (j = 0, mj = width; j < mj--; j++)
{
int tmp = array[ i][ j];
array[ i][ j] = array[mj][ i];
array[mj][ i] = array[mi][mj];
array[mi][mj] = array[ j][mi];
array[ j][mi] = tmp;
}
}
Yes, it's better.
Peter Nilsson wrote:
lovecreatesbeauty wrote:
Can I extend it to work on a matrix of any size (or even any type, not
just integers) for the logic may be the same when it applies to a
matrix of different size?
Yes.
How can you do this? In your later example, the size info is tied to
the type declaration of the parameter of the function, though that size
of the array is not seen inside the function.
void rotate(int array[][4])
This function accepts a 4*4 array of integers. Can it accept a 3*3
array or a 40*40 array? Can it be changed to accept an array of any
size.
"Tom St Denis" <to********@gmail.comwrites:
lovecreatesbeauty wrote:
I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.
It's OT but ...
"rotate by 90 degrees" is called a transposition. You don't need a
temp, hint: the new location for a value at x,y is the new destination
for a value at y,x.
[Still more OT, but]
Err.. no. Consider
1 2 3 4
0 1 2 3
0 0 1 2
0 0 0 1
Rotating by 90 degrees clockwise:
0 0 0 1
0 0 1 2
0 1 2 3
1 2 3 4
Transposition (a_{x,y} <- a_{y,x}):
1 0 0 0
2 1 0 0
3 2 1 0
4 3 2 1
Rotating by 90 degrees clockwise is the same as
transposition plus inversion of row numbering, i.e.,
a_{x,y} <- a_{n-y, x},
where n is the size of the matrix.
The cost is ~n^2, same as writing the matrix in the first
place. Hence, unless your matrices are really large,
I won't bother much about optimising. If you have large
matrices and fewer than ~n^2 calls for matrix elements, you
might be better off without performing the rotation at all,
but instead using a trivial function get_rotated(a, x, y),
returning a_{n-y,x}.
Best,
Jakob
lovecreatesbeauty wrote:
I write a function to rotate a matrix by 90 degrees clockwise, this
function works on a matrix of specific size, for example, it rotates a
4*4 matrix of integers in the following code. The function makes one
more copy of the original matrix, how is the efficiency? Can the copy
be saved? Comments on it are welcome.
Can I extend it to work on a matrix of any size (or even any type, not
just integers) for the logic may be the same when it applies to a
matrix of different size?
you can do this with only one temp variable...dividing the array into a
set of 4 quadrents.
to rotate some x,y...y,-x...-x,-y...-y,x you would just use 3 swaps
//three constant time operations
swap(x,y,y,-x)
swap(-x,-y,x,y)
swap(-y,x,x,y)
Repeat this process for each element in one quadrent (loop n/4 times)
thus this operates in linear time and linear space:-) This discussion thread is closed Replies have been disabled for this discussion. Similar topics
2 posts
views
Thread by JustSomeGuy |
last post: by
|
21 posts
views
Thread by Nik Coughlin |
last post: by
|
2 posts
views
Thread by Peter Proost |
last post: by
|
1 post
views
Thread by iwdu15 |
last post: by
|
3 posts
views
Thread by Eduard Witteveen |
last post: by
|
3 posts
views
Thread by Diego F. |
last post: by
|
5 posts
views
Thread by Gina_Marano |
last post: by
|
13 posts
views
Thread by =?Utf-8?B?dmlubw==?= |
last post: by
| | | | | | | | | | | |