simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

Rubyのcompact

Array#compactメソッドは配列の要素からnilを取り除くメソッドです。compact!だと自身も変更します。

array = [ 1, nil, 3, nil, 5 ]

p array
p array.compact
p array

array.compact!
p array
[1, nil, 3, nil, 5]
[1, 3, 5]
[1, nil, 3, nil, 5]
[1, 3, 5]

要素からnilを排除するときに使用します。

実行速度が気になった

配列のサイズを大きくして速度を測ってみました。測定方法として、Rubyでは添字に値を入れるとそれ以前の値をnilで埋めてくれるので、それをcompactメソッドを使用して消しています。

array = []
array[5] = 1
p array
[nil, nil, nil, nil, nil, 1]

array[5]より前の値がnilになっていることがわかる


require 'benchmark'

Benchmark.bm do |x|
  10.times do |i|
    puts "Array size = #{10**i}"
    x.report do
      array = []
      array[10**i-1] = 1
      array.compact!
    end
  end
end
       user     system      total        real
Array size = 1
   0.000000   0.000000   0.000000 (  0.000009)
Array size = 10
   0.000000   0.000000   0.000000 (  0.000004)
Array size = 100
   0.000000   0.000000   0.000000 (  0.000005)
Array size = 1000
   0.000000   0.000000   0.000000 (  0.000005)
Array size = 10000
   0.000000   0.000000   0.000000 (  0.000060)
Array size = 100000
   0.000000   0.000000   0.000000 (  0.000568)
Array size = 1000000
   0.010000   0.000000   0.010000 (  0.007023)
Array size = 10000000
   0.020000   0.030000   0.050000 (  0.052151)
Array size = 100000000
   0.200000   0.270000   0.470000 (  0.475037)
Array size = 1000000000
   1.970000   2.840000   4.810000 (  4.805006)

実装見る限りだと、配列を線形探索してnil排除してる感じだったので、こんなものなのかなーと思います。

ちなみに最後の10億の配列はメモリが5G近く奪われました。