list optimization

[Evangelista Sami]

Hi all

i have implemented a list type as an array of pointer like this

typedef struct {
int nb_elements;
void **elements;
} list;

to avoid having a pointer for each element as it is done with a recursive
definition.

the major drawback is that when i want to add an element at the end of the list,
i have to allocate an array of nb_elements+1 elements then copy all the elements
of the previous array to the new array like this

void append
(list *l,
void *new_element)
{
int i;
void **elements = (void **) malloc(sizeof(void *) * (l->nb_elements+1));
for(i=0; i<l->nb_elements; i++)
elements[i] = l->elements[i];
elements[i] = new_element;
l->nb_elements++;
free(l->elements);
l->elements = elements;
}

which is very time expensive.

can anyone tell me of a hint to avoid doing that or to optimize it.
note that my first aim is to save as much memory as possible and i didn't find
any solution which is cheaper in term of memory.

Thanks for any help

Sami Evangelista

[Karl Heinz Buchegger]

Evangelista Sami wrote:

Hi all

i have implemented a list type as an array of pointer like this

typedef struct {
int nb_elements;
void **elements;
} list;

to avoid having a pointer for each element as it is done with a recursive
definition.

the major drawback is that when i want to add an element at the end of the list,
i have to allocate an array of nb_elements+1 elements then copy all the elements
of the previous array to the new array like this

void append
(list *l,
void *new_element)
{
int i;
void **elements = (void **) malloc(sizeof(void *) * (l->nb_elements+1));
for(i=0; i<l->nb_elements; i++)
elements[i] = l->elements[i];
elements[i] = new_element;
l->nb_elements++;
free(l->elements);
l->elements = elements;
}

which is very time expensive.

can anyone tell me of a hint to avoid doing that or to optimize it.
note that my first aim is to save as much memory as possible and i didn't find
any solution which is cheaper in term of memory.

Put the pointer to the node.
If you think of it, memory cost will be the same.
But with creating a new node, you also create a pointer
to the next node.

--
Karl Heinz Buchegger
kb******@gascad.at

[Andreas Kahari]

In article <5f**************************@posting.google.com >, Evangelista Sami wrote:

Hi all

i have implemented a list type as an array of pointer like this

typedef struct {
int nb_elements;
void **elements;
} list;

to avoid having a pointer for each element as it is done with a recursive
definition.

the major drawback is that when i want to add an element at the end of the list,
i have to allocate an array of nb_elements+1 elements then copy all the elements
of the previous array to the new array like this

Well, if this is the way you want to store your data, then one
way of making it a bit more efficient is to always allocate/free
a number of elements greater than one.

You could, for example, choose to always allocate a chunk of
pointers twice as large as what you already had, or a fixed
number of pointer, maybe 10 or 20 or 100 depending on your
application.

When the number of unused pointers fall below 50% (or some
number), deallocate half (or some number) of them.

This way you do not have to do a realloc() for each additional
pointer.
--
Andreas Kähäri

[David Rubin]

Evangelista Sami wrote:

Hi all

i have implemented a list type as an array of pointer like this

typedef struct {
int nb_elements;
void **elements;
} list;

to avoid having a pointer for each element as it is done with a recursive
definition.

the major drawback is that when i want to add an element at the end of the list,
i have to allocate an array of nb_elements+1 elements then copy all the elements
of the previous array to the new array like this

The typical way of handling this situation is to separately keep track
of the list's size and capacity. When you need to grow the list
(size==cpacity), you double the capacity. Thus, the complexity in terms
of the number of "copy operations" needed to grow the list to size N is
linear in N. Your method is quadratic. The tradeoff is time v space, so
if you anticipate storing a small number of elements, increasing the
capacity by a constant (c>=1) might suit you better. Either way, you
should consider storing both size and capacity in the list structure.

Another approach is to use chained blocks where each block store some
number of elements. This obviates the need for copying when growing the
list, but complicates list access.

/david

--
"As a scientist, Throckmorton knew that if he were ever to break wind in
the echo chamber, he would never hear the end of it."

