Skip to content

Instantly share code, notes, and snippets.

@dresselm
Last active December 20, 2015 08:19
Show Gist options
  • Save dresselm/6099437 to your computer and use it in GitHub Desktop.
Save dresselm/6099437 to your computer and use it in GitHub Desktop.
Solution1 valid: true
Solution1: 2.280000 0.000000 2.280000 ( 2.275380)
Solution2 valid: true
solution2: 1.220000 0.000000 1.220000 ( 1.222917)
Solution3 valid: true
solution3: 1.470000 0.010000 1.480000 ( 1.481871)
Solution4 valid: true
solution4: 2.080000 0.000000 2.080000 ( 2.075977)
=> [
2.280000 0.000000 2.280000 ( 2.275380),
1.220000 0.000000 1.220000 ( 1.222917),
1.470000 0.010000 1.480000 ( 1.481871),
2.080000 0.000000 2.080000 ( 2.075977)
]
require 'benchmark'
test_array = [
{"timestamp"=>1347119549, "category"=>nil},
{"timestamp"=>1347119547, "category"=>"Monkeys"},
{"timestamp"=>1347119543, "category"=>nil},
{"timestamp"=>1347119542, "category"=>"Monkeys"},
{"timestamp"=>1347119548, "category"=>"Dog"},
{"timestamp"=>1347119544, "category"=>"Dog"}
].freeze
def solution1(orig)
grouped = orig.group_by { |x| x["category"] ? x["category"] : Object.new }
# Sort the siblings within the groups (note negation causes reverse order)
grouped.values.each { |siblings| siblings.sort_by! { |a| -a["timestamp"] } }
# Sort the list by first (i.e. "best" sort order) timestamp in each group
sorted_groups = grouped.sort_by { |group_id,siblings| -siblings.first["timestamp"] }
# Remove group ids and flatten the list:
sorted_groups.map { |group_id,siblings| siblings }.flatten
end
def solution2(arr)
sorted = arr.sort_by { |elem| 0 - elem['timestamp'] }
groups = sorted.group_by { |elem| elem['category'] or Object.new }
groups.values.flatten
end
def solution3(a)
groups = a.sort_by {|h| -h['timestamp']}.group_by {|h| h['category']}
sorted = (groups.delete(nil) || []) + groups.values
sorted.sort_by{|i| i.is_a?(Hash) ? -i['timestamp'] : -i.first['timestamp']}.flatten
end
def solution4(ar)
ar.group_by{|h| h['category'] ? h['category'] : h['timestamp']}.
map{|k,v| v.sort_by{|h| -h['timestamp']}}.
sort_by{|a| -a[0]['timestamp']}.flatten
end
n = 100000
Benchmark.bm do |benchmark|
puts solution1(test_array)
benchmark.report('solution1: ') { n.times { solution1(test_array) } }
puts solution2(test_array)
benchmark.report('solution2: ') { n.times { solution2(test_array) } }
puts solution3(test_array)
benchmark.report('solution3: ') { n.times { solution3(test_array) } }
puts solution4(test_array)
benchmark.report('solution4: ') { n.times { solution4(test_array) } }
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment