¿La matriz incluye algún valor de otra matriz?

155

¿Cuál es la forma más eficiente de probar si una matriz contiene algún elemento de una segunda matriz?

Dos ejemplos a continuación, que intentan responder la pregunta, foodscontienen algún elemento de 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 Paul Groves
fuente

Respuestas:

268 
(cheeses & foods).empty?

Como dijo Marc-André Lafortune en los comentarios, &funciona en tiempo lineal mientras que any?+ include?será cuadrático. Para conjuntos de datos más grandes, el tiempo lineal será más rápido. Para conjuntos de datos pequeños, any?+ include?puede ser más rápido como se muestra en la respuesta de Lee Jarvis, probablemente porque &asigna un nuevo Array mientras que otra solución no lo hace y funciona como un simple bucle anidado para devolver un valor booleano.

Nakilon
fuente
3
Al verificar si una matriz contiene un elemento de otra matriz, ¿no tendría más sentido hacer (quesos y alimentos)? como esto devuelve un valor verdadero si las matrices contienen de hecho los mismos elementos?
Ryan Francis
1
@RyanFrancis, documentos: any?: El método devuelve verdadero si el bloque siempre devuelve un valor que no sea falsa o nula. empty?: Devuelve verdadero si self no contiene elementos.
Nakilon
3
@Nakilon También estoy confundido, ¿por qué la respuesta no (cheeses & foods).any?es la pregunta del OP: si hay alimentos en los quesos? En su ejemplo, "feta" está en ambos, por lo que el resultado debería ser cierto, ¿verdad? Entonces, ¿por qué verificar .empty?en la intersección?
SuckerForMayhem
@SuckerForMayhem, porque la pregunta de OP es "¿Si alguno es ... ?", No solo "¿Si hay alguno?". Si se omite " are ... ", se supone que es "If any is True? " Y devolvería False para array [false, false, false], mientras que obviamente no está vacío.
Nakilon
¿Hay alguna implementación en el nivel de registro activo?
Lee Chun Hoe
35

¿Qué tal 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

Script de referencia:

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

Resultado:

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)
Lee Jarvis
fuente
Puede mejorar esto convirtiéndose cheesesen un conjunto.
akuhn
1
Ran mi propio punto de referencia aquí en ruby 2.2.7 y 2.3.4 y any?, include?fue el más rápido disjuntos, conjunto el más lento: gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497
Jared
44
Este punto de referencia está sesgado por el ejemplo específico mencionado y no necesariamente se cumple en un caso más general. ¿Qué pasaría si no hubiera elementos comunes entre las dos matrices? ¿Qué pasaría si las matrices estuvieran en un orden diferente en cada pasada? ¿Qué pasa si el queso feta apareció al final de ambas matrices? Como dijo Marc-André, la intersección de conjuntos se ejecuta en tiempo lineal, por lo que tiene sentido que sea mucho más escalable para el caso general, en lugar del único ejemplo específico utilizado únicamente para aclarar la pregunta.
user2259664
22

Puede verificar si la intersección está vacía.

cheeses = %w(chedder stilton brie mozzarella feta haloumi)
foods = %w(pizza feta foods bread biscuits yoghurt bacon)
foods & cheeses
=> ["feta"] 
(foods & cheeses).empty?
=> false
Simone Carletti
fuente
1 
Set.new(cheeses).disjoint? Set.new(foods)
davidkovsky
fuente
También en mi punto de referencia (no científico), establecer disjunción fue significativamente más lento que otros métodos: gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497
Jared
1
Gracias por tus comentarios. No estoy seguro de por qué no fue Set.new, pero acabo de editarlo. Probé sus puntos de referencia de rendimiento en 2.4.1. A la mía le fue mejor, pero aún no mejor usando conjuntos desarticulados que contienen más palabras. Puse mi versión en un comentario sobre tu esencia. También creo que disjoint?es muy elegante, especialmente en comparación con "any? Include?". La pregunta original preguntaba tanto sobre elegante como eficiente.
davidkovsky
.to_setEl método puede ser útil aquí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)
Ram on Rails-n-React
fuente