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

121

¿Cuál es la mejor manera, la más elegante/eficiente para probar si una matriz contiene algún elemento de una segunda matriz?¿La matriz incluye algún valor de otra matriz?

Dos ejemplos a continuación, tratando de responder a la pregunta hace 'alimentos' contienen ningún elemento de los 'quesos':

cheeses = %w(chedder stilton brie mozzarella feta haloumi) 
foods = %w(pizza feta foods bread biscuits yoghurt bacon) 

puts cheeses.collect{|c| foods.include?(c)}.include?(true) 

puts (cheeses - foods).size < cheeses.size

Fuente

2010-10-15 Paul Groves

211

(cheeses & foods).empty?

~~Se hace lo mismo, que posted Injekt, pero ya está compilado acciones en un idioma.~~

Como dijo Marc-André Lafortune en los comentarios, & obras en tiempo lineal, mientras que any? + include? serán cuadrática. 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 lo muestra la respuesta de Lee Jarvis.

Fuente

2010-10-15 11:55:24 Nakilon

+12

Ruby hace la intersección construyendo un hash, por lo que definitivamente no es lo mismo que 'any? {... include?}' Que recorrerá cada posible par de elementos. La intersección '&' es, por tanto, tiempo lineal, mientras que 'any?' Será cuadrático. Sería equivalente si "quesos" fuera un "conjunto" en lugar de un "conjunto". –

Al verificar si una matriz contiene un elemento de otra matriz, ¿no tendría más sentido hacer (quesos y alimentos) .any? ya que esto devuelve un valor verdadero si las matrices de hecho contienen alguno de los mismos elementos? –

@RyanFrancis, documentos: 'any?': * El método devuelve verdadero si el bloque alguna vez devuelve un valor distinto de falso o nulo. * 'Empty?': * Devuelve verdadero si el auto no contiene elementos. * – Nakilon

¿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

guión 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)

Fuente

2010-10-15 11:53:52

Esta debe ser la respuesta correcta. Incluso el otro es más legible. Esta es una solución mucho más rápida –

Puede mejorar esto al convertir 'quesos' en un conjunto. – akuhn

Corrí mi propio punto de referencia aquí en ruby 2.2.7 y 2.3.4 y 'any ?, include?' Fue el más rápido, conjunto disjoint el más lento: https://gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497 – Jared

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

Fuente

2010-10-15 11:58:11

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

Fuente

2016-09-27 19:02:09 davidkovsky

Esto no se ve como la sintaxis 2.0 válida - 'Set.new (CHEESES) .disjoint? Set.new (FOODS) 'tal vez? – Jared

También en mi punto de referencia (no científico), establecer disjuntos fue significativamente más lento que otros métodos: https://gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497 – Jared

Gracias por sus comentarios. No estoy seguro de por qué no fue Set.new, pero acabo de editarlo. Probé tus puntos de referencia de rendimiento en 2.4.1. Lo hice mejor, pero aún no es el mejor uso de conjuntos inconexos 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 sí preguntó acerca de elegante y eficiente. – davidkovsky

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

Respuesta

Cuestiones relacionadas