[tom_usenet]

On 27 Oct 2003 06:44:34 -0800, ev******@cnam.fr (Evangelista Sami)
wrote:

Hi all

i have implemented a list type as an array of pointer like this

typedef struct {
int nb_elements;
void **elements;
} list;
Change that to:

typedef struct {
int nb_elements;
int capacity;
void **elements;
} list;

and let capacity be greater than nb_elements. This means
to avoid having a pointer for each element as it is done with a recursive
definition.
Do you mean to avoid using a linked list?
the major drawback is that when i want to add an element at the end of the list,
i have to allocate an array of nb_elements+1 elements then copy all the elements
of the previous array to the new array like this

void append
(list *l,
void *new_element)
{
int i;
void **elements = (void **) malloc(sizeof(void *) * (l->nb_elements+1));
for(i=0; i<l->nb_elements; i++)
elements[i] = l->elements[i];
elements[i] = new_element;
l->nb_elements++;
free(l->elements);
l->elements = elements;
}

which is very time expensive.

A simple solution which may help with no other changes is to use
realloc rather than malloc. A more complete solution (using capacity)
is:
void append(list *l, void *new_element)
{
int i;
/*if we're out of capacity, double the capacity*/
if (l->nb_elements + 1 > l->capacity)
{
/*double capacity, unless it is 0*/
if (l->capacity == 0)
l->capacity = 4;
else
l->capacity *= 2;
l->elements = realloc(l->elements, l->capacity * sizeof(void*));
}
elements[l->nb_elements++] = new_element;
}

You need to add error checking for the realloc return!

Tom

[The Real OS/2 Guy]

On Mon, 27 Oct 2003 14:44:34 UTC, ev******@cnam.fr (Evangelista Sami)
wrote:

Hi all

i have implemented a list type as an array of pointer like this

typedef struct {
int nb_elements;
void **elements;
} list;

to avoid having a pointer for each element as it is done with a recursive
definition.

Use simply either a linked list or a tree.

A linket list would contain a single node and points to the next one
like

struct list {
struct list *pNext;
/* any kind of data follows here, e.g.: */
int flags;
char *name; /* a pointer because names are different in lengh */
/* must be malloced separately but saves amount of
memory */
char postalcode[6]; /* string with almost fixed length */
......
} list;

