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

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