Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?

Re: Re: Re: Re: Re: Re: what's faster than .=

by pg (Canon)
on Mar 08, 2003 at 19:01 UTC ( #241422=note: print w/replies, xml ) Need Help??

in reply to Re: Re: Re: Re: Re: what's faster than .=
in thread what's faster than .=

This is definitely the kind of discussion I would like to be part of it.

People are talking with solid facts, insightful thoughts, strong supporting data ... And also talk with respect to each other, at the same time, with respect to facts found.

The other thing I would be interested in, is the performance difference between using linked list and (dynamically growing) array.

By using linked list, you would call malloc once for each element, but no realloc is called; by using array, you would call malloc once at the beginning, and then call realloc each time when it grows. I used the two approaches from time to time, but never seriously measured them.

Also you might mix the two approaches, by using a linked list of sub-arrays. the size of each array is fixed, and we grow the data structure by growing the linked list, attaching more sub-arrays to the linked list.
  • Comment on Re: Re: Re: Re: Re: Re: what's faster than .=

Replies are listed 'Best First'.
Re: Re: Re: Re: Re: Re: Re: what's faster than .=
by Anonymous Monk on Mar 08, 2003 at 21:55 UTC
    With a dynamically growing array, growing it by a fixed amount has a O(1) amortized cost, with unpredictable performance on any append (you may allocate). Accessing any element is O(1). Finding the size is O(1). Splicing a new element into the interior is O(n).

    A linked list has a guaranteed O(1) cost to grow. Splicing is also O(1). Accessing an arbitrary element is O(n). Finding the size is O(n). Splicing a new element into the interior is O(1).

    Whether the linked list or array has more overhead is implementation and dataset dependent.

    As for your mixed approach, you can do that and some have. Check out for an example of a string library that does. (I have not looked closely at it.)

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://241422]
[oiskuu]: Someone needs to re-read How do I use the power of consideration responsibly? carefully. Consideration is not intended for stamping out humor, AFAIK.
[oiskuu]: E.g. Re^3: Big thank you to the Perl community. is surely dry humor (not mine). Don't they teach humor in german schools!?
[LanX]: you don't see the whole picture
[LanX]: But reu germans have no humor, better to refrain from this site till the troll is gone...
[LanX]: true

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (11)
As of 2017-04-27 19:53 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (512 votes). Check out past polls.