Array einen beliebigen Wert aus einem anderen Array enthalten?

155

Was ist der effizienteste Weg, um zu testen, ob ein Array ein Element aus einem zweiten Array enthält?

Zwei Beispiele unten, die versuchen, die Frage zu beantworten, foodsenthalten ein Element aus 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
quelle

Antworten:

268 
(cheeses & foods).empty?

Wie Marc-André Lafortune in Kommentaren sagte, &arbeitet in linearer Zeit, während any?+ include?quadratisch sein wird. Bei größeren Datenmengen ist die lineare Zeit schneller. Bei kleinen Datenmengen kann any?+ include?schneller sein, wie aus der Antwort von Lee Jarvis hervorgeht - wahrscheinlich, weil &ein neues Array zugewiesen wird, während eine andere Lösung dies nicht tut und als einfache verschachtelte Schleife arbeitet, um einen Booleschen Wert zurückzugeben.

Nakilon
quelle
3
Wäre es nicht sinnvoller, zu prüfen, ob ein Array ein Element aus einem anderen Array enthält (Käse und Lebensmittel). da dies einen wahren Wert zurückgibt, wenn die Arrays tatsächlich eines der gleichen Elemente enthalten?
Ryan Francis
1
@RyanFrancis, docs: any?: Die Methode liefert true , wenn der Block jemals einen anderen Wert als false oder nil zurückgibt. empty?: Gibt true zurück, wenn self keine Elemente enthält.
Nakilon
3
@Nakilon Ich bin auch verwirrt, warum die Antwort (cheeses & foods).any?nicht die Frage des OP ist: Sind Lebensmittel in Käse? In seinem Beispiel ist "Feta" in beiden enthalten, also sollte das Ergebnis wahr sein, oder? Warum also .empty?an der Kreuzung nachsehen?
SuckerForMayhem
@SuckerForMayhem, weil OPs Frage "Wenn welche sind ... ?" Lautet, nicht nur "Wenn welche?". Wenn " are ... " weggelassen wird, wird angenommen, dass es "If any is True? " Ist, und es würde "False" für "array like" zurückgeben [false, false, false], obwohl es offensichtlich nicht leer ist.
Nakilon
Gibt es eine Implementierung in Activerecord-Ebene?
Lee Chun Hoe
35

Wie wäre es mit 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

Benchmark-Skript:

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

Ergebnis:

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
quelle
Sie können dies verbessern, indem Sie sich cheesesin ein Set verwandeln .
Akuhn
1
Ich habe hier meinen eigenen Benchmark für Ruby 2.2.7 und 2.3.4 ausgeführt und any?, include?war der Schnellste, disjunkt am langsamsten: gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497
Jared
4
Dieser Benchmark ist durch das erwähnte spezifische Beispiel verzerrt und gilt nicht unbedingt für einen allgemeineren Fall. Was wäre, wenn es keine gemeinsamen Elemente zwischen den beiden Arrays gäbe? Was wäre, wenn die Arrays bei jedem Durchgang in einer anderen Reihenfolge wären? Was ist, wenn Feta am Ende beider Arrays erscheint? Wie Marc-André feststellte, wird die festgelegte Schnittmenge in linearer Zeit ausgeführt. Daher ist es sinnvoll, dass sie für den allgemeinen Fall viel skalierbarer ist als das eine spezifische Beispiel, das lediglich zur Klärung der Frage verwendet wird.
user2259664
22

Sie können überprüfen, ob die Kreuzung leer ist.

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
quelle
1 
Set.new(cheeses).disjoint? Set.new(foods)
Davidkowski
quelle
Auch in meinem (unwissenschaftlichen) Benchmark war die disjunkte Einstellung signifikant langsamer als bei anderen Methoden: gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497
Jared
1
Danke für deine Kommentare. Ich bin mir nicht sicher, warum es nicht Set.new war, aber ich habe es gerade bearbeitet. Ich habe Ihre Leistungsbenchmarks in 2.4.1 ausprobiert. Meins hat es besser gemacht, aber immer noch nicht am besten mit disjunkten Sets, die mehr Wörter enthalten. Ich habe meine Version in einen Kommentar zu Ihrem Kern eingefügt. Ich finde disjoint?es auch sehr elegant, besonders im Vergleich zu "any?, Include?". Die ursprüngliche Frage bezog sich sowohl auf elegant als auch auf effizient.
Davidkovsky
.to_setMethode kann hier nützlich seincheeses.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
quelle