Tablica zawiera jakąkolwiek wartość z innej tablicy?

155

Jaki jest najbardziej efektywny sposób sprawdzenia, czy tablica zawiera dowolny element z drugiej tablicy?

Dwa poniższe przykłady, próbując odpowiedzieć na pytanie, foodszawierają elementy z 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
źródło

Odpowiedzi:

268 
(cheeses & foods).empty?

Jak powiedział Marc-André Lafortune w komentarzach, &działa w czasie liniowym, podczas gdy any?+ include?będzie kwadratowe. W przypadku większych zestawów danych czas liniowy będzie szybszy. W przypadku małych zestawów danych any?+ include?może być szybsze, jak pokazano w odpowiedzi Lee Jarvisa - prawdopodobnie dlatego, że &przydziela nową tablicę, podczas gdy inne rozwiązanie nie działa i działa jak prosta zagnieżdżona pętla zwracająca wartość logiczną.

Nakilon
źródło
3
Podczas sprawdzania, czy tablica zawiera element z innej tablicy, czy nie miałoby to większego sensu (sery i żywność). ponieważ zwraca prawdziwą wartość, jeśli tablice faktycznie zawierają którykolwiek z tych samych elementów?
Ryan Francis,
1
@RyanFrancis, docs: any?: Metoda zwraca true, jeśli blok kiedykolwiek zwróci wartość inną niż false lub zero. empty?: Zwraca wartość true, jeśli self nie zawiera żadnych elementów.
Nakilon
3
@Nakilon Jestem również zdezorientowany, dlaczego odpowiedź nie (cheeses & foods).any?jest pytaniem OP: czy w serach są jakieś potrawy? W jego przykładzie „feta” występuje w obu, więc wynik powinien być prawdziwy, prawda? Po co więc sprawdzać .empty?na skrzyżowaniu?
SuckerForMayhem
@SuckerForMayhem, ponieważ pytanie OP brzmi „Jeśli jakieś są… ?”, A nie tylko „Jeśli w ogóle?”. Jeśli pominięto „ are ... ”, przyjmuje się, że jest to „Jeśli któryś z nich jest prawdziwy? ” I zwróci False dla tablicy typu [false, false, false], chociaż oczywiście nie jest pusta.
Nakilon
Czy jest jakaś implementacja na poziomie ActiveRecord?
Lee Chun Hoe
35

Co powiesz na 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

Skrypt testowy:

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

Wynik:

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
źródło
Możesz to poprawić, zamieniając cheesessię w zestaw.
akuhn
1
Przeprowadziłem tutaj mój własny benchmark na Ruby 2.2.7 i 2.3.4 i any?, include?byłem najszybszy, ustawiłem rozłączenie najwolniej: gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497
Jared
4
Ten punkt odniesienia jest obciążony przez konkretny wspomniany przykład i niekoniecznie obowiązuje w bardziej ogólnym przypadku. Co by było, gdyby nie było wspólnych elementów między dwiema tablicami? Co by było, gdyby tablice były w innej kolejności na każdym przebiegu? A co by było, gdyby feta pojawiła się na końcu obu tablic? Jak stwierdził Marc-André, punkt przecięcia zestawu jest wykonywany w czasie liniowym, więc ma sens, że jest on znacznie bardziej skalowalny dla przypadku ogólnego, niż jeden konkretny przykład używany wyłącznie do wyjaśnienia pytania.
user2259664
22

Możesz sprawdzić, czy skrzyżowanie jest puste.

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
źródło
1 
Set.new(cheeses).disjoint? Set.new(foods)
davidkovsky
źródło
Również w moim (nienaukowym) benchmarku zestaw rozłączny był znacznie wolniejszy niż inne metody: gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497
Jared
1
Dziękuję za uwagi. Nie jestem pewien, dlaczego to nie był Set.new, ale właśnie go zredagowałem. Wypróbowałem testy wydajności w 2.4.1. Mój radził sobie lepiej, ale nadal nie najlepiej, używając rozłącznych zestawów zawierających więcej słów. Umieściłem moją wersję w komentarzu do twojej istoty. Uważam też, że disjoint?jest bardzo eleganckie, zwłaszcza w porównaniu do „any ?, include?”. Oryginalne pytanie dotyczyło zarówno elegancji, jak i wydajności.
davidkovsky
.to_setmetoda może być przydatna tutajcheeses.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
źródło