benchmark

"SortedSet" behaves like "Array (sorted after every insert)"

Rehearsal ---------------------------------------------------------------------
Array (unsorted)                    0.300000   0.000000   0.300000 (  0.303850)
Set (unsorted)                      0.000000   0.000000   0.000000 (  0.000616)
Array (sorted once)                 0.300000   0.000000   0.300000 (  0.299126)
Array (sorted after every insert)   0.680000   0.000000   0.680000 (  0.690640)
SortedSet                           0.090000   0.010000   0.100000 (  0.108973)
------------------------------------------------------------ total: 1.380000sec

                                        user     system      total        real
Array (unsorted)                    0.300000   0.000000   0.300000 (  0.300900)
Set (unsorted)                      0.000000   0.000000   0.000000 (  0.000622)
Array (sorted once)                 0.320000   0.000000   0.320000 (  0.322210)
Array (sorted after every insert)   0.670000   0.000000   0.670000 (  0.676785)
SortedSet                           0.010000   0.000000   0.010000 (  0.003351)

code.rb

require 'benchmark'
require 'set'

seed_data = 2000.times.map { rand(100000) }

Benchmark.bmbm do |x|
  x.report 'Array (unsorted)' do
    list = []
    seed_data.each do |element|
      list << element unless list.include? element
    end
  end

  x.report 'Set (unsorted)' do
    list = []
    seed_data.each do |element|
      list << element
    end
  end

  x.report 'Array (sorted once)' do
    list = []
    seed_data.each do |element|
      list << element unless list.include? element
    end
    list.sort!
  end

  x.report 'Array (sorted after every insert)' do
    list = []
    seed_data.each do |element|
      list << element unless list.include? element
      list.sort!
    end
  end

  x.report 'SortedSet' do
    list = SortedSet.new
    seed_data.each do |element|
      list << element
    end
  end
end