benchmark

"SortedSet" behaves like "Array (sorted after every insert)" and "(insert in place)".

Rehearsal ---------------------------------------------------------------------
Array (unsorted)                    0.120000   0.000000   0.120000 (  0.120734)
Set (unsorted)                      0.000000   0.000000   0.000000 (  0.000302)
Array (sorted once)                 0.130000   0.000000   0.130000 (  0.121996)
Array (sorted after every insert)   0.350000   0.000000   0.350000 (  0.355280)
SortedSet                           0.120000   0.030000   0.150000 (  0.151816)
Array (insert in place)             0.090000   0.000000   0.090000 (  0.093471)
------------------------------------------------------------ total: 0.840000sec

                                        user     system      total        real
Array (unsorted)                    0.120000   0.000000   0.120000 (  0.122492)
Set (unsorted)                      0.000000   0.000000   0.000000 (  0.000327)
Array (sorted once)                 0.120000   0.000000   0.120000 (  0.122906)
Array (sorted after every insert)   0.360000   0.000000   0.360000 (  0.385497)
SortedSet                           0.000000   0.000000   0.000000 (  0.001511)
Array (insert in place)             0.090000   0.000000   0.090000 (  0.093302)

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

  x.report 'Array (insert in place)' do
    list = []
    seed_data.each do |element|
      idx = list.index { |x| x > element } || 0
      list.insert(idx, element)
    end
  end
end

...but it doesn't scale and this is what is important.

                                        user     system      total        real
Array (unsorted)                    3.420000   0.000000   3.420000 (  8.119942)
Set (unsorted)                      0.000000   0.000000   0.000000 (  0.002853)
Array (sorted once)                 3.430000   0.010000   3.440000 (  7.565435)
Array (sorted after every insert)  11.610000   0.010000  11.620000 ( 15.405632)
SortedSet                           0.020000   0.000000   0.020000 (  0.030547)
Array (insert in place)             0.970000   0.010000   0.980000 (  1.394989)

Yeah, although I'm not quite sure what we're trying to tell @telemachus here :P

I don't know what you try to tell who and why :)
I just meant that one has to choose the data structure wisely. Arrays are very efficient for small datasets.

Also, SortedSet will automatically use rbtree if available, not sure how big the speed up is, though.

Also, SortedSet will automatically use rbtree if available, not sure how big the speed up is, though.

Now that is a pleasant surprise!

The code is slightly disturbing, though, everything is in strings passed to module_eval.

Wow. That is disturbing: https://github.com/ruby/ruby/blob/trunk/lib/set.rb#L514