Dynamic Matrix!

[Sunnygirl]

hello @all, i need a dynamic two-dimensional matrix. how can i do this? thank you very much! sunny

[Neville Franks]

You can use malloc and realloc to do it all yourself, or use a STL vector or vectors. Neville Franks, Author of ED for Windows. Free Trial at www.getsoft.com

[MAAK]

if you just need 2d array that doesnt shrink or grow frequently then you can use two approaches, pointers to pointers or a 1d array accessed by formula. for pointers to pointers this is how it's done:

int ** p; //a pointer to an integer pointer
p = new int * [10]; //create 10 new integer pointers

for(int i = 0; i <10; i++)
	p[i] = new int[10];
for(int i = 0; i < 10; i++)
	for(int j = 0; j < 10; j++)
		p[i][j] = rand();
for(int i = 0; i <10; i++)
	delete [] p[i];
delete [] p;

for 1d arrays, you make an array with size m * n and access elements at i,j by formula j * m + i, where m are rows and n are columns.

int * p = new int[m * n];

for(int i = 0; i < n; i++)
	for(int j = 0; j < m; j++)
		p[j * m + i] = rand();
delete [] p;

this approach is better since the whole array elements are compact together rather than having group of 1d arrays scattered in the memory. if you need an array that grows and shrink frequently, then you may use template containers to make array or arrays, rather than making your own class for it. for example, if you gonna use the STL vector container you can declare the array as follows: vector< vector > my_matrix; //declare a vector of integer vecotrs //a space must be inserted between the last two '>' //symbol to be differentiated from insertion operator my_matrix.resize(10); //initialize the matrix to contain 10 rows //intialize each row to contrai 10 elements for(int i = 0; i <10; i++) my_matrix[i].resize(10); //fill the matrix with random numbers for(i = 0; i < 10; i++) for(int j = 0; j < 10; j++) my_matrix[i][j] = rand(); this also can be done using the MFC's CArray using the declaration

CArray< CArray, CArray > my_matrix;

[Toni78]

MAAK wrote: this approach is better since the whole array elements are compact together rather than having group of 1d arrays scattered in the memory. Does it really matter if they are scattered in the memory? My impression was quite different because the elements of the array will be accessed through indirect addressing and the general formula is [ base reg + factor *index reg + constant ]. I don't see a large overhead in computing the index. I am really opened to suggestions because I am geting very curios now. // Afterall, I realized that even my comment lines have bugs When one cannot invent, one must at least improve (in bed).-My latest fortune cookie

[Peter Weyzen]

For people who develop high-end software.... like spreadsheets and data models. This makes a huge difference. There's all kinds of fancy algorithms to make a true dynamic and fast array. For this case, it probably doesn't.... ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Peter Weyzen Staff Engineer Santa Cruz Networks

[MAAK]

Well I think I didn't think about it correctly, cuz when I think about it again I found that the int ** seems to have better performance than the 1D array implemenation, and it may be not related to how data is near to each other. The int ** needs 4 mov micro instruction to get the effective address, while the 1D needs 2 mov, one multiplication (which I think more costy and which make the whole overhead) and one addition operation to get the effective address. This is the assembly code for getting the effective address in the 1D implementation for a matrix 10 x 10 to access element (i, j)

ar[j * w + i] = 5;
mov         eax,dword ptr [j] 
imul        eax,dword ptr [w] 
add         eax,dword ptr [i] 
mov         ecx,dword ptr [ar] 
mov         dword ptr [ecx+eax*4],5 

This is code for the int ** implementation for a matrix 10 x 10

ar[i][j] = 5;
mov         eax,dword ptr [i] 
mov         ecx,dword ptr [ar] 
mov         edx,dword ptr [ecx+eax*4] 
mov         eax,dword ptr [j] 
mov         dword ptr [edx+eax*4],5

however, I found that the the 1D representation is more commonly used for example, this is how the same thing work for a static 2D array declared in the compiler:

ar[i][j] = 5;
mov         eax,dword ptr [i] 
imul        eax,eax,28h 
lea         ecx,ar[eax] 
mov         edx,dword ptr [j] 
mov         dword ptr [ecx+edx*4],5

If you checked it thourougly you will find that it's similar to the 1D, but it has optimization due to previous knowledge of the array size. [All assembly code is obtained using VC++ debugging disassembly] This approach is useful in data serializzation since serialization can be done using single call to I/O device, bitmaps for example are stored in memory as a single 1D array. I hope if anyone has more infomation about this issue shares it with us, cuz am more curios about it.

[Toni78]

That is very interesting. Thank you very much Peter for your reply. // Afterall, I realized that even my comment lines have bugs When one cannot invent, one must at least improve (in bed).-My latest fortune cookie

[Peter Weyzen]

I've had more than one programming job in the past working for companies that developed spreadsheets. They used a pretty fancy algorithm, based on something called "sparse matrix arrays" [You can search on the net for that, and you'll find all kinds of sites, with people posting and discussing these algorithms.] It was all about letting you create a spreadsheet with a virtual array of large proportions, and making it both quick to access entries in the array, and make it occupy as little memory as possible. Excel does a virtual array of 64K rows, 255 columns, and a third dimension of page accesses -- a 3D sparse array... with a possible capcity of 4,261,413,375 array entries (cells). There's no way you can pre-allocate an array of that size... But the arrays do allow you to place data anywhere, and it works and it remains small and fast. People get paid a lot of money to develop data structures like these... too bad it wasn't me. -p ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Peter Weyzen Staff Engineer Santa Cruz Networks