Array termasuk nilai dari array lain?

155

Apa cara paling efisien untuk menguji apakah array berisi elemen apa pun dari array kedua?

Dua contoh di bawah ini, mencoba menjawab pertanyaan memang foodsmengandung unsur apa pun dari 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
sumber

Jawaban:

268 
(cheeses & foods).empty?

Seperti yang dikatakan Marc-André Lafortune dalam komentar, &bekerja dalam waktu linier sementara any?+ include?akan kuadratik. Untuk kumpulan data yang lebih besar, waktu linier akan lebih cepat. Untuk set data kecil, any?+ include?mungkin lebih cepat seperti yang ditunjukkan oleh jawaban Lee Jarvis - mungkin karena &mengalokasikan Array baru sementara solusi lain tidak dan bekerja sebagai loop bersarang sederhana untuk mengembalikan boolean.

Nakilon
sumber
3
Saat memeriksa apakah array mengandung elemen dari array lain, bukankah lebih masuk akal untuk melakukannya (keju & ​​makanan) .any? karena ini mengembalikan nilai sebenarnya jika array 'sebenarnya mengandung elemen yang sama?
Ryan Francis
1
@RyanFrancis, docs: any?: Metode mengembalikan true jika blok pernah mengembalikan nilai selain palsu atau nihil. empty?: Mengembalikan nilai true jika self tidak mengandung elemen.
Nakilon
3
@Nakilon Saya juga bingung mengapa jawabannya bukan (cheeses & foods).any?pertanyaan OP: apakah ada makanan yang mengandung keju? Dalam contohnya, "feta" ada di keduanya, jadi hasilnya harus benar, kan? Jadi mengapa memeriksa .empty?persimpangan?
SuckerForMayhem
@SuckerForMayhem, karena pertanyaan OP adalah "Jika ada ... ?", Bukan hanya "Jika ada?". Jika " adalah ... " dihilangkan, itu dianggap "Jika ada Benar? " Dan akan mengembalikan False untuk array seperti [false, false, false], sementara itu jelas tidak kosong.
Nakilon
Apakah ada implementasi di level activerecord?
Lee Chun Hoe
35

Bagaimana dengan 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

Skrip benchmark:

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

Hasil:

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
sumber
Anda dapat meningkatkan ini dengan mengubah cheesesmenjadi satu set.
akuhn
1
Berlari benchmark saya sendiri di ruby ​​2.2.7 dan 2.3.4 dan any?, include?merupakan yang tercepat, atur paling lambat: gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497
Jared
4
Tolok ukur ini bias oleh contoh spesifik yang disebutkan dan tidak selalu berlaku dalam kasus yang lebih umum. Bagaimana jika tidak ada elemen umum di antara kedua array? Bagaimana jika array berada dalam urutan berbeda pada setiap pass? Bagaimana jika feta muncul di akhir kedua array? Seperti yang dikatakan Marc-André, mengatur persimpangan dijalankan dalam waktu linier, sehingga masuk akal bahwa itu jauh lebih skalabel untuk kasus umum, daripada satu contoh khusus yang digunakan murni untuk mengklarifikasi pertanyaan.
user2259664
22

Anda dapat memeriksa apakah persimpangan itu kosong.

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
sumber
1 
Set.new(cheeses).disjoint? Set.new(foods)
davidkovsky
sumber
Juga dalam tolok ukur (tidak ilmiah) saya, set disjoint secara signifikan lebih lambat daripada metode lain: gist.github.com/jaredmoody/d2a1e83de2f91fd6865920cd01a8b497
Jared
1
Terima kasih atas komentar anda Saya tidak yakin mengapa itu bukan Set.new tapi saya baru saja mengeditnya. Saya mencoba tolok ukur kinerja Anda di 2.4.1. Milik saya melakukan lebih baik tetapi masih tidak terbaik menggunakan set terputus-putus berisi lebih banyak kata. Saya memasukkan versi saya ke komentar pada intisari Anda. Saya juga berpikir disjoint?sangat elegan, terutama dibandingkan dengan "any ?, include?". Pertanyaan awal memang bertanya tentang elegan dan efisien.
davidkovsky
.to_setmetode dapat berguna di sinicheeses.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
sumber