algorithm needed

Quote:

---

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");
}

---

---

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. :thumb

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.

---

Quote:

---

Originally posted by souldog
uj_. why don't you plug you algorithm in there and see how it compares.

---

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];

---

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

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];

---

---

that is what the template code ends up with after it has compiled.
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;
                }
        }
}

---

Quote:

---

Originally posted by ChaMadness
I tried my own "vision" of the solution, please try it and tell me what you think.

---

It's the same principle as I've used (post 53) but it's generalized for the NxM matrix situation.

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.

Quote:

---

If you're interested in speed I think there's still room for simplifications in your 'walking' loop.

---

Ok.. _uj!
Let's Optimize the C# ZigZag walker.
Any suggestions to start with?

Quote:

---

Originally posted by ChaMadness
Ok.. _uj!
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.

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.