public
Created

Benchmarks comparing ruby's SortedSet implemented with and without the rbtree extension.

  • Download Gist
sorted-set-bench.out
1 2 3 4 5 6 7 8
Rehearsal ----------------------------------------------------------------------------
SortedSetRBTree#add and #first 0.040000 0.000000 0.040000 ( 0.039830)
SortedSetNoRBTree#add and #first 17.180000 0.360000 17.540000 ( 17.567993)
------------------------------------------------------------------ total: 17.580000sec
 
user system total real
SortedSetRBTree#add and #first 0.050000 0.000000 0.050000 ( 0.042851)
SortedSetNoRBTree#add and #first 36.200000 0.670000 36.870000 ( 36.914300)
sorted-set-bench.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108
require 'set'
require 'rbtree'
 
# This is stdlib SortedSet if the `require 'rbtree'` succeeds.
class SortedSetRBTree < Set
class << self
def [](*ary) # :nodoc:
new(ary)
end
end
 
def initialize(*args)
@hash = RBTree.new
super
end
 
def add(o)
o.respond_to?(:<=>) or raise ArgumentError, "value must respond to <=>"
super
end
alias << add
end
 
# This is stdlib SortedSet if the `require 'rbtree'` fails with LoadError.
class SortedSetNoRBTree < Set
class << self
def [](*ary) # :nodoc:
new(ary)
end
end
 
def initialize(*args)
@keys = nil
super
end
 
def clear
@keys = nil
super
end
 
def replace(enum)
@keys = nil
super
end
 
def add(o)
o.respond_to?(:<=>) or raise ArgumentError, "value must respond to <=>"
@keys = nil
super
end
alias << add
 
def delete(o)
@keys = nil
@hash.delete(o)
self
end
 
def delete_if
block_given? or return enum_for(__method__)
n = @hash.size
super
@keys = nil if @hash.size != n
self
end
 
def keep_if
block_given? or return enum_for(__method__)
n = @hash.size
super
@keys = nil if @hash.size != n
self
end
 
def merge(enum)
@keys = nil
super
end
 
def each(&block)
block or return enum_for(__method__)
to_a.each(&block)
self
end
 
def to_a
(@keys = @hash.keys).sort! unless @keys
@keys
end
end
 
if __FILE__ == $0
require 'benchmark'
 
Benchmark.bmbm(40) do |b|
[SortedSetRBTree, SortedSetNoRBTree].each do |set_class|
srand 7654321
s = set_class.new
xs = (0..10000).to_a.shuffle
 
b.report("#{set_class}#add and #first") {
xs.each {|x| s.add(x); s.first }
}
end
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.