growable arrays: realloc vs. linked list?

[gerard]

hi

problem: i have an array of items. this array will grow (but not
really shrink) during execution. new items are just appended and not
inserted in the middle. each item in the array will be touched
(processed) during execution repeatedly. the number of items is
unpredictable and can be only a few to over a hundred.

question: in terms of performance alone, would it be better to use an
ordinary array with a realloc strategy? or use a type of linked list?
since i need to go thru all items repeatedly, is following pointers
better than one level of array index indiretion? from previous posts,
is memory fragmentation a problem?

TIA.

gerard

[walter]

If the array is to be repeatedly scanned, using a variable sized array will
be the fastest. A linked list can span an arbitrary number of virtual pages,
resulting in lots of swapping and cache misses. I use realloc() to resize
arrays as necessary, doubling its allocated size on each overflow is a good
heuristic.

-Walter
www.digitalmars.com Free C compiler

gerard wrote in message ...

[rand mair fheal]

In article <c3905b22.01080...@posting.google.com>,
ger...@cs.ucsb.edu (gerard) wrote:

depends

random access in an array is always time O(1)

if all n elements are randomly accessed with equally frequency a linked
list or tree wont do better than log n time

but if elements have unequal frequency data structures like splay trees
have good times appraching O(1)

and a linear nonrandom scan will take O(n) for arrays or links

adding an element to a linked list is fast

adding an element to an array can be slow but you can still get good
overall time by increasing the array size by a constant factor (like 10 15
23 35 53 ... elements) rather than by a constant amount (like 10 20 30 40
50...)

but that can mean a large array badly approximates the necessary size and
crash if you dont have enough memory available

[gerard sychay]

also, as another example, is adding new linked list nodes faster than using
realloc to resize the array? i would guess that it is, since realloc must copy
the entire array. is that right? if so, is the difference that much?

thanks again.

gerard.

[Artie Gold]

gerard sychay wrote:
>
> also, as another example, is adding new linked list nodes faster than using
> realloc to resize the array? i would guess that it is, since realloc must copy
> the entire array. is that right? if so, is the difference that much?

Actually it can be, and gets worse as the array gets bigger. That is why
a poster elsethread recommended the heuristic of increasing the size of
the array geometrically (i.e. by some factor) when more space is needed.
This amortizes the resize cost -- while the resizes are increasingly
expensive, they're done less and less frequently.

HTH,
--ag

>
> thanks again.
>
> gerard.
>
> gerard wrote in message ...
> >hi
> >
> >problem: i have an array of items. this array will grow (but not
> >really shrink) during execution. new items are just appended and not
> >inserted in the middle. each item in the array will be touched
> >(processed) during execution repeatedly. the number of items is
> >unpredictable and can be only a few to over a hundred.
> >
> >question: in terms of performance alone, would it be better to use an
> >ordinary array with a realloc strategy? or use a type of linked list?
> >since i need to go thru all items repeatedly, is following pointers
> >better than one level of array index indiretion? from previous posts,
> >is memory fragmentation a problem?
> >
> >TIA.
> >
> >gerard
>
> >
> >

--
Artie Gold, Austin, TX (finger the cs.utexas.edu account for more info)
mailto:ag...@bga.com or mailto:ag...@cs.utexas.edu
--
"I wonder why I wonder why I wonder why..." -- S. Ulam

[rand mair fheal]

In article <Pine.GSO.4.21.0108072049380.14229-100000@miller>, gerard
sychay <ger...@cs.ucsb.edu> wrote:

>also, as another example, is adding new linked list nodes faster than using
>realloc to resize the array? i would guess that it is, since realloc must copy
>the entire array. is that right? if so, is the difference that much?

if you increase the array size by a constant factor rather than a constant
increment
then the allocation cost remains O(1) with a bigger multiplier

[Luca]

gerard wrote in message ...

>hi
>
>problem: i have an array of items. this array will grow (but not
>really shrink) during execution. new items are just appended and not
>inserted in the middle. each item in the array will be touched
>(processed) during execution repeatedly. the number of items is
>unpredictable and can be only a few to over a hundred.

A good compromise is a list of fixed size arrays; expansion is done by
allocating a new array and appending it to the list, without using
'realloc()' ; scanning the array is done paying attention to boundaries. The
only drawback is that random access requires the scanning of a linked list,
that is not really 'random' .

I suggest a structure like this :

#define PAGE_SIZE 2048
typedef struct sPage
{
element_type data[PAGE_SIZE] ;
struct sPage * next ;
} *Page ;

An allocation function for page is required. Scanning can be performed checking boundaries:

element_type * p ; /* p is a pointer to array elements */
Page current_page ;

/* .... some code ... */
p ++ ;
if ( ( p - currentPage->data ) == PAGE_SIZE )
{ /* switch page */
current_page = current_page->next ;
if( current_page ) p = current_page->data ;
else { /* code for index overflow */}
} else p++ ;

I hope been useful .
bye

______________________________________________________________
Luca De Santis
http://members.xoom.it/lucads