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.

cheers,
--Mark