Skip to content

Instantly share code, notes, and snippets.

@chulkilee
Created March 6, 2014 19:07
Show Gist options
  • Save chulkilee/9397051 to your computer and use it in GitHub Desktop.
Save chulkilee/9397051 to your computer and use it in GitHub Desktop.
Find duplicates in an array
require 'benchmark'
require 'set'
array_size = (ENV['TOTAL'] || 1_000_000).to_i
max_int = array_size / 5
array = 1.upto(array_size).map { rand(max_int) }
if ENV['CHECK']
@correct = array.group_by { |e| e }.select { |k, v| v.size > 1 }.keys.sort
end
def check_answer(answer)
if ENV['CHECK']
puts '[Checking answer]'
fail 'Wrong answer' unless answer.to_a.sort == @correct
end
end
Benchmark.bmbm do |x|
x.report 'group_by.select.keys (greater than)' do
check_answer array.group_by { |e| e }.select { |k, v| v.size > 1 }.keys
end
x.report 'group_by.select.keys (not equal)' do
check_answer array.group_by { |e| e }.select { |k, v| v.size != 1 }.keys
end
x.report 'sort.chunk.select (not equal)' do
check_answer array.sort.chunk { |e| e }.select { |e, count| count.size != 1 }.map(&:first)
end
x.report 'sort.chunk.select (greater than)' do
check_answer array.sort.chunk { |e| e }.select { |e, count| count.size > 1 }.map(&:first)
end
x.report 'iterate with set' do
found = Set.new
duplicates = Set.new
array.select do |e|
if found.member?(e)
duplicates.add(e)
false
else
found.add(e)
true
end
end
check_answer duplicates
end
if ENV['SLOW']
x.report 'select.rindex' do
check_answer array.select { |e| array.rindex(e) != array.index(e) }.uniq
end
x.report 'select.count.uniq' do
check_answer array.select { |e| array.count(e) > 1 }.uniq
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment