1k.rb

#!/usr/bin/env ruby
require "benchmark"

def method1(ar)
  (ar.first..ar.last).to_a - ar
end

def method2(ar)
  result_ar, prev = [], 0
  ar.each do |e|
    if e-prev > 1
      result_ar << prev + 1
    end
    prev = e
  end

  result_ar
end

def method3(ar)
  ar.unshift(0)
  result_ar = []

  1.upto(ar.size) do |n|
    if ar[n] != n
      ar.insert(n, nil)
      result_ar << n
    end
  end

  result_ar
end

####################################
k = ARGV.first.to_i
ar = (1..k).to_a.sort
2.times { |i| ar.delete(rand(k)) }

Benchmark.bm do |x|
  x.report("method1") { method1(ar) }
  x.report("method2") { method2(ar) }
  x.report("method3") { method3(ar) }
end

1k.sh

#!/bin/bash
rubies=( 1.8.7-p357 1.9.3-p0 2.0.0-dev jruby-1.7.0-dev rbx-2.0.0-dev )
nums=( 1_000 100_000 1_000_000 10_000_000 )

export JRUBY_OPTS="-J-Xmx4096m"

for i in "${rubies[@]}"; do
  export RBENV_VERSION=$i
  ruby -v

  for n in "${nums[@]}"; do
    echo -e "-----------------"
    echo $n numbers
    ruby 1k.rb $n
  done

  echo -e "\n##############################\n"
done

results.txt

ruby 1.8.7 (2011-12-28 patchlevel 357) [i686-darwin11.3.0]
1_000 numbers
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000201)
  0.000000   0.000000   0.000000 (  0.000402)
  0.000000   0.000000   0.000000 (  0.000330)
100_000 numbers
      user     system      total        real
  0.020000   0.000000   0.020000 (  0.022773)
  0.040000   0.000000   0.040000 (  0.040396)
  0.040000   0.000000   0.040000 (  0.033556)
1_000_000 numbers
      user     system      total        real
  0.220000   0.010000   0.230000 (  0.233339)
  0.410000   0.000000   0.410000 (  0.403953)
  0.320000   0.000000   0.320000 (  0.325868)
10_000_000 numbers
      user     system      total        real
  2.250000   0.160000   2.410000 (  2.399936)
  4.190000   0.000000   4.190000 (  4.196070)
  3.680000   0.010000   3.690000 (  3.690308)

##############################

ruby 1.9.3p0 (2011-10-30 revision 33570) [x86_64-darwin11.2.0]
1_000 numbers
       user     system      total        real
   0.000000   0.000000   0.000000 (  0.000349)
   0.000000   0.000000   0.000000 (  0.000086)
   0.000000   0.000000   0.000000 (  0.000098)
100_000 numbers
       user     system      total        real
   0.060000   0.010000   0.070000 (  0.063665)
   0.010000   0.000000   0.010000 (  0.008207)
   0.010000   0.000000   0.010000 (  0.008490)
1_000_000 numbers
       user     system      total        real
   1.130000   0.040000   1.170000 (  1.180170)
   0.110000   0.000000   0.110000 (  0.106023)
   0.090000   0.010000   0.100000 (  0.098330)
10_000_000 numbers
       user     system      total        real
  15.500000   0.550000  16.050000 ( 16.055409)
   0.860000   0.000000   0.860000 (  0.857811)
   0.860000   0.020000   0.880000 (  0.884756)

##############################

ruby 2.0.0dev (2012-01-31 trunk 34404) [x86_64-darwin11.2.0]
1_000 numbers
       user     system      total        real
   0.000000   0.000000   0.000000 (  0.000371)
   0.000000   0.000000   0.000000 (  0.000086)
   0.000000   0.000000   0.000000 (  0.000092)
100_000 numbers
       user     system      total        real
   0.070000   0.010000   0.080000 (  0.066245)
   0.000000   0.000000   0.000000 (  0.008137)
   0.010000   0.000000   0.010000 (  0.007754)
1_000_000 numbers
       user     system      total        real
   1.170000   0.040000   1.210000 (  1.214516)
   0.090000   0.000000   0.090000 (  0.087714)
   0.090000   0.000000   0.090000 (  0.092500)
10_000_000 numbers
       user     system      total        real
  15.240000   0.510000  15.750000 ( 15.745098)
   0.830000   0.000000   0.830000 (  0.825933)
   0.800000   0.020000   0.820000 (  0.881977)

##############################

jruby 1.7.0.dev (ruby-1.9.3-p28) (2012-01-31 564ade1) (Java HotSpot(TM) 64-Bit Server VM 1.7.0_04-ea) [darwin-amd64-java]
1_000 numbers
       user     system      total        real
   0.005000   0.000000   0.005000 (  0.005000)
   0.017000   0.000000   0.017000 (  0.017000)
   0.015000   0.000000   0.015000 (  0.015000)
100_000 numbers
       user     system      total        real
   0.083000   0.000000   0.083000 (  0.083000)
   0.091000   0.000000   0.091000 (  0.091000)
   0.102000   0.000000   0.102000 (  0.102000)
1_000_000 numbers
       user     system      total        real
   0.878000   0.000000   0.878000 (  0.878000)
   0.112000   0.000000   0.112000 (  0.112000)
   0.291000   0.000000   0.291000 (  0.290000)
10_000_000 numbers
       user     system      total        real
  13.797000   0.000000  13.797000 ( 13.797000)
   0.484000   0.000000   0.484000 (  0.484000)
   3.271000   0.000000   3.271000 (  3.271000)

##############################

rubinius 2.0.0dev (1.8.7 9fb8893b yyyy-mm-dd JI) [x86_64-apple-darwin11.2.0]
1_000 numbers
      user     system      total        real
  0.010255   0.000205   0.010460 (  0.004976)
  0.000207   0.000002   0.000209 (  0.000205)
  0.001827   0.000008   0.001835 (  0.000529)
100_000 numbers
      user     system      total        real
  0.580034   0.005120   0.585154 (  0.365458)
  0.022851   0.000085   0.022936 (  0.012636)
  0.102986   0.001031   0.104017 (  0.053959)
1_000_000 numbers
      user     system      total        real
  2.328463   0.031444   2.359907 (  2.111745)
  0.074831   0.000080   0.074911 (  0.063728)
  0.379024   0.009480   0.388504 (  0.274447)
10_000_000 numbers
      user     system      total        real
 45.684542   0.478062  46.162604 ( 45.878151)
  0.576948   0.000155   0.577103 (  0.565413)
  2.044151   0.081127   2.125278 (  2.016974)

##############################