Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Array duplicates test
require 'benchmark/ips'
def find_one_using_group_by_select(array)
array.group_by{ |e| e }.detect { |k, v| k if v.size > 1 }&.first
end
def find_one_using_chunk_select(array)
array.sort.chunk{ |e| e }.detect { |e, chunk| chunk.size > 1 }&.first
end
def find_one_using_count_select(array)
array.detect{ |e| array.count(e) > 1 }
end
def find_one_using_hash_map(array)
map = {}
dup = nil
array.each do |v|
map[v] = (map[v] || 0 ) + 1
if map[v] > 1
dup = v
break
end
end
return dup
end
def find_all_using_group_by_select(array)
array.group_by{ |e| e }.select { |k, v| k if v.size > 1 }.map &:first
end
def find_all_using_chunk_select(array)
array.sort.chunk{ |e| e }.select { |e, chunk| chunk.size > 1 }.map &:first
end
def find_all_using_count_select(array)
array.select{ |e| array.count(e) > 1 }.uniq
end
def find_all_using_hash_map(array)
map = {}
dup = []
array.each do |v|
map[v] = (map[v] || 0 ) + 1
if map[v] == 2
dup << v
end
end
return dup
end
num_array = Array.new(1000) { rand 1000 }
char_array = Array.new(20) { (65 + rand(26)).chr }
word_array = Array.new(1000) { Array.new(5) { (65 + rand(26)).chr }.join }
Benchmark.ips do |x|
puts "Find one uniq element from: Number array"
x.report('Using group_by.select') do
find_one_using_group_by_select(num_array)
end
x.report('Using sort.chunk.select') do
find_one_using_chunk_select(num_array)
end
x.report('Using count select') do
find_one_using_count_select(num_array)
end
x.report('Using hash map') do
find_one_using_hash_map(num_array)
end
x.compare!
end
Benchmark.ips do |x|
puts "Find one uniq element from: Character array"
x.report('Using group_by.select') do
find_one_using_group_by_select(char_array)
end
x.report('Using sort.chunk.select') do
find_one_using_chunk_select(char_array)
end
x.report('Using count select') do
find_one_using_count_select(char_array)
end
x.report('Using hash map') do
find_one_using_hash_map(char_array)
end
x.compare!
end
Benchmark.ips do |x|
puts "Find one uniq element from: Word array"
x.report('Using group_by.select') do
find_one_using_group_by_select(word_array)
end
x.report('Using sort.chunk.select') do
find_one_using_chunk_select(word_array)
end
x.report('Using count select') do
find_one_using_count_select(word_array)
end
x.report('Using hash map') do
find_one_using_hash_map(word_array)
end
x.compare!
end
Benchmark.ips do |x|
puts "Find all uniq elements from: Number array"
x.report('Using group_by.select') do
find_all_using_group_by_select(num_array)
end
x.report('Using sort.chunk.select') do
find_all_using_chunk_select(num_array)
end
x.report('Using count select') do
find_all_using_count_select(num_array)
end
x.report('Using hash map') do
find_all_using_hash_map(num_array)
end
x.compare!
end
Benchmark.ips do |x|
puts "Find all uniq elements from: Character array"
x.report('Using group_by.select') do
find_all_using_group_by_select(char_array)
end
x.report('Using sort.chunk.select') do
find_all_using_chunk_select(char_array)
end
x.report('Using count select') do
find_all_using_count_select(char_array)
end
x.report('Using hash map') do
find_all_using_hash_map(char_array)
end
x.compare!
end
Benchmark.ips do |x|
puts "Find all uniq elements from: Word array"
x.report('Using group_by.select') do
find_all_using_group_by_select(word_array)
end
x.report('Using sort.chunk.select') do
find_all_using_chunk_select(word_array)
end
x.report('Using count select') do
find_all_using_count_select(word_array)
end
x.report('Using hash map') do
find_all_using_hash_map(word_array)
end
x.compare!
end
@naveed-ahmad
Copy link
Author

naveed-ahmad commented Jan 11, 2019

Find one uniq element from: Number array

Warming up --------------------------------------
Using group_by.select
                       646.000  i/100ms
Using sort.chunk.select
                       970.000  i/100ms
  Using count select    14.488k i/100ms
      Using hash map     6.470k i/100ms
Calculating -------------------------------------
Using group_by.select
                          6.353k (± 7.8%) i/s -     31.654k in   5.017299s
Using sort.chunk.select
                         10.024k (± 5.6%) i/s -     50.440k in   5.049812s
  Using count select    146.607k (± 3.4%) i/s -    738.888k in   5.045736s
      Using hash map     69.544k (± 3.4%) i/s -    349.380k in   5.029652s

Comparison:
  Using count select:   146607.2 i/s
      Using hash map:    69544.1 i/s - 2.11x  slower
Using sort.chunk.select:    10023.5 i/s - 14.63x  slower
Using group_by.select:     6352.7 i/s - 23.08x  slower

