Cómo verificar si existe un valor en una matriz en Ruby

Tengo un valor 'Dog'y una matriz ['Cat', 'Dog', 'Bird'].

¿Cómo verifico si existe en la matriz sin recorrerla? ¿Hay una manera simple de verificar si el valor existe, nada más?

Estas buscando include?:

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

Hay un in?método enActiveSupport (parte de Rails) desde v3.1, como lo señaló @campaterson. Entonces, dentro de Rails, o si puedes require 'active_support', puedes escribir:

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

OTOH, no hay in operador o #in?método en Ruby, a pesar de que se ha propuesto antes, en particular por Yusuke Endoh, un miembro de primer nivel de ruby-core.

Como se ha señalado por otros, el método inverso include?existe, para todo Enumerables incluyendo Array, Hash, Set, Range:

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

Tenga en cuenta que si tiene muchos valores en su matriz, todos se verificarán uno después del otro (es decir O(n)), mientras que la búsqueda de un hash será de tiempo constante (es decir O(1)). Entonces, si su matriz es constante, por ejemplo, es una buena idea usar un Set en su lugar. P.ej:

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

Una prueba rápida revela que llamar include?a un elemento 10 Setes aproximadamente 3.5 veces más rápido que llamarlo al equivalente Array(si no se encuentra el elemento).

Una nota final de cierre: tenga cuidado al usar include?en un Range, hay sutilezas, así que consulte el documento y compárelo con cover?...

Tratar

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

Uso Enumerable#include:

a = %w/Cat Dog Bird/

a.include? 'Dog'

O, si se realizan varias pruebas, ¹ puede deshacerse del ciclo (que incluso include?tiene) y pasar de O (n) a O (1) con:

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

Si desea verificar por un bloque, puede intentarlo any?o all?.

%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  

Ver Enumerable para más información.

Mi inspiración vino de " evaluar si la matriz tiene algún artículo en rubí "

Ruby tiene once métodos para encontrar elementos en una matriz.

El preferido es include?o, para acceso repetido, crear un Set y luego llamar include?o member?.

Aquí están todos ellos:

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

Todos devuelven un truevalor ish si el elemento está presente.

include?Es el método preferido. Utiliza un forbucle de lenguaje C internamente que se rompe cuando un elemento coincide con las rb_equal_opt/rb_equalfunciones internas . No puede ser mucho más eficiente a menos que cree un Conjunto para verificaciones de membresía repetidas.

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

  for (i=0; i<RARRAY_LEN(ary); i++) {
    e = RARRAY_AREF(ary, i);
    switch (rb_equal_opt(e, item)) {
      case Qundef:
        if (rb_equal(e, item)) return Qtrue;
        break;
      case Qtrue:
        return Qtrue;
    }
  }
  return Qfalse;
}

member?no se redefine en la Arrayclase y utiliza una implementación no optimizada del Enumerablemódulo que literalmente enumera a través de todos los elementos:

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;
}

Traducido al código Ruby, esto hace lo siguiente:

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

Ambos include?ymember? tienen complejidad O (n) tiempo desde que el tanto buscar la matriz para la primera aparición del valor esperado.

Podemos usar un Set para obtener el tiempo de acceso O (1) a costa de tener que crear primero una representación Hash de la matriz. Si verifica repetidamente la membresía en la misma matriz, esta inversión inicial puede pagar rápidamente. Setno está implementado en C pero como clase simple de Ruby, sigue siendo el tiempo de acceso O (1) del subyacente@hash hace que valga la pena.

Aquí está la implementación de la clase 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

Como puede ver, la clase Set solo crea una @hashinstancia interna , asigna todos los objetos truey luego verifica la membresía usandoHash#include? que se implementa con el tiempo de acceso O (1) en la clase Hash.

No discutiré los otros siete métodos, ya que todos son menos eficientes.

