Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Benchmarks comparing ruby's SortedSet implemented with and without the rbtree extension.
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)
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.