Find one uniq element from: Character array

Warming up --------------------------------------
Using group_by.select
                        15.753k i/100ms
Using sort.chunk.select
                        13.161k i/100ms
  Using count select    70.992k i/100ms
      Using hash map    38.183k i/100ms
Calculating -------------------------------------
Using group_by.select
                        162.135k (± 4.9%) i/s -    819.156k in   5.065392s
Using sort.chunk.select
                        135.456k (± 4.2%) i/s -    684.372k in   5.061872s
  Using count select    855.683k (± 3.4%) i/s -      4.331M in   5.066818s
      Using hash map    394.814k (± 4.0%) i/s -      1.986M in   5.037327s

Comparison:
  Using count select:   855683.3 i/s
      Using hash map:   394814.2 i/s - 2.17x  slower
Using group_by.select:   162135.0 i/s - 5.28x  slower
Using sort.chunk.select:   135456.1 i/s - 6.32x  slower

Find one uniq element from: Word array

Warming up --------------------------------------
Using group_by.select
                       229.000  i/100ms
Using sort.chunk.select
                       178.000  i/100ms
  Using count select     5.000  i/100ms
      Using hash map   293.000  i/100ms
Calculating -------------------------------------
Using group_by.select
                          2.280k (± 2.3%) i/s -     11.450k in   5.024328s
Using sort.chunk.select
                          1.741k (± 3.8%) i/s -      8.722k in   5.018150s
  Using count select     51.486  (± 5.8%) i/s -    260.000  in   5.071485s
      Using hash map      2.820k (± 1.9%) i/s -     14.357k in   5.093590s

Comparison:
      Using hash map:     2819.7 i/s
Using group_by.select:     2280.1 i/s - 1.24x  slower
Using sort.chunk.select:     1740.8 i/s - 1.62x  slower
  Using count select:       51.5 i/s - 54.77x  slower

Find all uniq elements from: Number array

Warming up --------------------------------------
Using group_by.select
                       428.000  i/100ms
Using sort.chunk.select
                       270.000  i/100ms
  Using count select    15.000  i/100ms
      Using hash map   574.000  i/100ms
Calculating -------------------------------------
Using group_by.select
                          4.359k (± 2.9%) i/s -     21.828k in   5.011856s
Using sort.chunk.select
                          2.757k (± 4.0%) i/s -     14.040k in   5.100278s
  Using count select    156.355  (± 2.6%) i/s -    795.000  in   5.087442s
      Using hash map      6.098k (± 4.9%) i/s -     30.422k in   5.002874s

Comparison:
      Using hash map:     6097.7 i/s
Using group_by.select:     4359.1 i/s - 1.40x  slower
Using sort.chunk.select:     2757.3 i/s - 2.21x  slower
  Using count select:      156.4 i/s - 39.00x  slower

Find all uniq elements from: Character array

Warming up --------------------------------------
Using group_by.select
                        11.234k i/100ms
Using sort.chunk.select
                         7.522k i/100ms
  Using count select     9.105k i/100ms
      Using hash map    13.601k i/100ms
Calculating -------------------------------------
Using group_by.select
                        117.704k (± 3.2%) i/s -    595.402k in   5.063823s
Using sort.chunk.select
                         78.129k (± 4.1%) i/s -    391.144k in   5.015242s
  Using count select     97.855k (± 2.3%) i/s -    491.670k in   5.027306s
      Using hash map    143.837k (± 3.3%) i/s -    720.853k in   5.017199s

Comparison:
      Using hash map:   143837.4 i/s
Using group_by.select:   117704.1 i/s - 1.22x  slower
  Using count select:    97854.8 i/s - 1.47x  slower
Using sort.chunk.select:    78129.4 i/s - 1.84x  slower

Find all uniq elements from: Word array

Warming up --------------------------------------
Using group_by.select
                       265.000  i/100ms
Using sort.chunk.select
                       177.000  i/100ms
  Using count select     5.000  i/100ms
      Using hash map   278.000  i/100ms
Calculating -------------------------------------
Using group_by.select
                          2.593k (± 2.5%) i/s -     12.985k in   5.011357s
Using sort.chunk.select
                          1.766k (± 3.3%) i/s -      8.850k in   5.017083s
  Using count select     52.252  (± 3.8%) i/s -    265.000  in   5.076584s
      Using hash map      2.724k (± 6.8%) i/s -     13.622k in   5.026633s

Comparison:
      Using hash map:     2724.4 i/s
Using group_by.select:     2592.7 i/s - same-ish: difference falls within error
Using sort.chunk.select:     1765.9 i/s - 1.54x  slower
  Using count select:       52.3 i/s - 52.14x  slower

@naveed-ahmad
Copy link
Author

naveed-ahmad commented Jan 11, 2019

array.detect {|e| array.rindex(e) != array.index(e) }

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment