Re: Extending Array instances

Charles Hixson wrote in post #1084366:
> FWIW, the answer I was looking for is that Arrays are automatically
> extended to the last index inserted into.  This probably implies that
> Arrays use some sort of linked block index, though another possibility
> is that it just allocates a honking big chunk of memory, and does a copy
> whenever it needs to resize the array.  This seems unlikely.  Also
> silly.  So I'll bet on a linked block index.

Then you lose the bet. I already posted the code.

The code says: when you set an element beyond the end, the underlying 
array storage capacity (aux.capa) is increased to the new end index plus 
half the current capacity; new storage is allocated and the old data 
copied into the new (read the manpage for "realloc"). So the data is 
copied but the number of copy operations goes down as the array grows.

This is of course *way* more efficient for most purposes than an linked 
list implementation, because the memory is contiguous and all subsequent 
get/set operations are then a simple pointer offsets rather than walking 
a list (even a list of chunks).

> P.S.:  Developing this in Ruby *IS* a measurement test.  If I can do it
> in Ruby, then I've guessed the right size.  But picking a bad algorithm
> to implement wouldn't prove much of anything.

You're talking about two different things. Picking a bad algorithm is of 
course a bad idea, and will give you bad performance (relative to a good 
algorithm) in any language.

But what you are discussing is the same algorithm, simply whether c[k] 
is slower or more memory inefficient if collection c is an Array or a 
Hash. This is almost certainly irrelevant in the context of your 
application.

Code using the obvious approach: if the keys are all non-negative 
integers and not too sparse, use an Array. Otherwise use a Hash.

If it doesn't all fit into RAM then this is probably due to the space 
used by the objects themselves, not the collection (I notice you haven't 
asked how much RAM a String object uses). If it doesn't run fast enough 
then the set/get operations of Array or Hash are almost certainly not 
the culprit.

-- 
Posted via http://www.ruby-forum.com/.