list optimization

Discussion in 'C Programming' started by Evangelista Sami, Oct 27, 2003.

  1. 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 = l->elements;
    elements = 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
     
    Evangelista Sami, Oct 27, 2003
    #1
    1. Advertising

  2. 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 = l->elements;
    > elements = 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
     
    Karl Heinz Buchegger, Oct 27, 2003
    #2
    1. Advertising

  3. In article <>, 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
     
    Andreas Kahari, Oct 27, 2003
    #3
  4. Evangelista Sami

    David Rubin Guest

    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."
     
    David Rubin, Oct 27, 2003
    #4
  5. Evangelista Sami

    tom_usenet Guest

    On 27 Oct 2003 06:44:34 -0800, (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 = l->elements;
    > elements = 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
     
    tom_usenet, Oct 27, 2003
    #5
  6. On Mon, 27 Oct 2003 14:44:34 UTC, (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!
     
    The Real OS/2 Guy, Oct 28, 2003
    #6
  7. "The Real OS/2 Guy" <> wrote in message news:<wmzsGguTDN6N-pn2-gyr4P8EY0fCk@moon>...
    > On Mon, 27 Oct 2003 14:44:34 UTC, (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?
     
    Evangelista Sami, Oct 28, 2003
    #7
  8. On Tue, 28 Oct 2003 14:12:09 UTC, (Evangelista Sami)
    wrote:

    > "The Real OS/2 Guy" <> wrote in message news:<wmzsGguTDN6N-pn2-gyr4P8EY0fCk@moon>...
    > > On Mon, 27 Oct 2003 14:44:34 UTC, (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!
     
    The Real OS/2 Guy, Oct 29, 2003
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. roopa
    Replies:
    6
    Views:
    757
    Jerry Coffin
    Aug 27, 2004
  2. dackz
    Replies:
    0
    Views:
    493
    dackz
    Feb 6, 2007
  3. Debajit Adhikary
    Replies:
    17
    Views:
    694
    Debajit Adhikary
    Oct 18, 2007
  4. Ravikiran

    Zero Optimization and Sign Optimization???

    Ravikiran, Nov 17, 2008, in forum: C Programming
    Replies:
    22
    Views:
    877
    Thad Smith
    Nov 24, 2008
  5. Roy Smith

    Interesting list() un-optimization

    Roy Smith, Mar 7, 2013, in forum: Python
    Replies:
    18
    Views:
    261
    Roy Smith
    Mar 10, 2013
Loading...

Share This Page