En realidad, hay incluso más métodos con complejidad O (n) más allá de los 11 enumerados anteriormente, pero decidí no enumerarlos ya que escanean toda la matriz en lugar de romper en la primera coincidencia.

No uses estos:

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

Varias respuestas sugieren Array#include?, pero hay una advertencia importante: mirar la fuente, incluso Array#include?realiza bucles:

rb_ary_includes(VALUE ary, VALUE item)
{
    long i;

    for (i=0; i<RARRAY_LEN(ary); i++) {
        if (rb_equal(RARRAY_AREF(ary, i), item)) {
            return Qtrue;
        }
    }
    return Qfalse;
}

La forma de probar la presencia de la palabra sin bucle es construyendo un trie para su matriz. Hay muchas implementaciones de trie por ahí (google "ruby trie"). Usaré rambling-trieen este ejemplo:

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 }

Y ahora estamos listos para probar la presencia de varias palabras en su matriz sin recorrerla, a O(log n)tiempo, con la misma simplicidad sintáctica que Array#include?, usando sublinear Trie#include?:

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

Si no desea realizar un bucle, no hay forma de hacerlo con matrices. Deberías usar un Set en su lugar.

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

Los conjuntos funcionan internamente como Hashes, por lo que Ruby no necesita recorrer la colección para encontrar elementos, ya que, como su nombre lo indica, genera hashes de las claves y crea un mapa de memoria para que cada hash apunte a un cierto punto en la memoria. El ejemplo anterior hecho con un Hash:

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

La desventaja es que las teclas Sets y Hash solo pueden incluir elementos únicos y si agrega muchos elementos, Ruby tendrá que volver a mostrar todo después de cierto número de elementos para construir un nuevo mapa que se adapte a un espacio de teclas más grande. Para más información sobre esto, te recomiendo que veas " MountainWest RubyConf 2014 - Big O in a Homemade Hash por Nathan Long ".

Aquí hay un punto de referencia:

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

Y los resultados:

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

Esta es otra forma de hacer esto: use el Array#index método.

Devuelve el índice de la primera aparición del elemento en la matriz.

Por ejemplo:

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

index() También puede tomar un bloque:

Por ejemplo:

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

Esto devuelve el índice de la primera palabra en la matriz que contiene la letra 'o'.

Hecho de la diversión,

Puede usar *para verificar la membresía de una matriz en caseexpresiones.

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

Note el pequeño * en la cláusula when, esto verifica la membresía en la matriz.

Se aplica todo el comportamiento mágico habitual del operador splat, por lo que, por ejemplo, si arrayno es realmente una matriz sino un solo elemento, coincidirá con ese elemento.

Hay múltiples formas de lograr esto. Algunos de ellos son los siguientes:

a = [1,2,3,4,5]

2.in? a  #=> true

8.in? a #=> false

a.member? 1 #=> true

a.member? 8 #=> false

Si necesita verificar múltiples veces para cualquier clave, convierta arra hash, y ahora ingrese O (1)

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

Rendimiento de Hash # has_key? versus Array # include?

Parámetro Hash # has_key? Array # include

Complejidad de tiempo Operación O (1) Operación O (n) 

Tipo de acceso Accede al hash [clave] si se itera a través de cada elemento
                        devuelve cualquier valor de la matriz hasta que
                        true se devuelve a encuentra el valor en Array
                        Hash # has_key? llamada
                        llamada    

Para el control de una sola vez, usar include?está bien

Esto le dirá no solo que existe, sino también cuántas veces aparece:

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

Por lo que vale, los documentos de Ruby son un recurso increíble para este tipo de preguntas.

También tomaría nota de la longitud de la matriz que está buscando. El include?método ejecutará una búsqueda lineal con complejidad O (n) que puede volverse bastante fea dependiendo del tamaño de la matriz.

Si está trabajando con una matriz grande (ordenada), consideraría escribir un algoritmo de búsqueda binaria que no debería ser demasiado difícil y tiene el peor caso de O (log n).

