Array include any value from another array?

Question

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

Nakilon · Accepted Answer · 2020-01-18 06:58:41Z

314

(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.

edited Jan 18, 2020 at 6:58

answered Oct 15, 2010 at 11:55

Nakilon

35.2k16 gold badges112 silver badges148 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Ryan Francis Over a year ago

When checking if an array contains an element from another array, wouldn't it make more sense to do (cheeses & foods).any? as this returns a true value if the arrays' do in fact contain any of the same elements?

Nakilon Over a year ago

@RyanFrancis, docs: any?: The method returns true if the block ever returns a value other than false or nil. empty?: Returns true if self contains no elements.

mswieboda Over a year ago

@Nakilon I'm also confused why answer isn't (cheeses & foods).any? isn't the OP's question: if any foods are in cheeses? In his example, "feta" is in both, so result should be true, right? So why check .empty? on the intersection?

Nakilon Over a year ago

@SuckerForMayhem, because OP's question is "If any are ...?", not just "If any?". If "are ..." is omitted it's assumed to be "If any is True?" and would return False for array like [false, false, false], while it obviously is not empty.

Lee Chun Hoe Over a year ago

Is there any implementation in activerecord level?

|

czerasz · Accepted Answer · 2016-09-26 12:32:04Z

47

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)

edited Sep 26, 2016 at 12:32

czerasz

14.4k10 gold badges56 silver badges63 bronze badges

answered Oct 15, 2010 at 11:53

Lee Jarvis

16.3k4 gold badges40 silver badges40 bronze badges

3 Comments

akuhn Over a year ago

You can improve this by turning cheeses into a set.

Jared Over a year ago

Ran my own benchmark here on ruby 2.2.7 and 2.3.4 and any?, include? was the fastest, set disjoint the slowest: gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497

user2259664 Over a year ago

This benchmark is biased by the specific example mentioned and does not necessarily hold in a more general case. What if there were no common elements between the two arrays? What if the arrays were in a different order on each pass? What if feta appeared at the end of both arrays? As Marc-André stated, set intersection executes in linear time, so it makes sense that it is much more scalable for the general case, rather than the one specific example used purely to clarify the question.

Simone Carletti · Accepted Answer · 2010-10-15 11:58:11Z

27

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

answered Oct 15, 2010 at 11:58

Simone Carletti

177k50 gold badges371 silver badges370 bronze badges

Comments

souslov · Accepted Answer · 2023-07-04 12:00:45Z

7

you can use intersect? since ruby 3.1

foods.intersect?(cheeses)

answered Jul 4, 2023 at 12:00

souslov

44.7k11 gold badges92 silver badges113 bronze badges

Comments

Ram on Rails · Accepted Answer · 2020-06-16 20:54:43Z

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)

davidkovsky · Accepted Answer · 2017-05-04 18:09:47Z

1

Set.new(cheeses).disjoint? Set.new(foods)

edited May 4, 2017 at 18:09

answered Sep 27, 2016 at 19:02

davidkovsky

1,1478 silver badges11 bronze badges

3 Comments

Jared Over a year ago

Also in my (unscientific) benchmark, set disjoint was significantly slower than other methods: gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497

davidkovsky Over a year ago

Thanks for your comments. I'm not sure why it wasn't Set.new but I just edited it. I tried your performance benchmarks in 2.4.1. Mine did better but still not best using disjointed sets containing more words. I put my version in a comment on your gist. I also think disjoint? is very elegant, especially compared to "any?, include?". The original question did ask about both elegant and efficient.

nikolayp Over a year ago

.to_set method can be useful here cheeses.to_set.disjoint?(foods.to_set)

Collectives™ on Stack Overflow

Array include any value from another array?

6 Answers 6

8 Comments

3 Comments

Comments

Comments

Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

8 Comments

3 Comments

Comments

Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related