Dynamically allocated array

[Ray D.]

I'm trying to write a C function to compute the compressed row storage
(CRS) vectors of a 2-d matrix. This is used primarily for increasing
computing efficiency of matrices whose main elements are zeros. So
for example, if you were given the following matrix:

A = { 0, 0, 1, 0;
0, 3, 0, 0;
6, 0, 4, 0}

the function would compute three vectors - the non-zero element
vector, the column index vector for each element, and the row pointer
vector. For this example, the element vector would be {1, 3, 6, 4},
the column index vector would be {2, 1, 0, 2}, and the row pointer
vector would be {0, 1, 2, 5}.

Now what I want to do is generate these arrays from matrix A, so
clearly I don't know the array size until I begin to go through each
row of the matrix to see which elements are non-zero. Because of
this, how would I go about allocating the array size at run-time? I'm
assuming you can use the malloc() function, but I'm new to this so any
help would be appreciated. Thanks!

 

[fred.l.kleinschmidt]

I'm trying to write a C function to compute the compressed row storage
(CRS) vectors of a 2-d matrix. This is used primarily for increasing
computing efficiency of matrices whose main elements are zeros. So
for example, if you were given the following matrix:

A = { 0, 0, 1, 0;
0, 3, 0, 0;
6, 0, 4, 0}

the function would compute three vectors - the non-zero element
vector, the column index vector for each element, and the row pointer
vector. For this example, the element vector would be {1, 3, 6, 4},
the column index vector would be {2, 1, 0, 2}, and the row pointer
vector would be {0, 1, 2, 5}.

Now what I want to do is generate these arrays from matrix A, so
clearly I don't know the array size until I begin to go through each
row of the matrix to see which elements are non-zero. Because of
this, how would I go about allocating the array size at run-time? I'm
assuming you can use the malloc() function, but I'm new to this so any
help would be appreciated. Thanks!

Make a guess as to the size, based on what you know about how sparse
the
matrix is. If you haven't a clue, just pick some arbitrary number
based on
the number of rows/columns, such as r*c/n, where n is 2, or 5, or 100,
or...

Then if you reach that number while indexing through the matrix,
realloc
the three vectors, increasing the size by some factor based on how far
you
have made it through the matrix.

 

[Eric Sosman]

Ray D. wrote On 10/01/07 14:15,:

I'm trying to write a C function to compute the compressed row storage
(CRS) vectors of a 2-d matrix. This is used primarily for increasing
computing efficiency of matrices whose main elements are zeros. So
for example, if you were given the following matrix:

A = { 0, 0, 1, 0;
0, 3, 0, 0;
6, 0, 4, 0}

the function would compute three vectors - the non-zero element
vector, the column index vector for each element, and the row pointer
vector. For this example, the element vector would be {1, 3, 6, 4},
the column index vector would be {2, 1, 0, 2}, and the row pointer
vector would be {0, 1, 2, 5}.

Now what I want to do is generate these arrays from matrix A, so
clearly I don't know the array size until I begin to go through each
row of the matrix to see which elements are non-zero. Because of
this, how would I go about allocating the array size at run-time? I'm
assuming you can use the malloc() function, but I'm new to this so any
help would be appreciated. Thanks!

Make a guess, then call malloc(). If the guess turns
out to be too small, make a larger guess and call realloc()
to enlarge the allocated array. Repeat as needed. Optional:
At the end, if the final guess turns out to have been larger
than needed, call realloc() again to shrink to the final size.

Or,

Count the number of non-zero elements in A. This tells
you how large the CRS vectors must be; call malloc() with that
exact size. Now make a second pass, filling in the vectors.

 

[Ray D.]

Thanks. Now I'm trying to compile and I'm getting a syntax error when
I try to assign values to the array. This seems really simple, but
for some reason I can't get it! Anyways, here is the code:

#define MATSIZE 8
....
int **A;
....
A = malloc(MATSIZE*sizeof(int *));
for (i = 0; i < MATSIZE; i++)
A = malloc(MATSIZE*sizeof(int));

A = {{0, 1, 0, 0, 0, 3, 0, 0},
{0, 0, 0, 4, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 7, 0, 0},
{6, 0, 8, 0, 0, 0, 2, 0},
{0, 0, 0, 0, 0, 3, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 5},
{0, 2, 0, 0, 0, 0, 1, 0}};

And here is the error I'm getting: error C2059: syntax error : '{' -
this is for the first line of the A = {{ declaration. I thought that
was the way to define an array? Is this done differently with
pointers? Again, thank you for the help.

 

[Christopher Benson-Manica]

Make a guess, then call malloc(). If the guess turns
out to be too small, make a larger guess and call realloc()
to enlarge the allocated array. Repeat as needed.

Count the number of non-zero elements in A. This tells
you how large the CRS vectors must be; call malloc() with that
exact size. Now make a second pass, filling in the vectors.

I would think option #2 would be generally preferable, in the name of
reducing expensive *alloc calls.

 

[fred.l.kleinschmidt]

Thanks. Now I'm trying to compile and I'm getting a syntax error when
I try to assign values to the array. This seems really simple, but
for some reason I can't get it! Anyways, here is the code:

#define MATSIZE 8
...
int **A;
...
A = malloc(MATSIZE*sizeof(int *));

Better: A = malloc( MATSIZE*sizeof(*A) );
That way, if you ever change A to , say, double**,
you don't have to change this statement.

for (i = 0; i < MATSIZE; i++)
A = malloc(MATSIZE*sizeof(int)); again, use sizeof( *A[0] )

A = {{0, 1, 0, 0, 0, 3, 0, 0},
{0, 0, 0, 4, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 7, 0, 0},
{6, 0, 8, 0, 0, 0, 2, 0},
{0, 0, 0, 0, 0, 3, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 5},
{0, 2, 0, 0, 0, 0, 1, 0}};

And here is the error I'm getting: error C2059: syntax error : '{' -
this is for the first line of the A = {{ declaration. I thought that
was the way to define an array? Is this done differently with
pointers? Again, thank you for the help.

You have to use:
for ( i=0; i < MATSIZE; i++ ) {
for ( j=0; j < MATSIZE; j++ ) {
A[j] = ...
}
}

 

[Eric Sosman]

Make a guess, then call malloc(). If the guess turns
out to be too small, make a larger guess and call realloc()
to enlarge the allocated array. Repeat as needed.

Count the number of non-zero elements in A. This tells
you how large the CRS vectors must be; call malloc() with that
exact size. Now make a second pass, filling in the vectors.

I would think option #2 would be generally preferable, in the name of
reducing expensive *alloc calls.

Knuth illustrates the situation as follows:

"Little old lady, riding a bus: `Little boy, can you
tell me how to get off at Pasadena Street?'

"Little boy: `Just watch me, and get off two stops
before I do.'

"(The joke is that the little boy gives a two-pass
algorithm.)"

In other words: I am about to send you the values of matrix A,
one at a time, by smoke signal. Explain how to apply method #2.

 

[Christopher Benson-Manica]

In other words: I am about to send you the values of matrix A,
one at a time, by smoke signal. Explain how to apply method #2.

I admit that I didn't read the problem carefully. I plead guilty by
reason of yesterday being Monday

 

[Eric Sosman]

Christopher Benson-Manica wrote On 10/02/07 09:18,:

I admit that I didn't read the problem carefully. I plead guilty by
reason of yesterday being Monday

The Judge is likely to be lenient in view of that
extenuating circumstance. (All I was trying to point out
is that sometimes you can use a multi-pass method and
sometimes you must find a way to do everything in one
pass. Neither approach is right in all situations, and
the O.P. didn't tell us much about his, so ...)

 

[Jorge Peixoto de Morais Neto]

#define MATSIZE 8

...
int **A;
...
A = malloc(MATSIZE*sizeof(int *));
for (i = 0; i < MATSIZE; i++)
A = malloc(MATSIZE*sizeof(int));

A = {{0, 1, 0, 0, 0, 3, 0, 0},
{0, 0, 0, 4, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 7, 0, 0},
{6, 0, 8, 0, 0, 0, 2, 0},
{0, 0, 0, 0, 0, 3, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 5},
{0, 2, 0, 0, 0, 0, 1, 0}};

This makes no sense because A is of type pointer to pointer to int.
You are trying to put a matrix into a pointer. You could do this by
using an initialized array:

#include <stdio.h>

int main (void) {
#define MATSIZE 8
int A[][MATSIZE] = {{0, 1, 0, 0, 0, 3, 0, 0},
{0, 0, 0, 4, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 7, 0, 0},
{6, 0, 8, 0, 0, 0, 2, 0},
{0, 0, 0, 0, 0, 3, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 5},
{0, 2, 0, 0, 0, 0, 1, 0}};
int i,j;
for (i = 0; i < MATSIZE; i++) {
for (j = 0; j < MATSIZE - 1; j++)
printf ("%d, ", A[j]);
printf ("%d\n", A[j]);
}

return 0;
}