O si está utilizando Ruby 2.0, puede aprovecharlo bsearch.

Puedes probar:

Ejemplo: si Cat y Dog existen en la matriz:

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

En vez de:

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

Nota: member?y include?son lo mismo.

¡Esto puede hacer el trabajo en una línea!

Si no queremos usar include?esto también funciona:

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

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

¿Qué tal este camino?

['Cat', 'Dog', 'Bird'].index('Dog')

Si está tratando de hacer esto en una prueba de unidad MiniTest , puede usarla assert_includes. Ejemplo:

pets = ['Cat', 'Dog', 'Bird']
assert_includes(pets, 'Dog')      # -> passes
assert_includes(pets, 'Zebra')    # -> fails 

Hay otra forma de evitar esto.

Supongamos que la matriz es [ :edit, :update, :create, :show ], bueno, tal vez los siete pecados mortales / relajantes .

Y más juguete con la idea de extraer una acción válida de una cadena:

"my brother would like me to update his profile"

Entonces:

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

Si desea devolver el valor no solo verdadero o falso, use

array.find{|x| x == 'Dog'}

Esto devolverá 'Perro' si existe en la lista; de lo contrario, será nulo.

Aquí hay una forma más de hacer esto:

arr = ['Cat', 'Dog', 'Bird']
e = 'Dog'

present = arr.size != (arr - [e]).size

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

tiene muchas formas de encontrar un elemento en cualquier matriz, pero la forma más simple es 'in?' método.

example:
arr = [1,2,3,4]
number = 1
puts "yes #{number} is present in arr" if number.in? arr

si no desea usar include?, primero puede envolver el elemento en una matriz y luego verificar si el elemento envuelto es igual a la intersección de la matriz y el elemento envuelto. Esto devolverá un valor booleano basado en la igualdad.

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

Siempre me parece interesante ejecutar algunos puntos de referencia para ver la velocidad relativa de las diversas formas de hacer algo.

Encontrar un elemento de matriz al comienzo, en el medio o al final afectará cualquier búsqueda lineal, pero apenas afectará una búsqueda contra un Conjunto.

La conversión de una matriz en un conjunto causará un impacto en el tiempo de procesamiento, así que cree el conjunto desde una matriz una vez o comience con un conjunto desde el principio.

Aquí está el código de referencia:

# frozen_string_literal: true

require 'fruity'
require 'set'

ARRAY = (1..20_000).to_a
SET = ARRAY.to_set

DIVIDER = '-' * 20

def array_include?(elem)
  ARRAY.include?(elem)
end

def array_member?(elem)
  ARRAY.member?(elem)
end

def array_index(elem)
  ARRAY.index(elem) >= 0
end

def array_find_index(elem)
  ARRAY.find_index(elem) >= 0
end

def array_index_each(elem)
  ARRAY.index { |each| each == elem } >= 0
end

def array_find_index_each(elem)
  ARRAY.find_index { |each| each == elem } >= 0
end

def array_any_each(elem)
  ARRAY.any? { |each| each == elem }
end

def array_find_each(elem)
  ARRAY.find { |each| each == elem } != nil
end

def array_detect_each(elem)
  ARRAY.detect { |each| each == elem } != nil
end

def set_include?(elem)
  SET.include?(elem)
end

def set_member?(elem)
  SET.member?(elem)
end

puts format('Ruby v.%s', RUBY_VERSION)

{
  'First' => ARRAY.first,
  'Middle' => (ARRAY.size / 2).to_i,
  'Last' => ARRAY.last
}.each do |k, element|
  puts DIVIDER, k, DIVIDER

  compare do
    _array_include?        { array_include?(element)        }
    _array_member?         { array_member?(element)         }
    _array_index           { array_index(element)           }
    _array_find_index      { array_find_index(element)      }
    _array_index_each      { array_index_each(element)      }
    _array_find_index_each { array_find_index_each(element) }
    _array_any_each        { array_any_each(element)        }
    _array_find_each       { array_find_each(element)       }
    _array_detect_each     { array_detect_each(element)     }
  end
end

puts '', DIVIDER, 'Sets vs. Array.include?', DIVIDER
{
  'First' => ARRAY.first,
  'Middle' => (ARRAY.size / 2).to_i,
  'Last' => ARRAY.last
}.each do |k, element|
  puts DIVIDER, k, DIVIDER

  compare do
    _array_include? { array_include?(element) }
    _set_include?   { set_include?(element)   }
    _set_member?    { set_member?(element)    }
  end
end

Lo cual, cuando se ejecuta en mi computadora portátil Mac OS, da como resultado:

Ruby v.2.7.0
--------------------
First
--------------------
Running each test 65536 times. Test will take about 5 seconds.
_array_include? is similar to _array_index
_array_index is similar to _array_find_index
_array_find_index is faster than _array_any_each by 2x ± 1.0
_array_any_each is similar to _array_index_each
_array_index_each is similar to _array_find_index_each
_array_find_index_each is faster than _array_member? by 4x ± 1.0
_array_member? is faster than _array_detect_each by 2x ± 1.0
_array_detect_each is similar to _array_find_each
--------------------
Middle
--------------------
Running each test 32 times. Test will take about 2 seconds.
_array_include? is similar to _array_find_index
_array_find_index is similar to _array_index
_array_index is faster than _array_member? by 2x ± 0.1
_array_member? is faster than _array_index_each by 2x ± 0.1
_array_index_each is similar to _array_find_index_each
_array_find_index_each is similar to _array_any_each
_array_any_each is faster than _array_detect_each by 30.000000000000004% ± 10.0%
_array_detect_each is similar to _array_find_each
--------------------
Last
--------------------
Running each test 16 times. Test will take about 2 seconds.
_array_include? is faster than _array_find_index by 10.000000000000009% ± 10.0%
_array_find_index is similar to _array_index
_array_index is faster than _array_member? by 3x ± 0.1
_array_member? is faster than _array_find_index_each by 2x ± 0.1
_array_find_index_each is similar to _array_index_each
_array_index_each is similar to _array_any_each
_array_any_each is faster than _array_detect_each by 30.000000000000004% ± 10.0%
_array_detect_each is similar to _array_find_each

--------------------
Sets vs. Array.include?
--------------------
--------------------
First
--------------------
Running each test 65536 times. Test will take about 1 second.
_array_include? is similar to _set_include?
_set_include? is similar to _set_member?
--------------------
Middle
--------------------
Running each test 65536 times. Test will take about 2 minutes.
_set_member? is similar to _set_include?
_set_include? is faster than _array_include? by 1400x ± 1000.0
--------------------
Last
--------------------
Running each test 65536 times. Test will take about 4 minutes.
_set_member? is similar to _set_include?
_set_include? is faster than _array_include? by 3000x ± 1000.0

Básicamente, los resultados me dicen que use un Set para todo si voy a buscar la inclusión, a menos que pueda garantizar que el primer elemento sea el que quiero, lo cual no es muy probable. Hay algo de sobrecarga cuando se insertan elementos en un hash, pero los tiempos de búsqueda son mucho más rápidos que no creo que eso deba considerarse. Nuevamente, si necesita buscarlo, no use una matriz, use un conjunto. (O un hash)

Cuanto más pequeña sea la matriz, más rápido se ejecutarán los métodos de matriz, pero todavía no van a seguir el ritmo, aunque en matrices pequeñas la diferencia puede ser pequeña.

"Primero", "Medio" y "Última" reflejan el uso de first, size / 2y lastpara ARRAYel bienestar elemento buscado. Ese elemento se usará al buscar las variables ARRAYy SET.

Se realizaron cambios menores en los métodos que se comparaban > 0porque la prueba debería ser >= 0para indexpruebas de tipo.

Más información sobre Fruity y su metodología está disponible en su archivo README .