Array include any value from another array?
RubyArraysRuby Problem Overview
What's the most efficient way to test if an array contains any element from a second array?
Two examples below, attempting to answer the question does foods
contain any element from cheeses
:
cheeses = %w(chedder stilton brie mozzarella feta haloumi reblochon)
foods = %w(pizza feta foods bread biscuits yoghurt bacon)
puts cheeses.collect{|c| foods.include?(c)}.include?(true)
puts (cheeses - foods).size < cheeses.size
Ruby Solutions
Solution 1 - Ruby
(cheeses & foods).empty?
As Marc-André Lafortune said in comments, &
works in linear time while any?
+ include?
will be quadratic. For larger sets of data, linear time will be faster. For small data sets, any?
+ include?
may be faster as shown by Lee Jarvis' answer -- probably because &
allocates a new Array while another solution does not and works as a simple nested loop to return a boolean.
Solution 2 - Ruby
How about Enumerable#any?
>> cheeses = %w(chedder stilton brie mozzarella feta haloumi)
=> ["chedder", "stilton", "brie", "mozzarella", "feta", "haloumi"]
>> foods = %w(pizza feta foods bread biscuits yoghurt bacon)
=> ["pizza", "feta", "foods", "bread", "biscuits", "yoghurt", "bacon"]
>> foods.any? {|food| cheeses.include?(food) }
=> true
Benchmark script:
require "benchmark"
N = 1_000_000
puts "ruby version: #{RUBY_VERSION}"
CHEESES = %w(chedder stilton brie mozzarella feta haloumi).freeze
FOODS = %w(pizza feta foods bread biscuits yoghurt bacon).freeze
Benchmark.bm(15) do |b|
b.report("&, empty?") { N.times { (FOODS & CHEESES).empty? } }
b.report("any?, include?") { N.times { FOODS.any? {|food| CHEESES.include?(food) } } }
end
Result:
ruby version: 2.1.9
user system total real
&, empty? 1.170000 0.000000 1.170000 ( 1.172507)
any?, include? 0.660000 0.000000 0.660000 ( 0.666015)
Solution 3 - Ruby
You can check if the intersection is empty.
cheeses = %w(chedder stilton brie mozzarella feta haloumi)
foods = %w(pizza feta foods bread biscuits yoghurt bacon)
foods & cheeses
=> ["feta"]
(foods & cheeses).empty?
=> false
Solution 4 - Ruby
require "benchmark"
N = 1_000_000
puts "ruby version: #{RUBY_VERSION}"
CHEESES = %w(chedder stilton brie mozzarella feta haloumi).freeze
FOODS = %w(pizza feta foods bread biscuits yoghurt bacon).freeze
Benchmark.bm(15) do |b|
b.report("&, empty?") { N.times { (FOODS & CHEESES).empty? } }
b.report("any?, include?") { N.times { FOODS.any? {|food| CHEESES.include?(food) } } }
b.report("disjoint?") { N.times { FOODS.to_set.disjoint? CHEESES.to_set }}
end
user system total real
&, empty? 0.751068 0.000571 0.751639 ( 0.752745)
any?, include? 0.408251 0.000133 0.408384 ( 0.408438)
disjoint? 11.616006 0.014806 11.630812 ( 11.637300)
Solution 5 - Ruby
Set.new(cheeses).disjoint? Set.new(foods)