From: Saynatkari <ruby-ml@...>
Date: 2005-04-23T11:48:22+09:00
Subject: Re: Question: Time efficiency of Array <<


Le 23/4/2005, "Ara.T.Howard@noaa.gov" <Ara.T.Howard@noaa.gov> a �crit:
>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:

I think it is a bit of a stretch to call the following test
'real-world' :) That being said, Array does perform well.

Remember that an rb-tree is O(log n) for insertion, deletion
_and_ search, and it can be treated as sparse.

>   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

As a sidenote, you can use Benchmark for convenient timing:

require 'benchmark'
Benchmark.bm do |bench|
  # Setup
  # ...
  bench.report { # test1 }
  bench.report { # test2 }
  # ...
end

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

In your test, it most likely suffers from allocating
memory piecemeal rather than in chunks. Not sure how
effectively one could preallocate for a tree.

>-a

E

--
template<typename duck>
void quack(duck& d) { d.quack(); }