So when you needs a new member of the list you would simply malloc()
one member and insert it anywhere in the list. No need to copy
anything around (except the data for that single element.

If you have a high freyuence in inserting/removing accessing single
elements in unspecified order it would be a good idea to have them
listed as tree because this will shorten the access time when you have
to search it.

struct tree {
struct tree *pNext; /* greater than the current */
struct tree *pPre; /* lower than the current */
/* any data gets here */
} tree;


--
Tschau/Bye
Herbert

eComStation 1.1 Deutsch wird jetzt ausgeliefert!

[Evangelista Sami]

"The Real OS/2 Guy" <os****@pc-rosenau.de> wrote in message news:<wmzsGguTDN6N-pn2-gyr4P8EY0fCk@moon>...

On Mon, 27 Oct 2003 14:44:34 UTC, ev******@cnam.fr (Evangelista Sami)
wrote:

Hi all

i have implemented a list type as an array of pointer like this

typedef struct {
int nb_elements;
void **elements;
} list;

to avoid having a pointer for each element as it is done with a recursive
definition.

Use simply either a linked list or a tree.

A linket list would contain a single node and points to the next one
like

struct list {
struct list *pNext;
/* any kind of data follows here, e.g.: */
int flags;
char *name; /* a pointer because names are different in lengh */
/* must be malloced separately but saves amount of
memory */
char postalcode[6]; /* string with almost fixed length */

......
} list;

So when you needs a new member of the list you would simply malloc()
one member and insert it anywhere in the list. No need to copy
anything around (except the data for that single element.

If you have a high freyuence in inserting/removing accessing single
elements in unspecified order it would be a good idea to have them
listed as tree because this will shorten the access time when you have
to search it.

struct tree {
struct tree *pNext; /* greater than the current */
struct tree *pPre; /* lower than the current */
/* any data gets here */
} tree;

hi
thanks for all your responses

the problem with your solution is that it takes a pointer for each
element of my list. so the total size of your solution for a list of N
elements is
N * (sizeof(list *) + sizeof(element)) :

whereas the array solution "only" takes :
N * (sizeof(element)) + sizeof(int)

As far as my first goal is to save as much memory as possible i prefer
the array solution.

any idea?

[The Real OS/2 Guy]

On Tue, 28 Oct 2003 14:12:09 UTC, ev******@cnam.fr (Evangelista Sami)
wrote:

"The Real OS/2 Guy" <os****@pc-rosenau.de> wrote in message news:<wmzsGguTDN6N-pn2-gyr4P8EY0fCk@moon>...

On Mon, 27 Oct 2003 14:44:34 UTC, ev******@cnam.fr (Evangelista Sami)
wrote:

Hi all

i have implemented a list type as an array of pointer like this

typedef struct {
int nb_elements;
void **elements;
} list;

to avoid having a pointer for each element as it is done with a recursive
definition.

Use simply either a linked list or a tree.

A linket list would contain a single node and points to the next one
like

struct list {
struct list *pNext;
/* any kind of data follows here, e.g.: */
int flags;
char *name; /* a pointer because names are different in lengh */
/* must be malloced separately but saves amount of
memory */
char postalcode[6]; /* string with almost fixed length */

......
} list;

So when you needs a new member of the list you would simply malloc()
one member and insert it anywhere in the list. No need to copy
anything around (except the data for that single element.

If you have a high freyuence in inserting/removing accessing single
elements in unspecified order it would be a good idea to have them
listed as tree because this will shorten the access time when you have
to search it.

struct tree {
struct tree *pNext; /* greater than the current */
struct tree *pPre; /* lower than the current */
/* any data gets here */
} tree;

hi
thanks for all your responses

the problem with your solution is that it takes a pointer for each
element of my list. so the total size of your solution for a list of N
elements is
N * (sizeof(list *) + sizeof(element)) :

whereas the array solution "only" takes :
N * (sizeof(element)) + sizeof(int)

As far as my first goal is to save as much memory as possible i prefer
the array solution.

any idea?

As you have the need of dynamic memory allocation AND the problem that
realloc can be really time expansive AND you needs to save pointers
you may simple use a compromise of using an array and pointers between
the structs.

e.g.:

struct address {
struct address *pNext
struct address *pPre;
size_t cb; /* count the number of used entries */
struct {
char *name; /* instead of name[35] */
char *address1; /* instead of address1[35] */
char *address2; /* and so on */
....
} member[1000];
} addresses;

Holds up to 1000 addresses in one block. When this block is full
another block of 1000 addresses gets allocated.....

Using pointers for the true data helps to reduce the memory usage
because the same name - but with different addresses needs only ONE
string that holds the name, different names but same address 1 or 2
..... saves more memory because each string exists only once but has
multiple pointers to it. When you defines the space a field needs you
have to define the maximum size - even as the middle will only use the
half. Having a pointer to an dynamic allocated string will save space
- and if the same string can occure multiple times in the whole list
you can compact it more by using the same string again.

But consider that this solution costs a lot more of code that needs to
be debugged! Holding things a bit simple. Here use a single element of
data and spend a pointer for each is better, even as the memory usage
increases. This ends up with a big amount of allocated memory unused.
Look what you get when you have 10001 addresses. You've allocated 2
times 1000 ones! When you have each record separately you saves 999 *
the size of a record - but yes, you'll spend 1000 * sizeof(pointer to
struct) extra.

Having the records separately makes it easy to sort them in many cases
without copying they around, because sorting them by its pointers is
much quicker. Sorted insert reduces runtime too.
--
Tschau/Bye
Herbert

eComStation 1.1 Deutsch wird jetzt ausgeliefert!