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(); }