RubyのArrayのunshiftはpushと比べて同じだったり遅かったりする
最初に
自分の整理のためにRubyのArrayのpushとunshiftの速さについて書く。
結論からいうと、Array#unshiftは、pushと同じ並の速さをだすこともあれば、格段に遅くなることもある。
他の言語だと遅いが、RubyのArray#unshiftは速い
C++のvectorにはpush_backとpop_backという末尾への追加と取り出しはあるが、
先頭への追加・取り出しのpush_frontとpop_frontはない。
これはC++のvectorが、末尾への追加・取り出しは高速にできるが、先頭への追加・取り出しは容易にできないデータ構造だから、実装されてないと考えられる。
これは、他の言語でも似たようなことが言えて、JavaScriptやPythonでの基本的な配列(≒リスト)では先頭への追加・取り出しと末尾への追加・取り出しの両方が用意されているのが、後者が明らかに遅いようだ。
しかし、Rubyの末尾追加であるArray#unshiftは、必ずしも遅いわけではない。(遅いケースもあるのだが)
2019/07 RubyのArray#unshiftが速すぎる件と償却解析
実際、こういった記事を読んだり、経験などから、
Rubyの末尾追加であるArray#unshift (prepend)は、Array#push (append)と同等のスピードである、と感じていた。
すごく単純な時間計測をするとunshiftとpushを比べてみると、同等のスピードであることがわかる。
require 'benchmark' n = 10**5 Benchmark.bm(10) do |r| r.report("empty-loop"){ |i| a = []; n.times{ } } r.report("push "){ |i| a = []; n.times{ a.push(0) } } r.report("unshift "){ |i| a = []; n.times{ a.unshift(0) } } end # user system total real # empty-loop 0.002462 0.000000 0.002462 ( 0.002460) # push 0.005110 0.000000 0.005110 ( 0.005112) # unshift 0.005339 0.000000 0.005339 ( 0.005341)
上記の例では、10**5(100,000)個の要素を追加するのに、末尾追加でも先頭追加でも0.005秒かかっている。
同じループ数で空のループが0.0025秒で、pushでもunshiftでもO(1)の時間計算量であるといえそう。
ところで、ここで思うのは、単純な比較だが、要素を追加していく処理とループ処理がザックリ0.0025秒ほどで、 ループ処理は意外にけっこう重たい処理なように感じる。
こういうわけで、自分はpushとunshiftは常にO(1)の時間計算量であると思っていた。(これは誤りであった。)
RubyのArrayのunshiftは、やっぱり遅い一面がある。
競技プログラミングの「競プロ典型 90 問」の44問目の問題を解いて、unshiftは常に速いとは限らないことがわかった。
下記の例では、a[0] = 0という破壊的操作を加えた上に、同じように10**5個の要素を追加している。
しかし、明らかにunshiftが遅い。
require 'benchmark' n = 10**5 Benchmark.bm(8) do |r| r.report("= & push "){ |i| a = []; n.times{ a[0] = 0; a.unshift(0) } } r.report("= & unshift "){ |i| a = []; n.times{ a[0] = 0; a.push(0) } } end # user system total real # = & push 0.006590 0.000000 0.006590 ( 0.006592) # = & unshift 2.215506 0.000655 2.216161 ( 2.216260)
pushの方が0.0065秒、unshiftの方が2.2秒。
単純な比較ではpushとunshiftは同等の速さであったが、
a[0] = 0と破壊的操作を1つ加えるだけでunshiftが100倍以上も遅い結果となった。
pushは常にO(1)のようだが、unshiftは破壊的操作が加わると計算量がO(n)とかに変わるようでかなり遅くなっている。
最後に
Array#unshiftは、pushと同じ並のO(1)の速さをだすこともあれば、異常に遅い速さになることもなることがわかった。
気軽にunshiftを使うときは、破壊的操作をしてないか、遅くなってないかに気を配る必要がありそうだ。
最後になりますが、ruby-jpやTwitterで、mameさん、climpetさん、kuma kumaさん、tompngさん、superrino130さん等から、アドバイスや意見を貰え、とても参考になり感謝してます。
