From: Peter Vandenabeele <peter@...>
Date: 2010-12-20T06:03:23+09:00
Subject: Re: Arrays and Lists ?

Brian Candler wrote in post #969420:
> Emil Macarie wrote in post #969413:
>>   I do see the Array class has an insert method, however assuming that
>> the implementation of an Array is actually a contiguous array in memory,
>> the insert method will create a new copy of an array with the insert
>> element appended.
>
> Nope. It grows the memory space, and shuffles the existing elements if
> necessary (if you're inserting into the middle rather than at the end).
>
> I believe it also grows the memory space by more than is needed, so that
> 10,000 inserts don't require 10,000 grows.

These are the relevant pieces of code in array.c (ruby trunk)

static VALUE
rb_ary_push_1(VALUE ary, VALUE item)
{
    long idx = RARRAY_LEN(ary);

    if (idx >= ARY_CAPA(ary)) {
        ary_double_capa(ary, idx);
/* dirty hack ... sorry couldn't get cleaner solution to work */
        rb_define_global_const("ARRAY_CAPACITY",
INT2FIX(ARY_CAPA(ary)));
/* end of dirty hack */
    }
    RARRAY_PTR(ary)[idx] = item;
    ARY_SET_LEN(ary, idx + 1);
    return ary;
}
...
static void
ary_double_capa(VALUE ary, long min)
{
    long new_capa = ARY_CAPA(ary) / 2;

    if (new_capa < ARY_DEFAULT_SIZE) {
        new_capa = ARY_DEFAULT_SIZE;
    }
    if (new_capa >= ARY_MAX_SIZE - min) {
        new_capa = (ARY_MAX_SIZE - min) / 2;
    }
    new_capa += min;
    ary_resize_capa(ary, new_capa);
}

And with this little bit of dirty hacking I found that the
growing of the array (ary_double_capa) is called at these
values of idx:
007:0> a = Array(0)
008:0> (0..10000).each do  |i|
009:1* a << ARRAY_CAPACITY
010:1> end
011:0> b = a.uniq #=> [0, 19, 35, 52, 78, 117, 175, 262, 393, 589, 883,
1324, 1986, 2979, 4468, 6702, 10053]
...
023:0> c = []
024:0> b.each_with_index{|v,i| c << ((v*1.0)/b[i-1]) if i > 1 }
...
033:0> c.map{|ratio| "%5.3f" % ratio}
=> ["1.842", "1.486", "1.500", "1.500", "1.496", "1.497", "1.500",
"1.499", "1.499", "1.499", "1.500", "1.500", "1.500", "1.500", "1.500",
"1.842", "1.486", "1.500", "1.500", "1.496", "1.497", "1.500", "1.499",
"1.499", "1.499", "1.500", "1.500", "1.500", "1.500", "1.500"]

So, it is the array capacity is growing exponentially with approx.
50% growth per call (which could be expected from the implementation
of ary_double_capa).

If I understand correctly, this means that the cost of moving the
data around as the array grows is O(n.log(n)).

The more I see of this, the more I love Ruby :-)

HTH,

Peter

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