From: Ara.T.Howard@...
Date: 2005-04-23T10:54:32+09:00
Subject: Re: Question: Time efficiency of Array <<

On Sat, 23 Apr 2005, Eric Hodel wrote:

> --Apple-Mail-8-618338431
> Content-Transfer-Encoding: 7bit
> Content-Type: text/plain; charset=US-ASCII; format=flowed
>
> On 22 Apr 2005, at 17:31, Peter Suk wrote:
>
>> Forgive the newbie-ish question.  I have been playing around with
>> Array, and discovered the << operator:
>>
>> irb(main):001:0> array = [1, 2, 3, 4]
>> => [1, 2, 3, 4]
>> irb(main):002:0> array2 = array << 5
>> => [1, 2, 3, 4, 5]
>> irb(main):003:0> array
>> => [1, 2, 3, 4, 5]
>> irb(main):004:0> array2
>> => [1, 2, 3, 4, 5]
>> irb(main):005:0>
>>
>> I am curious about the time & space complexity of n << operations to
>> an array.  Is it O(n^2) or is it O(n)?  Is there a doubling of
>> allocated space going on behind the scenes?
>
> Take a look at rb_ary_store in array.c...
>
> It looks like an Array grows by half of its current capacity when an
> index is larger than the current capacity, but by no less than
> ARY_DEFAULT_SIZE (16 elements).

so i guess it's since that's the worst case.  note that one can avoid via

   a = Array::new(mb = 2 ** 20)
   a.size.times{|i| a[i] = method i}

unless storing nil is required...

interestingly real-world time with largish values is better for array than a
container with O(log n) performance:

   harp:~ > cat a.rb
   require 'rbtree'
   def time label
     a = Time::now.to_f
     fork{ yield } and Process::wait
     b = Time::now.to_f
     puts "#{ label } @ #{ b - a }"
   end

   n = 2 ** 20

   time('rbtree2array') do
     rbtree = RBTree::new
     n.times{|i| rbtree[i] = rand}
     array = rbtree.values
   end

   time('array <<') do
     array = []
     n.times{|i| array << rand}
   end

   harp:~ > ruby a.rb
   rbtree2array @ 8.43025994300842
   array << @ 1.26344704627991

who knew.  perhaps function call overhead ends up being responsible for the
difference.

-a
-- 
===============================================================================
| email   :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone   :: 303.497.6469
| although gold dust is precious, when it gets in your eyes, it obstructs
| your vision. --hsi-tang
===============================================================================