require 'benchmark' | |
require 'tsort' | |
def TSort.tsort_each_enum(each_node, each_child) # :yields: node | |
return to_enum(__method__, each_node, each_child) unless block_given? | |
TSort.each_strongly_connected_component(each_node, each_child) {|component| | |
if component.size == 1 | |
yield component.first | |
else | |
raise Cyclic.new("topological sort failed: #{component.inspect}") | |
end | |
} | |
end | |
n = 1_000 | |
g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]} | |
each_node = lambda {|&b| g.each_key(&b) } | |
each_child = lambda {|n, &b| g[n].each(&b) } | |
Benchmark.bmbm do |x| | |
x.report('each array') { | |
n.times do | |
r = [] | |
TSort.tsort_each(each_node, each_child) {|n| r << n } | |
r | |
end | |
} | |
x.report('to_a') { | |
n.times do | |
TSort.tsort_each_enum(each_node, each_child).to_a | |
end | |
} | |
end |
~/t/ruby-perf ❯❯❯ ruby -v | |
ruby 2.1.3p242 (2014-09-19 revision 47630) [x86_64-darwin14.0] | |
~/t/ruby-perf ❯❯❯ ruby enum_tsort.rb | |
Rehearsal ---------------------------------------------- | |
each array 0.780000 0.020000 0.800000 ( 0.802514) | |
to_a 0.390000 0.020000 0.410000 ( 0.408910) | |
------------------------------------- total: 1.210000sec | |
user system total real | |
each array 0.820000 0.010000 0.830000 ( 0.831467) | |
to_a 0.380000 0.010000 0.390000 ( 0.393889) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment