Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

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]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (6)
As of 2017-07-28 17:03 GMT
Find Nodes?
    Voting Booth?
    I came, I saw, I ...

    Results (431 votes). Check out past polls.