Массив включить любое значение из другого массива?

155

Какой самый эффективный способ проверить, содержит ли массив какой-либо элемент из второго массива?

Два примера ниже, попытка ответить на вопрос, foodsсодержит какой-либо элемент из 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 arrays Пол Гровс
источник

Ответы:

268 
(cheeses & foods).empty?

Как сказал в комментариях Марк-Андре Лафортун, &работает в линейном времени, пока any?+ include?будет квадратичным. Для больших наборов данных линейное время будет быстрее. Для небольших наборов данных any?+ include?может быть быстрее, как показано в ответе Ли Джарвиса - возможно, потому что &выделяет новый массив, в то время как другое решение этого не делает, и работает как простой вложенный цикл для возврата логического значения.

Nakilon
источник
3
При проверке, содержит ли массив элемент из другого массива, не имеет ли смысла делать это (сыры и продукты). как это возвращает истинное значение, если массивы действительно содержат какие-либо из тех же элементов?
Райан Фрэнсис
1
@RyanFrancis, документы: any?: Метод возвращает истину , если блок всегда возвращает значение , отличное от ложных или ноль. empty?: Возвращает истину , если сам не содержат элементов.
Накилон
3
@Nakilon Я также смущен, почему ответ не (cheeses & foods).any?является вопросом OP: есть ли продукты в сырах? В его примере «фета» есть в обоих, поэтому результат должен быть правдой, верно? Так зачем проверять .empty?перекресток?
SuckerForMayhem
@SuckerForMayhem, потому что вопрос OP - «Если есть ... ?», А не просто «Если есть?». Если значение « are ... » опущено, предполагается, что оно равно «If any is True? » И будет возвращать False для массива наподобие [false, false, false], хотя оно, очевидно, не пустое.
Накилон
Есть ли реализация на уровне activerecord?
Ли Чун Хо
35

Как насчет 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

Контрольный скрипт:

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

Результат:

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)
Ли Джарвис
источник
Вы можете улучшить это, превратившись cheesesв набор.
Akuhn
1
Здесь я выполнил свой собственный тест на ruby ​​2.2.7 и 2.3.4 и any?, include?был самым быстрым, а набор - самым медленным: gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497
Джаред
4
Этот критерий смещен на упомянутый конкретный пример и не обязательно имеет место в более общем случае. Что если бы не было общих элементов между двумя массивами? Что, если массивы были в другом порядке на каждом проходе? Что если фета появилась в конце обоих массивов? Как заявил Марк-Андре, множество пересечений выполняется за линейное время, поэтому имеет смысл, что оно гораздо более масштабируемо для общего случая, чем один конкретный пример, используемый исключительно для пояснения вопроса.
user2259664
22

Вы можете проверить, является ли пересечение пустым.

cheeses = %w(chedder stilton brie mozzarella feta haloumi)
foods = %w(pizza feta foods bread biscuits yoghurt bacon)
foods & cheeses
=> ["feta"] 
(foods & cheeses).empty?
=> false
Симона Карлетти
источник
1 
Set.new(cheeses).disjoint? Set.new(foods)
davidkovsky
источник
Кроме того, в моем (ненаучном) тесте набор дизъюнктов был значительно медленнее, чем другие методы: gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497
Джаред
1
Спасибо за ваши комментарии. Я не уверен, почему это не был Set.new, но я только отредактировал это. Я попробовал ваши показатели производительности в 2.4.1. Мой сделал лучше, но все еще не лучше, используя несвязные наборы, содержащие больше слов. Я поставил свою версию в комментарии к вашей сути. Я также думаю, что disjoint?это очень элегантно, особенно по сравнению с «любой? Оригинальный вопрос задавался как об элегантности, так и эффективности.
Давидковский
.to_setМетод может быть полезен здесьcheeses.to_set.disjoint?(foods.to_set)
itsnikolay
0 
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)
Таран на Rails-n-React
источник