Last active
September 15, 2016 19:25
-
-
Save davingee/5ca840e57b91a1ff3080377768f10ab2 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'pry' | |
require 'benchmark' | |
require 'benchmark-memory' | |
class Array | |
def top_occurrence_0(k) | |
counter = Hash.new{ |k, v| k[ v ] = 0 } | |
self.each { |id| counter[ id ] += 1 } | |
counter.sort_by{ |id, counts| -counts }[0, k].map{ |id_count| id_count[0] } | |
end | |
def top_occurrence_1(k) | |
self.each_with_object( Hash.new( 0 ) ) do |id, counter| | |
counter[ id ] += 1 | |
end.sort_by do |id, counts| | |
-counts | |
end[0, k].map do |id_count| | |
id_count[0] | |
end | |
end | |
def top_occurrence_2(k) | |
self.group_by do |id| | |
id | |
end.sort_by do |id, counts| | |
-counts.count | |
end.first( k ).map do |id_count| | |
id_count[0] | |
end | |
end | |
def top_occurrence_3(k) | |
counter = Hash.new{ |k, v| k[ v ] = 0 } | |
self.each do |id| | |
counter[ id ] += 1 | |
end | |
counter.sort_by do |id, counts| | |
-counts | |
end[0, k].map do |id_count| | |
id_count[0] | |
end | |
end | |
def top_occurrence_4(k) | |
self.each_with_object( Hash.new( 0 ) ) do |id, counter| | |
counter[ id ] += 1 | |
end.sort_by do |id, counts| | |
-counts | |
end.to_h.keys[0, k] | |
end | |
def self.test_a_method( args = {} ) | |
puts args[:array].send( args[:method], args[:k] ) | |
end | |
def self.benchmark( args = {} ) | |
Benchmark.bm do |x| | |
[ 0, 1, 2, 3, 4 ].each do |n| | |
x.report("top_occurrence_#{ n }") { args[:array].send("top_occurrence_#{ n }", args[:k]) } | |
end | |
end | |
end | |
def self.benchmark_mem( args = {} ) | |
Benchmark.memory do |x| | |
[ 0, 1, 2, 3, 4 ].each do |n| | |
x.report("top_occurrence_#{ n }") { args[:array].send("top_occurrence_#{ n }", args[:k]) } | |
end | |
x.compare! | |
end | |
end | |
end | |
k = 3 | |
array = [ 1,1, 3, 4, 6, 7,3, 1, 6, 8, 8, 8, 8, 8, 2, 1 ] * 1000000 | |
Array.benchmark(k: k, array: array) | |
Array.benchmark_mem(k: k, array: array) | |
# Array.test_a_method(k: k, array: array, method: :top_occurrence_1) | |
# array.top_occurrence_1(3) | |
# user system total real | |
# top_occurrence_0 2.330000 0.010000 2.340000 ( 2.343289) | |
# top_occurrence_1 2.940000 0.010000 2.950000 ( 2.949879) | |
# top_occurrence_2 2.370000 0.080000 2.450000 ( 2.458058) | |
# top_occurrence_3 2.710000 0.000000 2.710000 ( 2.719345) | |
# top_occurrence_4 3.340000 0.020000 3.360000 ( 3.364670) | |
# Calculating ------------------------------------- | |
# top_occurrence_0 1.488k memsize ( 0.000 retained) | |
# 15.000 objects ( 0.000 retained) | |
# 2.000 strings ( 0.000 retained) | |
# top_occurrence_1 1.232k memsize ( 0.000 retained) | |
# 13.000 objects ( 0.000 retained) | |
# 2.000 strings ( 0.000 retained) | |
# top_occurrence_2 168.000M memsize ( 0.000 retained) | |
# 20.000 objects ( 0.000 retained) | |
# 2.000 strings ( 0.000 retained) | |
# top_occurrence_3 1.488k memsize ( 0.000 retained) | |
# 15.000 objects ( 0.000 retained) | |
# 2.000 strings ( 0.000 retained) | |
# top_occurrence_4 1.800k memsize ( 0.000 retained) | |
# 14.000 objects ( 0.000 retained) | |
# 2.000 strings ( 0.000 retained) | |
# | |
# Comparison: | |
# top_occurrence_1: 1232 allocated | |
# top_occurrence_0: 1488 allocated - 1.21x more | |
# top_occurrence_3: 1488 allocated - 1.21x more | |
# top_occurrence_4: 1800 allocated - 1.46x more | |
# top_occurrence_2: 168000304 allocated - 136363.88x more |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment