Printable View
hi, i need algorithm to read the elements of an 8 x 8 matrix in a zigzag way. and also want the antizigzag algorithm to recover the elements.
i am giving link below..... that will show how actually i want to read the elemnts of the matrix.
http://www.ascc.net/nl/84/1110/05.html
there is a figure which shows the zigzag scan.
can you suggest any algorithm how to read and recover (anti zigzag) the elements in that way???
thanks
let me put my question in a simpler way,i have a 8 x 8 matrix.... from that matrix i want to read the elements like the link below and want to store in a 1-D buffer .
http://www.ascc.net/nl/84/1110/turn.gif
of course the elements could be anything(positive/negative/fraction)
can anybody suggest algorithm/pseuodocode plz
There is a function used to show that NxN has the same
cardinality as N (Here N is the set of natural numbers starting at
zero)
consider a point in NxN, <m,n>, then
f(m,n) = 1/2[(m+n)^2 +3m+n] defines a one-to-one onto relationship
between the desired sets.
This function "moves" in the zig-zag pattern you want.
so given an 8x8 matrix (however you implement that) I will
assume you access it as your_matrix[m][n], then the assignement
to a vector would be
first you need to compute a number
int j = (7 >= m+n ? 0:(m+n - 7));
for(int i = 1; i < (7 >= m+n ? 0:(m+n - 7)); i++)
j += 2i ;
your_vector[1/2((m+n)^2 +3m+n) - j] = your_matrix[m][n]
any way this is the idea
Looks like you are involved some way in image codecs.
In so, the better way is to have another 8x8 matrix for storing appropriate indexes.
for eg for 4x4 matrix you would have used the following
4x4 matrix
Zig Zag Seq:
0 1 5 6
2 4 7 9
3 8 10 11
Index Matrix
0 1 4 8
5 2 3 6
9 10 7 11
Then the loop will be
for (i=0 to 7
j= 0 to 7
Array[i * 8 + j] = Matrix[Index[i][j]]
Atleast the idea is correct
Regards
hi souldog,
your given function is interesting. but it is not giving me the correct result.
i wrote a small code for this.......
Code:#include<stdio.h>
int main()
{
int my_vector[65];//buffer
int my_matrix[8][8] = { { 0,1,5,6,14,15, 27, 28 },
{ 2,4,7,13,16,26,29,42},
{ 3,8,12,17,25,30,41,43},
{ 9,11,18,24,31,40,44,53},
{ 10,19,23,32,39,45,52,54},
{ 20,22,33,38,46,51,55,60},
{ 21,34,37,47,50,56,59,61},
{ 35,36,48,49,57,58,62,63}
};
for(int m=0;m<7;m++)
for(int n =0;n<7;n++)
{
int j = (7 >= m+n ? 0 : (m+n - 7));
for(int i = 1; i < (7 >= m+n ? 0 : (m+n - 7)); i++)
j += 2*i ;
my_vector[((m+n)*(m+n)+3*m+n)/(2) - j] = my_matrix[m][n];
}
for(m=0;m<64;m++) printf("%d\n",my_vector[m]);
return 0;
}
if i read from my_matrix[][] in a zigzag way then my_vector should print 1,2,3,4,5...........,63 is not it??? but its not giving that result...... some where there is mistake. its not reading in a zigzag way???????????
To nsh123
-----------------------
although i could not understand what exactly you wanted to mean by your example .......but i guess you want to creat a matrix(index matrix??) whose elements are the number in which way they are being acessed....so basically there would be a 8x8 index matrix i have to define at the beginig of the code.
plz can you explain more by a small code??
thanks
You are perfectly on track !!!Quote:
To nsh123
-----------------------
although i could not understand what exactly you wanted to mean by your example .......but i guess you want to creat a matrix(index matrix??) whose elements are the number in which way they are being acessed....so basically there would be a 8x8 index matrix i have to define at the beginig of the code.
plz can you explain more by a small code??
The code posted earlier is exactly what is required.
To make it more clear:
You were trying to generate the zig-zag sequence algorithmically
And I have suggested to hard-code it in your code itself in the form of 8x8 matrix.
Ofcourse assuming 8x8 the only type you deal with.
Regards,
Thats is because your indices are wrong.
I made the change ion the code below
The function works, but It could be cleaned up a bit.
Quote:
Originally posted by maxima
hi souldog,
your given function is interesting. but it is not giving me the correct result.
i wrote a small code for this.......
Code:#include<stdio.h>
int main()
{
int my_vector[65];//buffer
int my_matrix[8][8] = { { 0,1,5,6,14,15, 27, 28 },
{ 2,4,7,13,16,26,29,42},
{ 3,8,12,17,25,30,41,43},
{ 9,11,18,24,31,40,44,53},
{ 10,19,23,32,39,45,52,54},
{ 20,22,33,38,46,51,55,60},
{ 21,34,37,47,50,56,59,61},
{ 35,36,48,49,57,58,62,63}
};
for(int m=0;m<8;m++) //CHANGE UPPER LIMIT TO EIGHT
for(int n =0;n<8;n++) //CHANGE UPPER LIMIT TO EIGHT
{
int j = (7 >= m+n ? 0 : (m+n - 7));
for(int i = 1; i < (7 >= m+n ? 0 : (m+n - 7)); i++)
j += 2*i ;
my_vector[((m+n)*(m+n)+3*m+n)/(2) - j] = my_matrix[m][n];
}
for(m=0;m<64;m++) printf("%d\n",my_vector[m]);
return 0;
}
if i read from my_matrix[][] in a zigzag way then my_vector should print 1,2,3,4,5...........,63 is not it??? but its not giving that result...... some where there is mistake. its not reading in a zigzag way???????????
To nsh123
-----------------------
although i could not understand what exactly you wanted to mean by your example .......but i guess you want to creat a matrix(index matrix??) whose elements are the number in which way they are being acessed....so basically there would be a 8x8 index matrix i have to define at the beginig of the code.
plz can you explain more by a small code??
thanks
This is a prodecural approach using stepwise refinement.
Say you have two indexes i and j. The start condition is i=j=0 and the end condition is i=j=7. The indexes can 'move' in two diagonal directions diag_up and diag_down. There are four 'borders' that can be reached border_1 to border_4. When a border is reach the indexes can be advanced in four ways, advance_1 to advance_4 and the direction changes.
In pseudo code this translates to,
What remains is to identify the actual index increments/decrements. For example diag_up is i++, j--. Lim_1 is j==0. Advance_1 is i++.Code:boolean up = true; // direction
int i=j=0; // start
while (!(i == 7) && (j ==7 )) { // stop
if (border_1()) { // a border is reached
advance_1(); up = !up; // advance and change direction
} else if (border_2()) {
advance_2(); up = !up;
} else if (border_3()) {
advance_3(); up = !up;
} else if (border_4()) {
advance_4(); up = !up;
} else { // no border
if (up) diag_up(); else diag_down(); // cont. is same dir.
}
}
Well, this is the first refinement. :D You have to change the pseudocode a little because you can reach two borders at the same time. As a matter of fact one such two-border position constitutes the end criteria.Quote:
Originally posted by _uj
This is a prodecural approach using stepwise refinement.
Well, I have already given the function which will do what
the op wants, if he/she can manage to implement the code.
however, I would recommend using nsh123's suggestion and
just implement some lookup tables.
This is a simple to understand procedural version. Say you have an 8x8 chessboard. You start in the 0,0 position then you walk diagonal up. If you land outside the chessboard you correct the position and change walking direction. You can land outside the chessboard in 5 different places,
Code:int d=1; // start direction (diagonal up)
int i=0, j=0; // index
for (int k=0; k<64; k++) { // all chessboard squares
// TRACE(STR(k) + ":" + STR(i) + "/" + STR(j));
output_buffer[k] = chess_board[i,j];
i += d; // next index positions
j -= d;
if (j < 0) { // outside top
j = 0;
d = -d; // change direction
} else if (i < 0) {
if (j > 7) { // outside left and bottom
j = 7;
i += 2;
} else { // outside left
i = 0;
}
d = -d;
} else if (i > 7) { // outside right
i = 7;
j += 2;
d = -d;
} else if (j > 7) { // outside bottom
j = 7;
i += 2;
d = -d;
}
}
To souldog
-----------
yes...i did mistake in the limit.....now its working... thanks
chessboard algorithm given by ._uj is also good but i have to think about chessboard algorithm a little bit.
To nash
------------------
i think nash's suggestion would be the simplest one .
so, i want to implement that....... but getting some trouble.
i am writing below what i am thinking.
as you know i am expecting in my buffer[] this sequence(i.e zigzag)Code:
my_matrix[8][8] =
| 30 0 0 0 0 0 0 0|
| -7 8 1 1 0 0 0 0|
|-11 6 0 1 0 0 0 0|
| -5 -3 0 0 0 0 0 0|
| -7 -3 2 0 0 0 0 0|
| -4 4 0 0 0 0 0 0|
| -1 0 1 0 0 0 0 0|
| -3 1 0 0 0 0 0 0|
my_index[8][8] =
| 1 | 2 | 6 | 7 | 15 | 16 | 28 | 29 |
| 3 | 5 | 8 | 14 | 17 | 27 | 30 | 43 |
| 4 | 9 | 13 | 18 | 26 | 31 | 42 | 44 |
| 10 | 12 | 19 | 25 | 32 | 41 | 45 | 54 |
| 11 | 20 | 24 | 33 | 40 | 46 | 53 | 55 |
| 21 | 23 | 34 | 39 | 47 | 52 | 56 | 61 |
| 22 | 35 | 38 | 48 | 51 | 57 | 60 | 62 |
| 36 | 37 | 49 | 50 | 58 | 59 | 63 | 64 |
// my_index[8][8] is the look up table/zigzag table that u r suugesting.
your quote
can you explicitly tell me which way i would fetch the elements form the my_matrix[][] by looking index table?????
Quote:
Then the loop will be
for (i=0 to 7
j= 0 to 7
Array[i * 8 + j] = Matrix[Index[i][j]]
30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0
0 0 0 0 0 0 0 -3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
You my_index matrix is wrong, look at nsh's post again.
I've run the chessboard algoritm with your index matrix. If you run the code snippet below you'll see that the elements come out in the expected order, namely: 1,2,3, ....... 63,64. Now you just have to plug in my_matrix instead and assign the elements to a 64 element int array using the k index. Use it if you like, it does the expected.Quote:
Originally posted by maxima
chessboard algorithm given by ._uj is also good but i have to think about chessboard algorithm a little bit.
PS. TRACE and STR are just a way to print numbers.Code:int my_index[8][8] =
{{1 , 2 , 6 , 7 , 15 , 16 , 28 , 29},
{3 , 5 , 8 , 14 , 17 , 27 , 30 , 43},
{4 , 9 , 13 , 18 , 26 , 31 , 42 , 44},
{10 , 12 , 19 , 25 , 32 , 41 , 45 , 54},
{11 , 20 , 24 , 33 , 40 , 46 , 53 , 55},
{21 , 23 , 34 , 39 , 47 , 52 , 56 , 61},
{22 , 35 , 38 , 48 , 51 , 57 , 60 , 62},
{36 , 37 , 49 , 50 , 58 , 59 , 63 , 64}};
for (int d=1,i=0,j=0,k=0; k<64; k++) { // all chessboard squares
TRACE(STR(my_index[j][i])); // println
i += d; // next index positions
j -= d;
if (j < 0) { // outside top
j = 0;
d = -d; // change direction
} else if (i < 0) {
if (j > 7) { // outside left and bottom
j = 7;
i += 2;
} else { // outside left
i = 0;
}
d = -d;
} else if (i > 7) { // outside right
i = 7;
j += 2;
d = -d;
} else if (j > 7) { // outside bottom
j = 7;
i += 2;
d = -d;
}
}
To make the algoritm general and work for all 'chessboard' sizes like 9x9 you'll have to take care of the 'outside right and top' case too which would be easy.
i am sorry.....its not working properly. only changing the index will not be sufficient .... i checked again.....somewher there is some problem......Quote:
To souldog
-----------
yes...i did mistake in the limit.....now its working... thanks
To _uj
------------------
yes it is going into buffer in the correct way... but i want to reconstruct the matrix from the buffer again...
ok what i wrote giving below...
Code:
#include<stdio.h>
int main()
{
int output_buffer[64];
int new_matrix[8][8];
int my_index[8][8] =
{{1 , 2 , 6 , 7 , 15 , 16 , 28 , 29},
{3 , 5 , 8 , 14 , 17 , 27 , 30 , 43},
{4 , 9 , 13 , 18 , 26 , 31 , 42 , 44},
{10 , 12 , 19 , 25 , 32 , 41 , 45 , 54},
{11 , 20 , 24 , 33 , 40 , 46 , 53 , 55},
{21 , 23 , 34 , 39 , 47 , 52 , 56 , 61},
{22 , 35 , 38 , 48 , 51 , 57 , 60 , 62},
{36 , 37 , 49 , 50 , 58 , 59 , 63 , 64}};
for (int d=1,i=0,j=0,k=0; k<64; k++)
{
output_buffer[k] = my_index[j][i];
i += d;
j -= d;
if (j < 0) {
j = 0;
d = -d; // change direction
} else if (i < 0) {
if (j > 7) { // outside left and bottom
j = 7;
i += 2;
} else { // outside left
i = 0;
}
d = -d;
} else if (i > 7) { // outside right
i = 7;
j += 2;
d = -d;
} else if (j > 7) { // outside bottom
j = 7;
i += 2;
d = -d;
}
}
for( k=0;k<64;k++)
printf("%d\t",output_buffer[k]);
printf("\n\n\n");
/* ---reconstruction of the matrix from the output buffer -----------------*/
// this part(anti-zigzag ) is not reconstructing the matrix.
for ( d=1,i=0,j=0,k=0; k<64; k++)
{
new_matrix[j][i] = output_buffer[k];
i += d;
j -= d;
if (j < 0) {
j = 0;
d = -d; // change direction
} else if (i < 0) {
if (j > 7) { // outside left and bottom
j = 7;
i += 2;
} else { // outside left
i = 0;
}
d = -d;
} else if (i > 7) { // outside right
i = 7;
j += 2;
d = -d;
} else if (j > 7) { // outside bottom
j = 7;
i += 2;
d = -d;
}
}
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
printf("%d\t",new_matrix[j][i]);
}
printf("\n");
}
}
That is because it zig_zags in the opposite direction. So you
need to plug-in the transpose
But as far as speed goes, you are probably better with a lookPHP Code:int my_transpose_matrix[8][8] = { { 0, 2, 3, 9, 10,20,21,35},
{ 1, 4, 8, 11,19,22,34,36},
{ 5, 7, 12, 18,23,33,37,48},
{ 6, 13, 17, 24,32,38,47,49},
{ 14, 16, 25, 31,39,46,50,57},
{ 15, 26, 30, 40,45,51,56,58},
{ 27, 29, 41, 44,52,55,59,62},
{ 38, 42, 43, 53,54,60,61,63}
};
up table, although you can use this function to generate one for any size of matrix
OOPS. You are right. Give me a second and I will fix it. That is if
you are really going to use it?
I am deeply ashamed of myself :sick: :sick: :blush:
yes i am interested to use the look up table.
thats why, i gave in one of mine previous post two matrix.
my_matrix[8][8]
and
my_index[8][8];
i have given the numbering in my_index[8][8] by looking the zigzag control flow in the my_matrix[8][8].
so my_index[8][8] contains 1,2,3,.....63
i thought this is the look-up table or index table( but i have been opposed by Marc G.)
anyway, if i am correctly defined my my_matrix[][] and my_index[][]
then how can i acesses the elements just by looking index-table[][]???? what is the mapping between them??
ALL i need to do is , i first push the zigzag elements into the buffer and then from the buffer i want to create the matrix again
I don't have time to test now because it's friday. But intutively I think you have to do this in anti-zigzag,
new_matrix[fj(k)][fi(k)] = output_buffer[f(i,j)];
It's just to define f(i,j), fj(k) and fi(k). It's probably easy. I'll give it a shot later.
Well, It turns out the function I used does not zig-zag, but
moves along the diagonals always in the same order.
So I changed the order on odd diagonals (m+n odd)
PHP Code:using namespace std;
int GetIndex(const int m, const int n)
{
//after move past the main diagonal, need to account for
//missing terms from all of NxN
int j(7 >= m+n ? 0 : (m+n - 7));
for(int i = 0; i < (7 >= m+n ? 0 : (m+n - 7)); i++)
j += 2*i ;
return ((m+n)*(m+n)+3*m+n)/(2) - j;
}
int main(int argc, char *argv[])
{
int my_vector[64];//buffer
int my_matrix[8][8] = { { 0, 1, 5, 6, 14, 15, 27, 28 },
{ 2, 4, 7, 13, 16, 26, 29, 42},
{ 3, 8, 12, 17, 25, 30, 41, 43},
{ 9, 11, 18, 24, 31, 40, 44, 53},
{ 10, 19, 23, 32, 39, 45, 52, 54},
{ 20, 22, 33, 38, 46, 51, 55, 60},
{ 21, 34, 37, 47, 50, 56, 59, 61},
{ 35, 36, 48, 49, 57, 58, 62, 63}
};
for(int m=0;m<8;m++)
for(int n =0;n<8;n++)
{
//change direction on odd diagonals
my_vector[GetIndex(m,n)] = my_matrix[1 == (m+n)%2 ? m:n][1 == (m+n)%2 ? n:m];
}
for(int m=0;m<64;m++) printf("%d ",my_vector[m]);
system("PAUSE");
return 0;
}
and here is a simplified form
PHP Code:for(int m=0;m<8;m++)
for(int n =0;n<8;n++)
{
my_vector[((m+n)*(m+n)+3*(1 == (m+n)%2 ? m:n)+(1 == (m+n)%2 ? n:m))/(2) - ( (7 >= m+n) ? 0 :( (m+n - 7)*(m+n - 7)))] = my_matrix[m][n];
}
Simplified? You mean shortened...
No, simplified. A loop which was not needed was removed.Quote:
Originally posted by CornedBee
Simplified? You mean shortened...
By the way, you just change the inequality to get the matrix back
PHP Code:for(int m=0;m<8;m++)
for(int n =0;n<8;n++)
{
my_matrix[m][n] = my_vector[((m+n)*(m+n)+3*(1 == (m+n)%2 ? m:n)+(1 == (m+n)%2 ? n:m))/(2) - ( (7 >= m+n) ? 0 :( (m+n - 7)*(m+n - 7)))];
}
Well I've thought about it and this is what I would try first (not tested),Quote:
Originally posted by _uj
I don't have time to test now because it's friday. But intutively I think you have to do this in anti-zigzag,
new_matrix[fj(k)][fi(k)] = output_buffer[f(i,j)];
It's just to define f(i,j), fj(k) and fi(k). It's probably easy. I'll give it a shot later.
new_matrix[k/8][k%8] = output_buffer[j*8 + i];
This should inverse the doings of the first algoritm.
So it seems we are implementing slightly different versions
of this algorithm _uj. Any way I go to thinking about this problem.
here is an implementation using template metaprogramming to
try and unrole the loops.
PHP Code:
template<int I, int n>
class Assign_Matrix_Entry_To_Vector_Entry {
public:
static inline void assign(const int m, std::vector<double>& dest, const std::vector<std::vector<double> >& src)
{
dest[((m+n)*(m+n)+3*(1 == (m+n)%2 ? m:n)+(1 == (m+n)%2 ? n:m))/(2) - ( ((I - 1) >= m+n) ? 0 :( (m+n - (I - 1))*(m+n - (I - 1))))] = src[m][n];
}
};
template<int I, int J>
class Matrix_To_Zig_Zag_VectorLoop {
private:
enum { go = (J < I - 1)};
public:
static inline void loop(const int first_index, std::vector<double>& dest, const std::vector<std::vector<double> >& src)
{
Assign_Matrix_Entry_To_Vector_Entry<I ,J>::assign(first_index, dest, src);
Matrix_To_Zig_Zag_VectorLoop<go ? I: -1, go ? (J+1) : -1>::loop(first_index, dest, src);
}
};
class Matrix_To_Zig_Zag_VectorLoop<-1,-1> {
public:
static inline void loop(const int first_index, std::vector<double>& dest, const std::vector<std::vector<double> >& src)
{
}
};
template<int S, int N>
class Matrix_To_Zig_Zag_Vector {
private:
enum { go = (N > 1)};
public:
static inline void assign(std::vector<double>& dest, const std::vector<std::vector<double> >& src)
{
Matrix_To_Zig_Zag_VectorLoop<S,0>::loop(N-1, dest, src);
Matrix_To_Zig_Zag_Vector<go ? S : -1,go ? N-1: -1>::assign(dest, src);
}
};
class Matrix_To_Zig_Zag_Vector<-1, -1> {
public:
static inline void assign(std::vector<double>& dest, const std::vector<std::vector<double> >& src)
{
}
};
template<int I, int n>
class Assign_Vector_Entry_To_Matrix_Entry {
public:
static inline void assign(const int m, std::vector<std::vector<double> >& dest, const std::vector<double>& src)
{
dest[m][n] = src[((m+n)*(m+n)+3*(1 == (m+n)%2 ? m:n)+(1 == (m+n)%2 ? n:m))/(2) - ( ((I - 1) >= m+n) ? 0 :( (m+n - (I - 1))*(m+n - (I - 1))))];
}
};
template<int I, int J>
class Zig_Zag_Vector_To_MatrixLoop {
private:
enum { go = (J < I - 1)};
public:
static inline void loop(const int first_index, std::vector<std::vector<double> >& dest, const std::vector<double>& src)
{
Assign_Vector_Entry_To_Matrix_Entry<I ,J>::assign(first_index, dest, src);
Zig_Zag_Vector_To_MatrixLoop<go ? I: -1, go ? (J+1) : -1>::loop(first_index, dest, src);
}
};
class Zig_Zag_Vector_To_MatrixLoop<-1,-1> {
public:
static inline void loop(const int first_index, std::vector<std::vector<double> >& dest, const std::vector<double>& src)
{
}
};
template<int S, int N>
class Zig_Zag_Vector_To_Matrix {
private:
enum { go = (N > 1)};
public:
static inline void assign(std::vector<std::vector<double> >& dest, const std::vector<double>& src)
{
Zig_Zag_Vector_To_MatrixLoop<S,0>::loop(N-1, dest, src);
Zig_Zag_Vector_To_Matrix<go ? S : -1,go ? N-1: -1>::assign(dest, src);
}
};
class Zig_Zag_Vector_To_Matrix<-1, -1> {
public:
static inline void assign(std::vector<std::vector<double> >& dest, const std::vector<double>& src)
{
}
};
int main(int argc, char *argv[])
{
std::vector<std::vector<double> > my_matrix;
double row1[] ={ 0, 1, 5, 6, 14, 15, 27, 28 };
my_matrix.push_back(std::vector<double>(row1, row1 + sizeof(row1)/sizeof(row1[0])));
double row2[] = { 2, 4, 7, 13, 16, 26, 29, 42};
my_matrix.push_back(std::vector<double>(row2, row2 + sizeof(row2)/sizeof(row2[0])));
double row3[8] = { 3, 8, 12, 17, 25, 30, 41, 43};
my_matrix.push_back(std::vector<double>(row3, row3 + sizeof(row3)/sizeof(row3[0])));
double row4[8] = { 9, 11, 18, 24, 31, 40, 44, 53};
my_matrix.push_back(std::vector<double>(row4, row4 + sizeof(row4)/sizeof(row4[0])));
double row5[8] = { 10, 19, 23, 32, 39, 45, 52, 54};
my_matrix.push_back(std::vector<double>(row5, row5 + sizeof(row5)/sizeof(row5[0])));
double row6[8] = { 20, 22, 33, 38, 46, 51, 55, 60};
my_matrix.push_back(std::vector<double>(row6, row6 + sizeof(row6)/sizeof(row6[0])));
double row7[8] = { 21, 34, 37, 47, 50, 56, 59, 61};
my_matrix.push_back(std::vector<double>(row7, row7 + sizeof(row7)/sizeof(row7[0])));
double row8[8] = { 35, 36, 48, 49, 57, 58, 62, 63};
my_matrix.push_back(std::vector<double>(row8, row8 + sizeof(row8)/sizeof(row8[0])));
for(int m=0;m<8;m++)
{
for(int n =0;n<8;n++)
{
printf("%1.0f ",my_matrix[m][n]);
}
printf("\n");
}
std::vector<double> my_vector(64, 0.0);
Matrix_To_Zig_Zag_Vector<8, 8>::assign(my_vector, my_matrix);
/*
for(int m=0;m<8;m++)
for(int n =0;n<8;n++)
{
//change direction on odd diagonals
my_vector[((m+n)*(m+n)+3*(1 == (m+n)%2 ? m:n)+(1 == (m+n)%2 ? n:m))/(2) - ( (7 >= m+n) ? 0 :( (m+n - 7)*(m+n - 7)))] = my_matrix[m][n];
}
*/
for(int m=0;m<64;m++) printf("%1.0f ",my_vector[m]);
printf("\n\n");
/*
for(int m=0;m<8;m++)
for(int n =0;n<8;n++)
{
//change direction on odd diagonals
my_matrix[m][n] = my_vector[((m+n)*(m+n)+3*(1 == (m+n)%2 ? m:n)+(1 == (m+n)%2 ? n:m))/(2) - ( (7 >= m+n) ? 0 :( (m+n - 7)*(m+n - 7)))];
}
*/
Zig_Zag_Vector_To_Matrix<8,8>::assign(my_matrix, my_vector);
for(int m=0;m<8;m++)
{
for(int n =0;n<8;n++)
{
printf("%1.0f ",my_matrix[m][n]);
}
printf("\n");
}
system("PAUSE");
return 0;
}
Yes, I know and basically the OP should be able to solve it now but it's quite amusing to give algoritms like this a shot. I've a programmers soul (but no dog :)) and I'm new to C++ so I learn from it.Quote:
Originally posted by souldog
So it seems we are implementing slightly different versions
of this algorithm _uj.
Does anyone know how I can get a listing file from Dev-C++
I would like to look at assembly
That's beautiful code there, souldog! I'm gonna need some time to look it over...
But if you want to look at the disassembly and still haven't found the way in Dev-C++ (which I don't know either), you could compile it and then take a look at something like dumppe or other dump tools. They usually have a -disasm switch, and you can pipe the output to a text file.
Thanks Galathaea, I would appreciate any pointers. That is my first
attempt at template metaprogramming. It is basically an adaptation
of a buble sort implementation I found.
Hi again, It's actually the way you print new_matrix that's wrong. You should change indexes in the loops above. The outer one should loop over j and the inner over i. Then it works. :thumbQuote:
Originally posted by maxima
To _uj
------------------
yes it is going into buffer in the correct way... but i want to reconstruct the matrix from the buffer again...
ok what i wrote giving below...
......................................
Code:for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
printf("%d\t",new_matrix[j][i]);
}
printf("\n");
}
Well I decided to compare using the template meta programming
code to using normal loops or a lookup table. WOW! the template code is much
faster
I am using Dev-C++ 5.0 beta 8 (4.9.8.0) with Mingw/GCC 3.2
the template code wont compile on VC++ 6.0
(in milliseconds)
Normal loops
333.221
323.524
325.21
329.865
330.409
321.219
338.126
324.802
325.803
322.094
Index Lookup Table
63.9081
79.5333
67.4942
64.434
64.2503
63.9613
63.4255
64.0648
63.6991
64.0701
Template code
44.2549
43.9077
45.6625
47.0667
51.3528
52.8727
44.0614
44.8019
46.1657
43.3918
the code is
PHP Code:#include <Windows.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
template<int I, int n>
class Assign_Matrix_Entry_To_Vector_Entry {
public:
static inline void assign(const int m, std::vector<double>& dest, const std::vector<std::vector<double> >& src)
{
dest[((m+n)*(m+n)+3*(1 == (m+n)%2 ? m:n)+(1 == (m+n)%2 ? n:m))/(2) - ( ((I - 1) >= m+n) ? 0 :( (m+n - (I - 1))*(m+n - (I - 1))))] = src[m][n];
}
};
template<int I, int J>
class Matrix_To_Zig_Zag_VectorLoop {
private:
enum { go = (J < I - 1)};
public:
static inline void loop(const int first_index, std::vector<double>& dest, const std::vector<std::vector<double> >& src)
{
Assign_Matrix_Entry_To_Vector_Entry<I ,J>::assign(first_index, dest, src);
Matrix_To_Zig_Zag_VectorLoop<go ? I: -1, go ? (J+1) : -1>::loop(first_index, dest, src);
}
};
class Matrix_To_Zig_Zag_VectorLoop<-1,-1> {
public:
static inline void loop(const int first_index, std::vector<double>& dest, const std::vector<std::vector<double> >& src)
{
}
};
template<int S, int N>
class Matrix_To_Zig_Zag_Vector {
private:
enum { go = (N > 1)};
public:
static inline void assign(std::vector<double>& dest, const std::vector<std::vector<double> >& src)
{
Matrix_To_Zig_Zag_VectorLoop<S,0>::loop(N-1, dest, src);
Matrix_To_Zig_Zag_Vector<go ? S : -1,go ? N-1: -1>::assign(dest, src);
}
};
class Matrix_To_Zig_Zag_Vector<-1, -1> {
public:
static inline void assign(std::vector<double>& dest, const std::vector<std::vector<double> >& src)
{
}
};
template<int I, int n>
class Assign_Vector_Entry_To_Matrix_Entry {
public:
static inline void assign(const int m, std::vector<std::vector<double> >& dest, const std::vector<double>& src)
{
dest[m][n] = src[((m+n)*(m+n)+3*(1 == (m+n)%2 ? m:n)+(1 == (m+n)%2 ? n:m))/(2) - ( ((I - 1) >= m+n) ? 0 :( (m+n - (I - 1))*(m+n - (I - 1))))];
}
};
template<int I, int J>
class Zig_Zag_Vector_To_MatrixLoop {
private:
enum { go = (J < I - 1)};
public:
static inline void loop(const int first_index, std::vector<std::vector<double> >& dest, const std::vector<double>& src)
{
Assign_Vector_Entry_To_Matrix_Entry<I ,J>::assign(first_index, dest, src);
Zig_Zag_Vector_To_MatrixLoop<go ? I: -1, go ? (J+1) : -1>::loop(first_index, dest, src);
}
};
class Zig_Zag_Vector_To_MatrixLoop<-1,-1> {
public:
static inline void loop(const int first_index, std::vector<std::vector<double> >& dest, const std::vector<double>& src)
{
}
};
template<int S, int N>
class Zig_Zag_Vector_To_Matrix {
private:
enum { go = (N > 1)};
public:
static inline void assign(std::vector<std::vector<double> >& dest, const std::vector<double>& src)
{
Zig_Zag_Vector_To_MatrixLoop<S,0>::loop(N-1, dest, src);
Zig_Zag_Vector_To_Matrix<go ? S : -1,go ? N-1: -1>::assign(dest, src);
}
};
class Zig_Zag_Vector_To_Matrix<-1, -1> {
public:
static inline void assign(std::vector<std::vector<double> >& dest, const std::vector<double>& src)
{
}
};
int main(int argc, char *argv[])
{
std::vector<std::vector<double> > my_matrix;
double row1[] ={ 0, 1, 5, 6, 14, 15, 27, 28 };
my_matrix.push_back(std::vector<double>(row1, row1 + sizeof(row1)/sizeof(row1[0])));
double row2[] = { 2, 4, 7, 13, 16, 26, 29, 42};
my_matrix.push_back(std::vector<double>(row2, row2 + sizeof(row2)/sizeof(row2[0])));
double row3[8] = { 3, 8, 12, 17, 25, 30, 41, 43};
my_matrix.push_back(std::vector<double>(row3, row3 + sizeof(row3)/sizeof(row3[0])));
double row4[8] = { 9, 11, 18, 24, 31, 40, 44, 53};
my_matrix.push_back(std::vector<double>(row4, row4 + sizeof(row4)/sizeof(row4[0])));
double row5[8] = { 10, 19, 23, 32, 39, 45, 52, 54};
my_matrix.push_back(std::vector<double>(row5, row5 + sizeof(row5)/sizeof(row5[0])));
double row6[8] = { 20, 22, 33, 38, 46, 51, 55, 60};
my_matrix.push_back(std::vector<double>(row6, row6 + sizeof(row6)/sizeof(row6[0])));
double row7[8] = { 21, 34, 37, 47, 50, 56, 59, 61};
my_matrix.push_back(std::vector<double>(row7, row7 + sizeof(row7)/sizeof(row7[0])));
double row8[8] = { 35, 36, 48, 49, 57, 58, 62, 63};
my_matrix.push_back(std::vector<double>(row8, row8 + sizeof(row8)/sizeof(row8[0])));
//lookup table
std::vector<std::vector<int> > index_matrix;
int index_row1[] ={ 0, 1, 5, 6, 14, 15, 27, 28 };
index_matrix.push_back(std::vector<int>(index_row1, index_row1 + sizeof(index_row1)/sizeof(index_row1[0])));
int index_row2[] = { 2, 4, 7, 13, 16, 26, 29, 42};
index_matrix.push_back(std::vector<int>(index_row2, index_row2 + sizeof(index_row2)/sizeof(index_row2[0])));
int index_row3[8] = { 3, 8, 12, 17, 25, 30, 41, 43};
index_matrix.push_back(std::vector<int>(index_row3, index_row3 + sizeof(index_row3)/sizeof(index_row3[0])));
int index_row4[8] = { 9, 11, 18, 24, 31, 40, 44, 53};
index_matrix.push_back(std::vector<int>(index_row4, index_row4 + sizeof(index_row4)/sizeof(index_row4[0])));
int index_row5[8] = { 10, 19, 23, 32, 39, 45, 52, 54};
index_matrix.push_back(std::vector<int>(index_row5, index_row5 + sizeof(index_row5)/sizeof(index_row5[0])));
int index_row6[8] = { 20, 22, 33, 38, 46, 51, 55, 60};
index_matrix.push_back(std::vector<int>(index_row6, index_row6 + sizeof(index_row6)/sizeof(index_row6[0])));
int index_row7[8] = { 21, 34, 37, 47, 50, 56, 59, 61};
index_matrix.push_back(std::vector<int>(index_row7, index_row7 + sizeof(index_row7)/sizeof(index_row7[0])));
int index_row8[8] = { 35, 36, 48, 49, 57, 58, 62, 63};
index_matrix.push_back(std::vector<int>(index_row8, index_row8 + sizeof(index_row8)/sizeof(index_row8[0])));
LARGE_INTEGER Frequency;
if(!QueryPerformanceFrequency(&Frequency))
cout << "QueryPerformanceFrequency FAILED" << endl;
// Installed hardware does not support high-resolution counter
else
{
LARGE_INTEGER liStart;
LARGE_INTEGER liStop;
// Start time measurement
::QueryPerformanceCounter(&liStart);
// Do your processing
std::vector<double> my_vector(64, 0.0);
for(int k = 0; k < 10; k++)
{
// Start time measurement
::QueryPerformanceCounter(&liStart);
for(int l = 0; l < 100000; l++)
{
//uncomment this to test the template metaprogramming code
Matrix_To_Zig_Zag_Vector<8,8>::assign(my_vector, my_matrix);
Zig_Zag_Vector_To_Matrix<8,8>::assign(my_matrix, my_vector);
//uncomment this to test the normal loop code
/*
for(int m=0;m<8;m++)
for(int n =0;n<8;n++)
{
//change direction on even diagonals
my_vector[((m+n)*(m+n)+3*(1 == (m+n)%2 ? m:n)+(1 == (m+n)%2 ? n:m))/(2) - ( (7 >= m+n) ? 0 :( (m+n - 7)*(m+n - 7)))] = my_matrix[m][n];
}
for(int m=0;m<8;m++)
for(int n =0;n<8;n++)
{
//change direction on even diagonals
my_matrix[m][n] = my_vector[((m+n)*(m+n)+3*(1 == (m+n)%2 ? m:n)+(1 == (m+n)%2 ? n:m))/(2) - ( (7 >= m+n) ? 0 :( (m+n - 7)*(m+n - 7)))];
}
*/
//uncomment this to test lookup table
/*
for(int m=0;m<8;m++)
for(int n =0;n<8;n++)
{
//change direction on even diagonals
my_vector[index_matrix[m][n]] = my_matrix[m][n];
}
for(int m=0;m<8;m++)
for(int n =0;n<8;n++)
{
//change direction on even diagonals
my_matrix[m][n] = my_vector[index_matrix[m][n]];
}
*/
}
// Stop time measurement
QueryPerformanceCounter(&liStop);
LONGLONG llTimeDiff = liStop.QuadPart - liStart.QuadPart;
// To get duration in milliseconds
double dftDuration = (double) llTimeDiff * 1000.0 / (double) Frequency.QuadPart;
cout << dftDuration << endl;
}
}
//to prove it actually works
cout <<endl;
for(int g = 0; g < my_vector.size(); g++)
cout << my_vector[g] << " ";
cout << endl << endl;
for(int m=0;m<8;m++)
{
for(int n =0;n<8;n++)
{
cout << my_matrix[m][n] << " ";
}
cout << endl;
}
system("PAUSE");
return 0;
}
uj_. why don't you plug you algorithm in there and see how it compares.
From the gcc man pages, this should apply to MingW as well.
Quote:
If you only want some of the stages of compilation, you can
use -x (or filename suffixes) to tell gcc where to start,
and one of the options -c, -S, or -E to say where gcc is to
stop. Note that some combinations (for example, -x cpp-
output -E) instruct gcc to do nothing at all.
-c Compile or assemble the source files, but do not link.
The linking stage simply is not done. The ultimate
output is in the form of an object file for each source
file.
By default, the object file name for a source file is
made by replacing the suffix .c, .i, .s, etc., with .o.
Unrecognized input files, not requiring compilation or
assembly, are ignored.
-S Stop after the stage of compilation proper; do not
assemble. The output is in the form of an assembler
code file for each non-assembler input file specified.
By default, the assembler file name for a source file is
made by replacing the suffix .c, .i, etc., with .s.
Input files that don't require compilation are ignored.
-E Stop after the preprocessing stage; do not run the
compiler proper. The output is in the form of
preprocessed source code, which is sent to the standard
output.
Input files which don't require preprocessing are
ignored.
I haven't thought much about speed but in this special case I would probably use 'straight code' and put 64 assignments one after the other. No looping and no index calculations at all, like thisQuote:
Originally posted by souldog
uj_. why don't you plug you algorithm in there and see how it compares.
Code:output_buffer[0] = my_index[0][0];
output_buffer[1] = my_index[0][1];
output_buffer[2] = my_index[1][0];
output_buffer[3] = my_index[2][0];
output_buffer[4] = my_index[1][1];
//.
//.
output_buffer[63] = my_index[7][7];
yes, i have got the desired result usuing both the code(souldog and _uj)
its working properly. thanks
in fact i have nearly 5000 ...... 8x8 block matrix.
so i will use routines for zigzag and anti-zigzag......i will send matrix one after another. In zigzag routine i will use output buffer of size >>> static int output_buffer[5000 *64] and will store all values.....
i think i can manage now....
thanks
that is what the template code ends up with after it has compiled.Quote:
Originally posted by _uj
I haven't thought much about speed but in this special case I would probably use 'straight code' and put 64 assignments one after the other. No looping and no index calculations at all, like this
Code:output_buffer[0] = my_index[0][0];
output_buffer[1] = my_index[0][1];
output_buffer[2] = my_index[1][0];
output_buffer[3] = my_index[2][0];
output_buffer[4] = my_index[1][1];
//.
//.
output_buffer[63] = my_index[7][7];
At least that is the goal. Pretty nice:)
Hi Guys...
Interesting stuff you posted here!
I tried my own "vision" of the solution, please try it and tell me what you think. I know some of you don't like MicroSoft but I really didn't have time to convert my idea to C++.
If you succeed in converting the idea to C++ I would appreciate posting it here.
Let's keep thinking ;)
Code:using System;
namespace ZigZag
{
/// <summary>
/// Summary description for Class1.
/// </summary>
class MyApplication
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
int [][] Matrix = { new int [] { 0, 1, 5, 6,14,15,27,28},
new int [] { 2, 4, 7,13,16,26,29,42},
new int [] { 3, 8,12,17,25,30,41,43},
new int [] { 9,11,18,24,31,40,44,53},
new int [] {10,19,23,32,39,45,52,54},
new int [] {20,22,33,38,46,51,55,60},
new int [] {21,34,37,47,50,56,59,61},
new int [] {35,36,48,49,57,58,62,63}
};
System.Console.WriteLine("Reading Matrix: ");
int [] buffer = getBufferFromMatrix( Matrix );
System.Console.WriteLine("");
for(int i = 0; i < buffer.Length; i++)
{
System.Console.Write(" " + buffer[i].ToString() );
}
System.Console.WriteLine("\n\nPress RETURN to continue...\n\n Reverting buffer to Matrix: \n\n");
System.Console.Read();
Matrix = getMatrixFromBuffer( buffer );
for(int i = 0; i < Matrix.Length; i++)
{
int [] row = Matrix[i];
for(int j = 0; j < row.Length; j++)
{
System.Console.Write(row[j].ToString() + "\t");
}
System.Console.WriteLine("");
}
System.Console.WriteLine("\n\nPress RETURN to continue...\n\n");
System.Console.Read();
}
public static int [] getBufferFromMatrix( int [][] Matrix )
{
int zig = 0, zigLimit = Matrix.Length;
int zag = 0, zagLimit = Matrix[0].Length;
int zigWas = 0, zagWas = 0;
bool UpRightDirection = true;
int BufferLength = zigLimit * zagLimit;
int BufferIndex = 0;
int [] Buffer = new int [ BufferLength ];
while(BufferIndex < BufferLength)
{
Buffer[ BufferIndex ] = Matrix[zag][zig];
BufferIndex++;
zigWas = zig;
zagWas = zag;
if(UpRightDirection)
{ zig++; zag--; }
else { zig--; zag++; }
if(zig == zigLimit && zag != -1)
{ zig--; zag+=2; UpRightDirection = !UpRightDirection; }
else if(zig == -1 && zag != zagLimit)
{ zig++; UpRightDirection = !UpRightDirection; }
else if(zag == zagLimit)
{ zag--; zig+=2; UpRightDirection = !UpRightDirection; }
else if(zag == -1)
{ zag++; UpRightDirection = !UpRightDirection; }
else if(zig == zigLimit && zag == -1)
{ zig--; zag += 2; UpRightDirection = !UpRightDirection; }
else if(zig == -1 && zag == zagLimit)
{ zig+=1; zag--; UpRightDirection = !UpRightDirection; }
if(zig <= -1 || zig >= zigLimit) zig = zigWas;
if(zag <= -1 || zag >= zagLimit) zag = zagWas;
}
return Buffer;
}
public static int [][] getMatrixFromBuffer( int [] Buffer )
{
int zig = 0, zigLimit = (int) Math.Sqrt(Convert.ToDouble(Buffer.Length));
int zag = 0, zagLimit = Buffer.Length / zigLimit;
int zigWas = 0, zagWas = 0;
bool UpRightDirection = true;
int BufferLength = zigLimit * zagLimit;
int BufferIndex = 0;
int [][] Matrix = new int [zagLimit][];
for(int i = 0; i < Matrix.Length; i++)
Matrix[i] = new int[zigLimit];
while(BufferIndex < BufferLength)
{
Matrix[zag][zig] = Buffer[ BufferIndex ];
BufferIndex++;
zigWas = zig;
zagWas = zag;
if(UpRightDirection)
{ zig++; zag--; }
else { zig--; zag++; }
if(zig == zigLimit && zag != -1)
{ zig--; zag+=2; UpRightDirection = !UpRightDirection; }
else if(zig == -1 && zag != zagLimit)
{ zig++; UpRightDirection = !UpRightDirection; }
else if(zag == zagLimit)
{ zag--; zig+=2; UpRightDirection = !UpRightDirection; }
else if(zag == -1)
{ zag++; UpRightDirection = !UpRightDirection; }
else if(zig == zigLimit && zag == -1)
{ zig--; zag += 2; UpRightDirection = !UpRightDirection; }
else if(zig == -1 && zag == zagLimit)
{ zig+=1; zag--; UpRightDirection = !UpRightDirection; }
if(zig <= -1 || zig >= zigLimit) zig = zigWas;
if(zag <= -1 || zag >= zagLimit) zag = zagWas;
}
return Matrix;
}
}
}
It's the same principle as I've used (post 53) but it's generalized for the NxM matrix situation.Quote:
Originally posted by ChaMadness
I tried my own "vision" of the solution, please try it and tell me what you think.
You start in the upper left corner and walk in one diagonal direction. In each step you check if you've left the boundaries of the matrix. There are 6 different out-of-bound areas you can end up in (3 for each walking direction), and each represents a different way to re-enter the matrix. You do that and continue walking in the opposite diagonal direction. After N*M steps you stop because you're now at the lower right corner.
If you're interested in speed I think there's still room for simplifications in your 'walking' loop.
Ok.. _uj!Quote:
If you're interested in speed I think there's still room for simplifications in your 'walking' loop.
Let's Optimize the C# ZigZag walker.
Any suggestions to start with?
Well I really shouldn't spend more time on this but have you looked at my post 55. It's exactly the same principle as you're using.Quote:
Originally posted by ChaMadness
Ok.. _uj!
Let's Optimize the C# ZigZag walker.
Any suggestions to start with?
My version has 2 integer increments and 4 logical evaluations in each step (when a step stays inside the matrix which it often does). To generalize this to the N*M situation you'll have to replace the 7's with N or M depending on which boundary is checked. Also 64 should be replaced by the N*M number. Finally one of the 6 out-of-bound areas are missing and has to be included (it wasn't necessary in an 8*8 matrix).
The one further improvement I can see is to utilize that fact that depending on direction you only have to check for 3 out-of-bound areas. So instead of 4 logical evaluation in each step (that stays inside) you get just 3 evaluations. That's very close to optimum I would say.