Skip to content

Instantly share code, notes, and snippets.

@halilim
Created October 5, 2016 11:22
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save halilim/688154c1fb399e347b139a2af4f6bb6e to your computer and use it in GitHub Desktop.
require 'set'
def find_uniq(ids)
# O(n) space
# uniqs = Set.new
# ids.each do |id|
# uniqs.delete(id) unless uniqs.add?(id)
# end
# uniqs.first
# O(1) space
ids.reduce(:^)
end
require 'minitest/autorun'
require 'minitest/benchmark'
class FindUniqBenchmark < Minitest::Benchmark
UNIQ = 0
def self.bench_range
bench_linear(10_000, 50_000, 10_000)
end
def setup
@ids = {}
self.class.bench_range.each do |n|
@ids[n] = ((1..n).to_a * 2 << UNIQ).shuffle
end
end
def bench_find_uniq
assert_performance_linear 0.95 do |n|
assert_equal UNIQ, find_uniq(@ids[n])
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment