Controlla se esiste un valore in una matrice in Ruby

Ho un valore 'Dog' e un array ['Cat', 'Dog', 'Bird'] .

Come posso verificare se esiste nell’array senza doverlo scorrere? C’è un modo semplice per verificare se il valore esiste, niente di più?

Stai cercando include? :

 >> ['Cat', 'Dog', 'Bird'].include? 'Dog' => true 

C’è un in? metodo in ActiveSupport (parte di Rails) dalla v3.1, come sottolineato da @campaterson. Quindi, all’interno di Rails, o se require 'active_support' , puoi scrivere:

 'Unicorn'.in?(['Cat', 'Dog', 'Bird']) # => false 

OTOH, non c’è operatore in o #in? metodo in Ruby stesso, anche se è stato proposto prima, in particolare da Yusuke Endoh un membro di prima qualità di ruby-core.

Come sottolineato da altri, il metodo inverso include? esiste, per tutti gli Enumerable s inclusi Array , Hash , Set , Range :

 ['Cat', 'Dog', 'Bird'].include?('Unicorn') # => false 

Si noti che se si hanno molti valori nell’array, verranno controllati uno dopo l’altro (cioè O(n) ), mentre quella ricerca per un hash sarà costante (es. O(1) ). Quindi, se la matrice è costante, ad esempio, è preferibile utilizzare un Set . Per esempio:

 require 'set' ALLOWED_METHODS = Set[:to_s, :to_i, :upcase, :downcase # etc ] def foo(what) raise "Not allowed" unless ALLOWED_METHODS.include?(what.to_sym) bar.send(what) end 

Un rapido test rivela che la chiamata include? su un 10 elemento Set è circa 3,5 volte più veloce rispetto a chiamarlo sulla Array equivalente (se l’elemento non viene trovato).

Una nota conclusiva: diffidare quando si utilizza include? su un Range , ci sono sottigliezze, quindi fare riferimento al documento e confrontare con la cover?

Provare

 ['Cat', 'Dog', 'Bird'].include?('Dog') 

Utilizza Enumerable#include :

 a = %w/Cat Dog Bird/ a.include? 'Dog' 

Oppure, se viene eseguito un numero di test, 1 puoi eliminare il loop (che include? anche has) e passare da O (n) a O (1) con:

 h = Hash[[a, a].transpose] h['Dog'] 

1. Spero che questo sia ovvio, ma a parte le obiezioni: sì, solo per alcune occhiate, le operazioni di Hash [] e trasposizione dominano il profilo e sono ciascuna di esse (n) .

Se vuoi controllare da un blocco, puoi provarne? o tutto ?.

 %w{ant bear cat}.any? {|word| word.length >= 3} #=> true %w{ant bear cat}.any? {|word| word.length >= 4} #=> true [ nil, true, 99 ].any? #=> true 

I dettagli sono qui: http://ruby-doc.org/core-1.9.3/Enumerable.html
La mia ispirazione viene da qui: https://stackoverflow.com/a/10342734/576497

Diverse risposte suggeriscono l’ Array#include? , ma c’è un avvertimento importante: guardando la fonte, anche l’ Array#include? esegue il looping:

 rb_ary_includes(VALUE ary, VALUE item) { long i; for (i=0; i 

Il modo per testare la presenza della parola senza il loop è costruendo un trie per il tuo array. Ci sono molte implementazioni trie là fuori (google "ruby trie"). rambling-trie in questo esempio:

 a = %w/cat dog bird/ require 'rambling-trie' # if necessary, gem install rambling-trie trie = Rambling::Trie.create { |trie| a.each do |e| trie << e end } 

E ora siamo pronti a testare la presenza di varie parole nell'array senza ricorrere al loop, in O(log n) time, con la stessa semplicità sintattica di Array#include? , usando l' Trie#include? sublineare Trie#include? :

 trie.include? 'bird' #=> true trie.include? 'duck' #=> false 

Ruby ha 11 metodi per trovare elementi in un array.

Quello preferito è include?

O per l’accesso ripetuto, creando un set e quindi chiamando include? o member?

Ecco tutti loro,

 array.include?(element) # preferred method array.member?(element) array.to_set.include?(element) array.to_set.member?(element) array.index(element) > 0 array.find_index(element) > 0 array.index { |each| each == element } > 0 array.find_index { |each| each == element } > 0 array.any? { |each| each == element } array.find { |each| each == element } != nil array.detect { |each| each == element } != nil 

Tutti restituiscono un true valore ish se l’elemento è presente.

include? è il metodo preferito Utilizza internamente un linguaggio C for ciclo che si interrompe quando un elemento corrisponde alle rb_equal_opt/rb_equal interne rb_equal_opt/rb_equal . Non può diventare molto più efficiente a meno che non si crei un set per i controlli di appartenenza ripetuti.

 VALUE rb_ary_includes(VALUE ary, VALUE item) { long i; VALUE e; for (i=0; i 

member? non viene ridefinito nella class Array e utilizza un'implementazione non ottimizzata dal modulo Enumerable che enumera letteralmente attraverso tutti gli elementi.

 static VALUE member_i(RB_BLOCK_CALL_FUNC_ARGLIST(iter, args)) { struct MEMO *memo = MEMO_CAST(args); if (rb_equal(rb_enum_values_pack(argc, argv), memo->v1)) { MEMO_V2_SET(memo, Qtrue); rb_iter_break(); } return Qnil; } static VALUE enum_member(VALUE obj, VALUE val) { struct MEMO *memo = MEMO_NEW(val, Qfalse, 0); rb_block_call(obj, id_each, 0, 0, member_i, (VALUE)memo); return memo->v2; } 

Tradotto in codice Ruby questo fa quanto segue

 def member?(value) memo = [value, false, 0] each_with_object(memo) do |each, memo| if each == memo[0] memo[1] = true break end memo[1] end 

Entrambi include? e member? ha O(n) complessità temporale poiché entrambi cercano nell'array la prima occorrenza del valore atteso.

Possiamo usare un set per ottenere il tempo di accesso O(1) al costo di dover prima creare una rappresentazione hash dell'array. Se si controlla ripetutamente l'appartenenza allo stesso array, questo investimento iniziale può ripagare rapidamente. Set non è implementato in C ma come semplice class Ruby, tuttavia il tempo di accesso O(1) del sottostante @hash rende utile.

Ecco l'implementazione della class Set ,

 module Enumerable def to_set(klass = Set, *args, &block) klass.new(self, *args, &block) end end class Set def initialize(enum = nil, &block) # :yields: o @hash ||= Hash.new enum.nil? and return if block do_with_enum(enum) { |o| add(block[o]) } else merge(enum) end end def merge(enum) if enum.instance_of?(self.class) @hash.update(enum.instance_variable_get(:@hash)) else do_with_enum(enum) { |o| add(o) } end self end def add(o) @hash[o] = true self end def include?(o) @hash.include?(o) end alias member? include? ... end 

Come puoi vedere, la class Set crea solo un'istanza @hash interna, @hash mapping di tutti gli oggetti su true e quindi controlla l'appartenenza usando Hash#include? che è implementato con O(1) tempo di accesso nella class Hash .

Non discuterò gli altri 7 metodi perché sono tutti meno efficienti.

Esistono ancora più metodi con la complessità O(n) oltre gli 11 elencati sopra, ma ho deciso di non elencarli poiché esegui la scansione dell'intero array piuttosto che rompere alla prima corrispondenza.

Non usare questi,

 # bad examples array.grep(element).any? array.select { |each| each == element }.size > 0 ... 

Se non vuoi eseguire il ciclo, non c’è modo di farlo con gli array. Dovresti usare invece un Set.

 require 'set' s = Set.new 100.times{|i| s << "foo#{i}"} s.include?("foo99") => true [1,2,3,4,5,6,7,8].to_set.include?(4) => true 

Imposta il lavoro internamente come hash, quindi Ruby non ha bisogno di scorrere la collezione per trovare gli oggetti, poiché come suggerisce il nome, genera degli hash delle chiavi e crea una mappa di memoria in modo che ogni hash punti a un certo punto nella memoria. L’esempio precedente fatto con un hash:

 fake_array = {} 100.times{|i| fake_array["foo#{i}"] = 1} fake_array.has_key?("foo99") => true 

Lo svantaggio è che i set e le chiavi hash possono includere solo oggetti unici e se aggiungete molti oggetti, Ruby dovrà ripetere l’intera operazione dopo un certo numero di elementi per build una nuova mappa che si adatta a uno spazio chiavi più grande. Per ulteriori informazioni su questo, ti consiglio di guardare MountainWest RubyConf 2014 – Big O in un hash fatto in casa di Nathan Long

Ecco un punto di riferimento:

 require 'benchmark' require 'set' array = [] set = Set.new 10_000.times do |i| array << "foo#{i}" set << "foo#{i}" end Benchmark.bm do |x| x.report("array") { 10_000.times { array.include?("foo9999") } } x.report("set ") { 10_000.times { set.include?("foo9999") } } end 

E i risultati:

  user system total real array 7.020000 0.000000 7.020000 ( 7.031525) set 0.010000 0.000000 0.010000 ( 0.004816) 

Questo è un altro modo per farlo: usa il metodo dell’indice # di Array.

Restituisce l’indice della prima occorrenza dell’elemento nell’array.

esempio:

 a = ['cat','dog','horse'] if a.index('dog') puts "dog exists in the array" end 

index () può anche prendere un blocco

per esempio

 a = ['cat','dog','horse'] puts a.index {|x| x.match /o/} 

qui, restituire l’indice della prima parola nell’array che contiene la lettera ‘o’.

Ci sono molti modi per farlo. Alcuni di loro sono i seguenti:

 a = [1,2,3,4,5] 2.in? a #=> true 8.in? a #=> false a.member? 1 #=> true a.member? 8 #=> false 

Fatto divertente,

È ansible utilizzare * per verificare l’appartenenza dell’array in un’espressione di case .

 case element when *array ... else ... end 

Si noti la piccola * nella clausola when, questo controlla l’appartenenza alla matrice.

Tutto il solito comportamento magico dell’operatore splat si applica, quindi per esempio se l’ array non è in realtà un array ma un singolo elemento lo abbinerà.

Questo ti dirà non solo che esiste ma anche quante volte appare:

  a = ['Cat', 'Dog', 'Bird'] a.count("Dog") #=> 1 

Per quello che vale, i documenti di Ruby sono una risorsa straordinaria per questo tipo di domande.

Vorrei anche prendere nota della lunghezza della matrice che stai cercando. L’ include? il metodo eseguirà una ricerca lineare con complessità O (n) che può diventare piuttosto brutta a seconda delle dimensioni dell’array.

Se stai lavorando con una matrice di grandi dimensioni (ordinata), prenderei in considerazione la scrittura di un algoritmo di ricerca binaria che non dovrebbe essere troppo difficile e ha il peggior caso di O (log n).

Oppure se stai usando Ruby 2.0, puoi approfittare di bsearch .

Se hai in mente più valori … puoi provare:

Esempio: se Gatto e Cane esistono nell’array:

 (['Cat','Dog','Bird'] & ['Cat','Dog'] ).size == 2 #or replace 2 with ['Cat','Dog].size 

Invece di:

 ['Cat','Dog','Bird'].member?('Cat') and ['Cat','Dog','Bird'].include?('Dog') 

Nota: membro? e includere? sono uguali

Questo può fare il lavoro in una sola riga!

C’è anche il contrario!

Supponiamo che la matrice sia [: modifica,: aggiorna,: crea,: mostra] – beh forse gli interi sette peccati mortali / riposanti 🙂

E poi giocare con l’idea di tirare una valida azione da qualche stringa – per dire

mio fratello vorrebbe che aggiorni il suo profilo

Soluzione

 [ :edit, :update, :create, :show ].select{|v| v if "my brother would like me to update his profile".downcase =~ /[,|.| |]#{v.to_s}[,|.| |]/} 

Se non vogliamo usare include? questo funziona anche:

 ['cat','dog','horse'].select{ |x| x == 'dog' }.any? 

Converti arr in hash , ora controlla O (1) tempi multipli per qualsiasi chiave: hash = arr.map {|x| [x,true]}.to_h hash = arr.map {|x| [x,true]}.to_h

 arr = ['Cat', 'Dog', 'Bird'] hash = arr.map {|x| [x,true]}.to_h => {"Cat"=>true, "Dog"=>true, "Bird"=>true} hash["Dog"] => true hash["Insect"] => false 

Prestazioni di hash # has_key? contro l’ array # include?

 Parametro hash # has_key?  Array # includono 

 Complessità temporale O (1) operazione operazione O (n) 

 Tipo di accesso Accede Hash [chiave] se scorre attraverso ogni elemento
                         restituisce qualsiasi valore quindi dell'array fino a quel momento
                         true viene restituito al trova il valore in Array
                         Hash # has_key?  chiamata
                         chiamata    

Che ne dici di questo modo?

 ['Cat', 'Dog', 'Bird'].index('Dog') 
 ['Cat', 'Dog', 'Bird'].detect { |x| x == 'Dog'} => "Dog" !['Cat', 'Dog', 'Bird'].detect { |x| x == 'Dog'}.nil? => true 

Prova ad usare include? per un array. Ad esempio, se l’istruzione restituisce true, allora quel valore esiste in array altrimenti no.

 array = [ 'Cat', 'Dog', 'Bird' ] array.include?("Dog") 

se non vuoi usare include? è ansible prima avvolgere l’elemento in una matrice e quindi verificare se l’elemento avvolto è uguale all’intersezione della matrice e dell’elemento avvolto. Ciò restituirà un valore booleano basato sull’eguaglianza.

 def in_array?(array, item) item = [item] unless item.is_a?(Array) item == array & item end 

Ecco un altro modo per farlo:

 arr = ['Cat', 'Dog', 'Bird'] e = 'Dog' present = arr.size != (arr - [e]).size 
 array = [ 'Cat', 'Dog', 'Bird' ] array.include?("Dog") 

Puoi trovare nel tuo array:

['Cat', 'Dog', 'Bird'].include?('Dog')

o

['Cat', 'Dog', 'Bird'].include? 'Dog'