Arrays and Lists ?

Discussion in 'Ruby' started by Emil Macarie, Dec 19, 2010.

  1. Emil Macarie

    Emil Macarie Guest

    I have recently started playing around with Ruby, and now I am starting
    to use it for more serious projects.
    I am working on a program that works with quite a bit of data that is
    originally stored in array format.
    I want to be able to loop through my original data and add or remove
    elements.
    In another language I would create a linked list, loop through the
    original array and add what I need to the list.
    However, Ruby seems to lump Arrays and Lists into one object.
    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.
    That means that if I want to start with an empty list and insert
    10,000 elements, 10,000 arrays will be created out of which I would only
    care about the final one.

    If that is the case how should I (starting with 0 elementS) append and
    create a large linked list ?

    This is my impression of what is happening and please help me clear up
    any misconceptions I may have. I have scoured Google to some sort of
    article about the intention of the Ruby Array class with no luck.

    --
    Posted via http://www.ruby-forum.com/.
     
    Emil Macarie, Dec 19, 2010
    #1
    1. Advertising

  2. On Sun, Dec 19, 2010 at 10:01 AM, Emil Macarie <> wro=
    te:

    > =A0I 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.
    > =A0That means that if I want to start with an empty list and insert
    > 10,000 elements, 10,000 arrays will be created out of which I would only
    > care about the final one.


    Forgive me if I'm misunderstanding your point, but --

    >> things =3D Array.new

    =3D> []
    >> things.object_id

    =3D> 2163798080
    >> things << Object.new

    =3D> [#<Object:0x101f12668>]
    >> things

    =3D> [#<Object:0x101f12668>]
    >> things.object_id

    =3D> 2163798080
    >>


    No new Array is being created by adding an element to the Array.

    --=20
    Hassan Schroeder ------------------------
    twitter: @hassan
     
    Hassan Schroeder, Dec 19, 2010
    #2
    1. Advertising

  3. 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.

    > If that is the case how should I (starting with 0 elementS) append and
    > create a large linked list ?


    Just append to an empty Array. And relax :)

    --
    Posted via http://www.ruby-forum.com/.
     
    Brian Candler, Dec 19, 2010
    #3
  4. Emil Macarie

    Emil Macarie Guest

    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.
    >
    >> If that is the case how should I (starting with 0 elementS) append and
    >> create a large linked list ?

    >
    > Just append to an empty Array. And relax :)


    Thanks ! That does make me feel better about using an array as a list
    for now. I will have to take a look at the source code as I am curious
    it all works.
    As for relaxing, I do try :), but the amount of times I've seen people
    make these kinds of mistakes has made me rather thin skinned.

    --
    Posted via http://www.ruby-forum.com/.
     
    Emil Macarie, Dec 19, 2010
    #4
  5. 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/.
     
    Peter Vandenabeele, Dec 19, 2010
    #5
  6. Emil Macarie

    Walton Hoops Guest

    On 12/19/2010 02:03 PM, Peter Vandenabeele wrote:
    > 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 :)

    Also, Ruby is using realloc to resize the array, meaning it tries to
    grow it in place and only copy if it has to. I won't even try to
    speculate on how often it manages to grow in place, but it does mean in
    the best-case scenario there is no moving cost.
     
    Walton Hoops, Dec 20, 2010
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    425
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  2. Daniel Nogradi
    Replies:
    3
    Views:
    356
    Dennis Lee Bieber
    Nov 10, 2006
  3. Gabriel Zachmann

    Bug with lists of pairs of lists and append()

    Gabriel Zachmann, Sep 28, 2007, in forum: Python
    Replies:
    2
    Views:
    241
    Gabriel Zachmann
    Oct 1, 2007
  4. Gabriel Zachmann

    Bug with lists of pairs of lists and append()

    Gabriel Zachmann, Sep 28, 2007, in forum: Python
    Replies:
    5
    Views:
    269
    Gabriel Zachmann
    Oct 1, 2007
  5. Philipp
    Replies:
    21
    Views:
    1,157
    Philipp
    Jan 20, 2009
Loading...

Share This Page