Algorithms on matrix. Pointer/No pointer in the prototype issue.

  • (2 Pages)
  • +
  • 1
  • 2

26 Replies - 725 Views - Last Post: 24 February 2013 - 05:32 PM Rate Topic: -----

#1 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 17 February 2013 - 08:56 AM

Hi guys,
I'm tring to code an algorithm that given a square matrix of even dimension, transpone 2x2 submatrix in it
Example:
Posted Image

So, I written all the code (check below).

Problem is, I written it based on a matrix[ row ][ col ] logic, not with pointers , while the assignment requires that matrix dimension should be asked to the user.
Now, if write a function prototype like this
const int MAX_COLS = 100;
void transpose ( int matrix[ ][MAX_COLS], const int ROWS, const int COLS );


compiler won't do it's job, and if I choose a pointer logic I should rewrite all this from 0 ( and it's far more complicated to write it with pointers, I think ).

It's a frequent issue for me, it's happened before and I choosed always to practice with pointers because i was at the beginning with them.

Now it's startng to get annoying, so
Is there an easy way to fix this or should i go for the torture?



Here is the code I think should do the job (not tested).

void transpose ( int matrix[][ COLS ], const int ROWS, const int COLS )
{
	int temp;
	
	for ( int current_row = 0; current_row < ROWS; current_row = current_row + 2 )
	{
		for ( int current_col = current_row + 2; current_col < COLS; current_col = current_col + 2 )
		{

			temp = matrix[ current_row ][ current_col ];
			matrix[ current_row ][ current_col ] = matrix[ current_col ][ current_row ];
			matrix[ current_col ][ current_row ] = temp;

			temp = matrix[ current_row ][ current_col + 1 ];
			matrix[ current_row ][ current_col + 1] = matrix[ current_col ][ current_row + 1 ];
			matrix[ current_col ][ current_row + 1 ] = temp;

			temp = matrix[ current_row + 1 ][ current_col ];
			matrix[ current_row + 1 ][ current_col ] = matrix[ current_col + 1 ][ current_row ];
			matrix[ current_col + 1 ][ current_row ] = temp;

			temp = matrix[ current_row + 1 ][ current_col + 1];
			matrix[ current_row + 1 ][ current_col + 1 ] = matrix[ current_col + 1 ][ current_row + 1 ];
			matrix[ current_col + 1 ][ current_row + 1] = temp;
		}
	}
	
}

This post has been edited by domenico: 17 February 2013 - 08:57 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Algorithms on matrix. Pointer/No pointer in the prototype issue.

#2 jimblumberg  Icon User is offline

  • member icon


Reputation: 4074
  • View blog
  • Posts: 12,563
  • Joined: 25-December 09

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 17 February 2013 - 09:18 AM

Quote

Now, if write a function prototype like this
	const int MAX_COLS = 100;
	void transpose ( int matrix[ ][MAX_COLS], const int ROWS, const int COLS );


compiler won't do it's job,

Could you please explain what you mean by the compiler won't do it's job. The snippet you provided appears to be syntactically correct.

Quote

if I choose a pointer logic I should rewrite all this from 0 ( and it's far more complicated to write it with pointers, I think ).

Why would you necessarily need to rewrite this using pointers? If you properly allocate your matrix in the calling function then you can use array notation in the function even when you use pointer notation in the function signature. I suggest you supply the smallest possible complete program that illustrates your problem. Then ask specific questions based on that complete program.

Quote

Here is the code I think should do the job (not tested).

Then I suggest you test it to see if it does the job.

Jim
Was This Post Helpful? 0
  • +
  • -

#3 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 17 February 2013 - 11:11 AM

Could you please explain what you mean by the compiler won't do it's job. The snippet you provided appears to be syntactically correct.


Error seems to be originated form the fact that I create a matrix a[ rows ][ cols ] with rows and cols variable chosed from the user, and it can't convert that matrix to a matrix a[ rows ][ MAX_COLS ].

I would let the user choose the dimensions of the matrix and then fool him by writing and printing just the upper-left part of it.

Is there a more honest way to proceed?

(Little doubt here. We've mentioned dynamic allocation of memory in a class. Does it have smth do to with this?)

This post has been edited by domenico: 17 February 2013 - 11:17 AM

Was This Post Helpful? 0
  • +
  • -

#4 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 17 February 2013 - 11:40 AM

OK, so I've used the matrix
int matrix[ rows ][ MAX_COLS ];
and when i call the function written in the first post on matrix, this is the output i get:

INPUT:
0 1 2 3
4 5 6 7
8 9 0 1
2 3 4 5

OUTPUT:
0 1 11479672 0
4 5 6 7
8 9 0 1
2 3 4 5


What the hell!? It hasn't changed a single element in the proper manner!
I've tried to focus on what happens to matrix[ 0 ][ 2 ], but it doesn't make sense at all to me...

This post has been edited by domenico: 17 February 2013 - 11:42 AM

Was This Post Helpful? 0
  • +
  • -

#5 jimblumberg  Icon User is offline

  • member icon


Reputation: 4074
  • View blog
  • Posts: 12,563
  • Joined: 25-December 09

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 17 February 2013 - 11:40 AM

Quote

(Little doubt here. We've mentioned dynamic allocation of memory in a class. Does it have smth do to with this?)


Yes.

Quote

Error seems to be originated form the fact that I create a matrix a[ rows ][ cols ] with rows and cols variable chosed from the user, and it can't convert that matrix to a matrix a[ rows ][ MAX_COLS ].


Are you using C or C++? C++ doesn't allow Variable Length Arrays so this will be a big problem. If using C, only C99 guarantees VLA is allowed, so you may also face problems. I actually don't recommend using VLA no matter if your compiler supports this "feature" or not.

Quote

Is there a more honest way to proceed?

Yes, create your array using dynamic memory, new/delete, malloc/free, then prototype your function as:
void transpose ( int **matrix, const int ROWS, const int COLS )

The innards of your function would be basically the same as what you posted, meaning you can use array notation[][] to access individual elements.


Jim

This post has been edited by jimblumberg: 17 February 2013 - 11:41 AM

Was This Post Helpful? 1
  • +
  • -

#6 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 18 February 2013 - 02:22 PM

Are you using C or C++? C++ doesn't allow Variable Length Arrays so this will be a big problem. If using C, only C99 guarantees VLA is allowed, so you may also face problems. I actually don't recommend using VLA no matter if your compiler supports this "feature" or not.

C++ does allow me to declare, read and print a VLA as long as I don't use it in a function that's different from the one where it was created. Did you mean that?

Yes, create your array using dynamic memory, new/delete, malloc/free, then prototype your function as:
void transpose ( int **matrix, const int ROWS, const int COLS )

The innards of your function would be basically the same as what you posted, meaning you can use array notation[][] to access individual elements.


Thank you!
My program runs correctly now, I use the propotipe you wrote and the subsequent matrix declaration
	int ** matrix = new int * [ rows ];
	if ( rows )
	{
		matrix [ 0 ] = new int [ rows * cols ];
		for ( int row = 1; row < rows; row++ )
			matrix[ row ] = matrix[ row - 1 ] + cols;
	}


Dynamic memory allocation is so cool :D
Also, what a joy when your non-tested algorithm run correctly the first time you try it!!!

EDIT: I couldn't explain this thing:
Since I introduced the dynamically allocated matrix, my program have been taking like 30-40 seconds to run the first time after i compile it.
Subsequent runs wil start instantaneously, with no lags.
Why that enourmus lag the first time I run it?
And why zero lag after that?

This post has been edited by domenico: 18 February 2013 - 02:36 PM

Was This Post Helpful? 0
  • +
  • -

#7 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3575
  • View blog
  • Posts: 11,117
  • Joined: 05-May 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 18 February 2013 - 03:15 PM

View Postdomenico, on 18 February 2013 - 04:22 PM, said:

Are you using C or C++? C++ doesn't allow Variable Length Arrays so this will be a big problem. If using C, only C99 guarantees VLA is allowed, so you may also face problems. I actually don't recommend using VLA no matter if your compiler supports this "feature" or not.

C++ does allow me to declare, read and print a VLA as long as I don't use it in a function that's different from the one where it was created. Did you mean that?


Try putting your code into Visual Studio. I think you will discover that the compiler will give you an error. Basically, VLA is only supported in the C99 standard. Any other will support you are finding is an extension provided by your compiler, but may not be supported by other compilers.
Was This Post Helpful? 0
  • +
  • -

#8 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1074
  • View blog
  • Posts: 4,533
  • Joined: 09-June 09

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 18 February 2013 - 07:20 PM

int ** matrix = new int * [ rows ];
if ( rows )
{
	matrix [ 0 ] = new int [ rows * cols ];
	for ( int row = 1; row < rows; row++ )
		matrix[ row ] = matrix[ row - 1 ] + cols;
}


This is completely incorrect. If you are trying the allocate a dynamic 2D array array the size of rows x cols, you should do something like the following

int **matrix = new int*[rows];
for(int i=0; i<rows; i++)
   matrix[i] = new int[cols];




If 2d array allocation seems difficult to understand, you can just use a 1D array instead.

This post has been edited by jjl: 18 February 2013 - 07:38 PM

Was This Post Helpful? 0
  • +
  • -

#9 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 19 February 2013 - 09:51 AM

View Postjjl, on 18 February 2013 - 07:20 PM, said:

int ** matrix = new int * [ rows ];
if ( rows )
{
	matrix [ 0 ] = new int [ rows * cols ];
	for ( int row = 1; row < rows; row++ )
		matrix[ row ] = matrix[ row - 1 ] + cols;
}


This is completely incorrect. If you are trying the allocate a dynamic 2D array array the size of rows x cols, you should do something like the following

int **matrix = new int*[rows];
for(int i=0; i<rows; i++)
   matrix[i] = new int[cols];




If 2d array allocation seems difficult to understand, you can just use a 1D array instead.


My program run correctly every time, and it fails at the first try when I tried to insert your declaration.
I think it's because your solution ask for a new array of cols integer as soon as they're available. It's not requested that they've to be in contiguous cells of memory and so the index-based algorithm doesn't work.
Can anyone confirm my words?
Is my declaration completely incorrect?
And most importantly, why?

This post has been edited by domenico: 19 February 2013 - 09:53 AM

Was This Post Helpful? 0
  • +
  • -

#10 jimblumberg  Icon User is offline

  • member icon


Reputation: 4074
  • View blog
  • Posts: 12,563
  • Joined: 25-December 09

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 19 February 2013 - 01:15 PM

Quote

Is my declaration completely incorrect?

Not completely, but it is incorrect, jjl implementation is correct.

Quote

My program run correctly every time, and it fails at the first try when I tried to insert your declaration.

What do you mean by fails? What error messages did you receive?

Here is a small sample program to illustrate the idea.
#include <iostream>

int main()
{
   int rows = 10;
   int cols = 20;

   int **matrix = new int*[rows];
   for(int i=0; i<rows; i++)
      matrix[i] = new int[cols];

   for(int i = 0; i < rows;++i)
      for(int j = 0; j < cols; ++j)
         matrix[i][j] = (i * 20) + j + 1;

   for(int i = 0; i < rows;++i)
   {
      for(int j = 0; j < cols; ++j)
         std::cout << matrix[i][j] << " ";
      std::cout << std::endl;
   }
   for(int i=0; i<rows; i++)
      delete matrix[i] ;
   delete matrix;

   return(0);
}



Jim

This post has been edited by jimblumberg: 19 February 2013 - 01:15 PM

Was This Post Helpful? 0
  • +
  • -

#11 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 19 February 2013 - 01:49 PM

View Postjimblumberg, on 19 February 2013 - 01:15 PM, said:

Quote

Is my declaration completely incorrect?

Not completely, but it is incorrect, jjl implementation is correct.

Quote

My program run correctly every time, and it fails at the first try when I tried to insert your declaration.

What do you mean by fails? What error messages did you receive?

Here is a small sample program to illustrate the idea.
#include <iostream>

int main()
{
   int rows = 10;
   int cols = 20;

   int **matrix = new int*[rows];
   for(int i=0; i<rows; i++)
      matrix[i] = new int[cols];

   for(int i = 0; i < rows;++i)
      for(int j = 0; j < cols; ++j)
         matrix[i][j] = (i * 20) + j + 1;

   for(int i = 0; i < rows;++i)
   {
      for(int j = 0; j < cols; ++j)
         std::cout << matrix[i][j] << " ";
      std::cout << std::endl;
   }
   for(int i=0; i<rows; i++)
      delete matrix[i] ;
   delete matrix;

   return(0);
}



Jim


I see, but I don't see why my declaration is incorrect.
I basically do the same, with the difference that my code ask for rows * cols number and then adjust the pointers. Your code ask for cols number, rows times.
Plus, isn't true that code doesn't ask for contiguous integers? Can I use indexes-based algorithms with that?
Last thing, my code is less efficient because system has to find more free space at once, so it will take more time, right?


EDIT: Forgot about the output message. That's why it fails:

INPUT:
0 1 2 3 2 1
4 5 6 7 0 1
8 9 0 1 1 2
1 2 1 2 1 0
2 3 4 5 3 6
5 0 8 6 4 5

OUTPUT:
0 1 1 2 8 6
4 5 6 7 2 3
5312720 5308612 0 1 2 3
1 2 4 5 1 0
0 1 4 5 1970608968 1970609608
5 0 2 1 1 2


Notice that I use a function to print matrix that runs every element from *matrix to *( matrix + rows * cols - 1 ) with a simple for ( int i = 0; i < rows * cols; i++ ) cycle.

This post has been edited by domenico: 19 February 2013 - 02:04 PM

Was This Post Helpful? 0
  • +
  • -

#12 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 19 February 2013 - 02:17 PM

It's even read from a file using that method.
Sorry about two posts but I can't edit the former anymore

This post has been edited by domenico: 19 February 2013 - 02:18 PM

Was This Post Helpful? 0
  • +
  • -

#13 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 19 February 2013 - 02:34 PM

Tried to run the program changing the reading and printing method (now I use indexes annotation to print them )
It's to my surprise that the program behave properly now.

I read somewhere that functions has to know the second size of a 2d array ( let's call it MAX_COLS), because it has to jump i * MAX_COLS position and then add j to get to matrix[ i ][ j ].

If that's true... well, I'm confused.

This post has been edited by domenico: 19 February 2013 - 02:35 PM

Was This Post Helpful? 0
  • +
  • -

#14 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1074
  • View blog
  • Posts: 4,533
  • Joined: 09-June 09

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 19 February 2013 - 05:52 PM

Quote

I see, but I don't see why my declaration is incorrect.
int ** matrix = new int * [ rows ];
if ( rows )
{
	matrix [ 0 ] = new int [ rows * cols ];
	for ( int row = 1; row < rows; row++ )
		matrix[ row ] = matrix[ row - 1 ] + cols;
}


To allocate a dynamic 2D array, you need to allocate an array of pointers (which you do correctly). Every element in the array of pointers needs to point to an array of length col.

Quote

I read somewhere that functions has to know the second size of a 2d array

Yes, memory addressing is sequential, the system does not know what a 2D block of memory is. This means that 2D arrays are laid out continuously in memory. In order to map the 2D array indices to an element in a 2D array, the compiler needs to know what the width of the matrix is.

i.e.
index = row * WIDTH_OF_MATRIX + col


Quote

Plus, isn't true that code doesn't ask for contiguous integers? Can I use indexes-based algorithms with that?


Yes, you can use a single 1D array and then map your 2D indices to 1D indices.

i.e.
#define ROWS 30
#define COLS 30

inline int 2Dto1D(int width, int row, int col) {
   return row * width + col;
}

int main() {
   int *matrix = new int[ROWS * COLS];

   //set all elements to i * j, based on 2D indices
   for(int i=0; i<ROWS; i++) {
      for(int j=0; j<COLS; j++) {
         matrix[2Dto1D(COLS, i, j)] = i * j;
      }
   }

   delete matrix
   return 0;
}





Quote

Last thing, my code is less efficient because system has to find more free space at once, so it will take more time, right?


The time spend allocating memory on the heap is negligible compared to the operations on the matrix. If you really want to find the time it takes to allocate the memory relative to the operations, try profiling your code using gprof.

This post has been edited by jjl: 19 February 2013 - 05:56 PM

Was This Post Helpful? 0
  • +
  • -

#15 domenico  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 89
  • Joined: 21-July 12

Re: Algorithms on matrix. Pointer/No pointer in the prototype issue.

Posted 20 February 2013 - 05:54 AM

It was late yesterday and I really didn't explained myself properly.
What I wanted to say is
If matrixes work like that ( index = row * WIDTH_OF_MATRIX + col ),
why did I get different outputs when I changed my printMatrix from this
printMatrix( const int * const matrix, const int ROWS, const int COLS )
{
   for ( int i = 0; i < ROWS * COLS; ++i )
   {
      cout << *( matrix + i ) << '\t';
      if ( ( i + 1 ) % COLS == 0 )
         cout << '\n';
   }
}

to this
void printMatrix( int ** const matrix, const int ROWS, const int COLS )
{			
	for ( int row = 0; row < ROWS; ++row )
	{
		for ( int col = 0; col < COLS; ++col )
			cout << matrix[ row ][ col ] << '\t';
			
		cout << '\n';
	}
}


Shouldn't the second inherently do the same thing as the first one?

This post has been edited by domenico: 20 February 2013 - 06:04 AM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2