Skip to content

Instantly share code, notes, and snippets.

@CaDs
Created April 14, 2018 02:14
Show Gist options
  • Save CaDs/ec0c630b69d76b2462fd1a98dc9d51e3 to your computer and use it in GitHub Desktop.
Save CaDs/ec0c630b69d76b2462fd1a98dc9d51e3 to your computer and use it in GitHub Desktop.
john_lynch_scrtip
def get_partition_original(ss)
return (ss.size == 0 ? [[[] of Int32]] : [[ss]]) if ss.size <= 1
out = [[Array(Int32).new, Array(Int32).new]].clear
(0...2**ss.size / 2).each { |i|
parts = [Array(Int32).new, Array(Int32).new]
ss.each { |item|
parts[i&1] << item
i >>= 1
}
get_partition_original(parts[1]).each { |b|
out << (b[0].empty? ? [parts[0]] : [parts[0]] + b)
}
}
out
end
def get_partition(ss)
return (ss.size == 0 ? [[[] of Int32]] : [[ss]]) if ss.size <= 1
out = [] of Array(Array(Int32))
(0...2**ss.size / 2).each do |i|
parts = [[] of Int32, [] of Int32]
ss.each do |item|
parts[i&1] << item
i >>= 1
end
get_partition(parts[1]).each do |b|
out << (b[0].empty? ? [parts[0]] : [parts[0]] + b)
end
end
out
end
require "benchmark"
part = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Benchmark.ips do |x|
x.report("original implementation") { get_partition_original(part) }
x.report("new implementation") { get_partition(part) }
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment