Array の push/pop/unshift/shift に要する時間(ruby)

ruby の Array は生のメモリに近いものだから、 push と pop は速いけど、 shift と unshift は遅い。

そう思っていたんだけど、思っていただけで測ったことがなかった。

で。測定してみた。

環境は ruby 2.5.0p0

まずはソースコード。

ruby2.5

require "benchmark"

r=Array.new(10) do
  a=[0]*100_000_000
  Array.new(3){  1000*Benchmark.realtime{ 
    a.push 1  # この行を、「a.pop」「a.unshift 1」「a.shift」 に変更する
  }  }
end

puts (0...3).map{ |ix|
  "%.8f|" % ( r.map{ |e| e[ix] }.inject(&:+) / r.size )
}.join

測定結果

	１回目	2回目	3回目
push	0.01390	0.00030	0.00150
pop	0.00370	0.00040	0.00020
unshift	355.36490	0.00140	0.00020
shift	0.00370	0.00010	0.00000

push と pop は、予想通り速い。
でも push の初回はちょっと遅い。なんでだろ。

unshift は、一度目だけが遅い。
おそらく、1要素だけの unshift でも、3つ以上の要素を先頭に追加できるだけのメモリが確保されるのであろう。
shift も速い。メモリの移動はせず、先頭を指すポインタを動かしているのであろう。

というわけで、当初の予想は極一部しか当たっていなかった。

おまけの実験

せっかくなので

ruby2.5

require "benchmark"

r=Array.new(10) do
  a=[0]*100_000_000
  [
    Benchmark.realtime{ a.shift }, #1
    Benchmark.realtime{ a.shift }, #2
    Benchmark.realtime{ a.unshift 3 }, #3
    Benchmark.realtime{ a.unshift 4 }, #4
    Benchmark.realtime{ a.unshift 5 }, #5
    Benchmark.realtime{ a.unshift 6 }, #6
  ].map{ |x| x*1000 }
end

puts (0...6).map{ |ix|
  "%.5f|" % ( r.map{ |e| e[ix] }.inject(&:+) / r.size )
}.join

という実験をしてみた。
結果は

#1(shift)	#2(shift)	#3(unshift)	#4(unshift)	#5(unshift)	#6(unshift)
0.00460	0.00090	0.00090	453.12790	0.00190	0.00070

こんな感じ。

あれ？　#5 が遅いんじゃないの？？