Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > List as a dynamic array of increasing-sized arrays

Reply
Thread Tools

List as a dynamic array of increasing-sized arrays

 
 
Seebs
Guest
Posts: n/a
 
      10-29-2010
On 2010-10-29, Trevor <(E-Mail Removed)> wrote:
> They love to smack down the newbie with their superior *knowledge", but have
> they actually *found out*?
> Realloc *hardly ever* copies.


This, like everything else you've posted, is a gross oversimplification.

But wait! I can simplify this further: You're rude, you're arrogant,
and you don't seem to be able to disagree in a way suited to someone
who's gotten to his adult teeth yet.

*plonk*

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / http://www.velocityreviews.com/forums/(E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.
 
Reply With Quote
 
 
 
 
MartinBroadhurst
Guest
Posts: n/a
 
      10-30-2010
On 29 Oct, 22:04, "Trevor" <(E-Mail Removed)> wrote:
>
> You've invented a "new" data structure, but you've solved a problem that
> doesn't exist!
>


That's pretty much the conclusion I came to on the basis of the
empirical evidence I have.

>
> http://groups.google.co.uk/group/com...ead/thread/3e7...
>


I had read the first thread you mention, not the second. Things like
this were my motivation in looking for a better structure than a
dynamic array.

> They love to smack down the newbie with their superior *knowledge", but have
> they actually *found out*?


They were probably speaking in general terms, or on the basis of their
experience of particular platforms on which they had seen a problem
with dynamic arrays.

> Realloc *hardly ever* copies.
>


My experiments showed that it copied about 20% of the time, but this
was just glibc. For all I know, glibc may be optimised for geometric
expansion. After all, it's being used for std::vector(T>s in C++.
Other allocators may be optimised for quite different scenarios. It is
also important *which* 20% of the reallocs result in a copy. If it's
the larger ones, this will have a greater impact.

> 1) If you only want to add at the end, use a dynamic array
> 2) If you need to do random inserts, use a linked list, but (as you've
> discovered), embed it in a dynamic array
>


Again, that would be a valid conclusion from my results, reiterating
though that they were using one particular allocator.

There are, however, other considerations:

1) If your memory is half-used by a dynamic array, and you need to add
one more element, you will run out of memory. A linked list will
handle this fine.
It's easy to be complacent about memory usage when you're on a
platform with virtual memory, but not all platforms have this.

2) Dynamic arrays use up to twice as much memory as is needed at any
one time. Memory used in linked lists is in a constant ratio with the
elements. If the linked list is an "intrusive" one, where nodes
contain a significant amount of data, this ratio will be much more
favourable.

3) Data in a list can be highly structured, with elements containing
pointers to other elements. These pointers will be invalidated by
reallocation.
You could solve this problem by using the array-of-arrays structure I
began this thread by describing, though.

4) Some people favour the "open-work" interface exposed by linked
lists rather than using a more general container. It is handy to be
able to just have a node, and be able to tack another one on without
needing to have access to the container and go through its interface.

5) Linked lists can "recycle" nodes, by keeping nodes from removed
elements in a chain and using them preferentially when a new node is
required. This will mean less allocation and deallocation in a list
that changes frequently.

Martin

 
Reply With Quote
 
 
 
 
MartinBroadhurst
Guest
Posts: n/a
 
      10-30-2010
On Oct 30, 9:56*pm, "Scouser" <(E-Mail Removed)> wrote:
>
> They do that though, don't they?
>
> Scouser


I'm gutted, I am. I'm as sick as a parrot.

Martin

 
Reply With Quote
 
MartinBroadhurst
Guest
Posts: n/a
 
      11-03-2010
On 29 Oct, 21:04, "Trevor" <(E-Mail Removed)> wrote:
> 2) If you need to do random inserts, use a linked list, but (as you've
> discovered), embed it in a dynamic array
>


You've reminded me of something I did a while ago.
If you have a linked list embedded in an array and you remove an
element, you can move the last element in the buffer into its place.
This means that:

1. You don't need a free node list
2. You don't need to keep track of the used range of the buffer
because used = count
3. Unordered traversal (like when you just want to call a function on
each element in any order) is just array traversal, because the
elements in the buffer are dense

Linked list embedded in an array with compaction:
http://www.martinbroadhurst.com/arti...ompaction.html

Martin
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Merging two arrays -> array of arrays Allen Walker Ruby 6 05-21-2010 08:31 AM
problem making an array of arrays (of arrays) Cec Tre Ruby 3 03-19-2010 02:02 PM
Multidimensional arrays and arrays of arrays Philipp Java 21 01-20-2009 08:33 AM
dynamic arrays (convert vector to array) NeeZee C++ 7 02-04-2006 10:21 PM
Arrays Of Arrays: Is it an Array or Scalar? Hal Vaughan Perl Misc 5 02-06-2004 02:10 PM



Advertisments