From: Jeff Mitchell <quixoticsycophant@...>
Date: 2004-05-21T01:23:00+09:00
Subject: Re: Ruby's builtin Datastructures


--- Mark Hubbart <discord@mac.com> wrote:
> 
> On May 20, 2004, at 5:23 AM, Brian Schroeder wrote:
> 
> > Thanks for your answer. I should have looked in the raa by myself. 
> > Just a
> > question regarding array as deque. How efficient is it? Is all the data
> > shifted through the array every time I push something at the front and
> > remove it from the back, or is it organized more efficiently?
> 
> One of the great things about ruby is how easy it is to test things 
> like this :)
> 
> mark@imac% ruby
> require 'profile'
> def t_pop(ary)     5000.times{|n| ary.pop}       end
> def t_push(ary)    5000.times{|n| ary.push n}    end
> def t_shift(ary)   5000.times{|n| ary.shift}     end
> def t_unshift(ary) 5000.times{|n| ary.unshift n} end
> 
> a=[]
> t_push a
> t_pop a
> t_unshift a
> t_shift a
>    %   cumulative   self              self     total
>   time   seconds   seconds    calls  ms/call  ms/call  name
>   71.77    11.06     11.06        4  2765.00  3850.00  Integer#times
>    8.37    12.35      1.29     5000     0.26     0.26  Array#unshift
>    7.46    13.50      1.15     5000     0.23     0.23  Array#pop
>    7.40    14.64      1.14     5000     0.23     0.23  Array#push
>    4.93    15.40      0.76     5000     0.15     0.15  Array#shift
>    0.84    15.53      0.13        1   130.00   130.00  
> Profiler__.start_profile
>    0.06    15.54      0.01        1    10.00  3720.00  Object#t_shift
>    0.00    15.54      0.00        4     0.00     0.00  
> Module#method_added
>    0.00    15.54      0.00        1     0.00  3860.00  Object#t_pop
>    0.00    15.54      0.00        1     0.00 15410.00  #toplevel
>    0.00    15.54      0.00        1     0.00  4080.00  Object#t_unshift
>    0.00    15.54      0.00        1     0.00  3750.00  Object#t_push
> 
> 
> Interpretation: it looks like unshift is slightly (~6%) slower than 
> pop. shift is barely faster than push. Still, they are all comparable 
> in speed.
> 
> I ran this test a few times, with similar results.

But look what happens for larger data,
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 56.80    33.00     33.00   100000     0.33     0.33  Array#unshift
 34.77    53.20     20.20        4  5050.00 14525.00  Integer#times
  4.87    56.03      2.83   100000     0.03     0.03  Array#pop
  1.94    57.16      1.13   100000     0.01     0.01  Array#push
  1.62    58.10      0.94   100000     0.01     0.01  Array#shift
  0.02    58.11      0.01        1    10.00    10.00  Profiler__.start_profile
  0.00    58.11      0.00        4     0.00     0.00  Module#method_added
  0.00    58.11      0.00        1     0.00  6520.00  Object#t_pop
  0.00    58.11      0.00        1     0.00  6390.00  Object#t_shift
  0.00    58.11      0.00        1     0.00 58100.00  #toplevel
  0.00    58.11      0.00        1     0.00 39010.00  Object#t_unshift
  0.00    58.11      0.00        1     0.00  6180.00  Object#t_push






	
		
__________________________________
Do you Yahoo!?
Yahoo! Domains � Claim yours for only $14.70/year
http://smallbusiness.promotions.yahoo.com/offer