Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

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

View 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)
View sorted-set-bench.out
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.