Pregunta Compruebe si existe un valor en una matriz en Ruby


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

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


1106
2017-12-31 17:49


origen


Respuestas:


Estas buscando include?:

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

1659
2017-12-31 17:51



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

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

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

Como señalaron otros, el método inverso include? existe, para todos Enumerables incluido 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á un tiempo constante (es decir, O(1)) Entonces, si la matriz es constante, por ejemplo, es una buena idea usar una Conjunto en 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

UN examen rápido revela esa vocación include? en un 10 elemento Set es aproximadamente 3.5 veces más rápido que llamarlo en el equivalente Array (si el elemento no se encuentra).

Una nota final de cierre: tenga cuidado al usar include? en un Range, hay sutilezas, así que refiérase a El documento y comparar con cover?...


205
2018-05-15 12:50



Tratar

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

157
2017-12-31 17:52



Utilizar Enumerable#include:

a = %w/Cat Dog Bird/

a.include? 'Dog'

O bien, si se realizan varias pruebas,1 puedes deshacerte del bucle (que incluso include? tiene) y pasar de En) a O (1) con:

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


1. Espero que esto sea obvio, pero para evitar objeciones: sí, solo para algunas búsquedas, el Hash [] y las operaciones de transposición dominan el perfil y son cada una En) sí mismos.


44
2017-12-31 17:52



Si desea verificar por bloque, ¿podría probar alguno? o todo ?.

%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  

Los detalles están aquí: http://ruby-doc.org/core-1.9.3/Enumerable.html
Mi inspiración viene de aquí: https://stackoverflow.com/a/10342734/576497


41
2018-05-20 09:08



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 mediante la construcción de un trie para su matriz. Hay muchas implementaciones por ahí (google "ruby trie"). usaré rambling-trie en 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 pasar por encima, en 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

28
2018-06-10 16:23



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

El preferido es include?

O para acceso repetido, crear un conjunto y luego llamar include? o member?

Aquí están todos,

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 ellos devuelven un trueish value si el elemento está presente.

include? es el método preferido Utiliza un lenguaje C for lazo interno que se rompe cuando un elemento coincide con el interno rb_equal_opt/rb_equalfunciones. No puede ser mucho más eficiente a menos que crees 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 Array clase y utiliza una implementación no optimizada de la Enumerable módulo que enumera literalmente 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 de Ruby esto hace sobre el 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? y member? tener O(n) complejidad de tiempo ya que ambos buscan en la matriz la primera aparición del valor esperado.

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

Aquí está la implementación de la Set clase,

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 puedes ver Set clase solo crea un interno @hash ejemplo, mapea todos los objetos a true y luego verifica la membresía usando Hash#include? que se implementa con O(1) tiempo de acceso en el Hash clase.

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

En realidad, hay incluso más métodos con O(n) complejidad más allá de los 11 enumerados anteriormente, pero decidí no enumerarlos ya que escanear todo el conjunto en lugar de romper en el primer partido.

No los uses,

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

23
2017-12-25 23:40



Si no desea realizar un bucle, no hay forma de hacerlo con Arrays. 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

Establece el trabajo internamente como hashes, por lo que Ruby no necesita pasar por la colección para buscar elementos, ya que como su nombre lo indica, genera hashes de las teclas y crea un mapa de memoria para que cada punto señale 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 claves de conjuntos y hash solo pueden incluir elementos únicos y si agrega muchos elementos, Ruby tendrá que repetir todo después de cierto número de elementos para crear un nuevo mapa que se adapte a un espacio de teclado más grande. Para más información sobre esto, te recomiendo que mires MountainWest RubyConf 2014 - Big O en una Hash hecha en casa 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)

16
2018-05-29 19:58



Esta es otra forma de hacerlo: use el método de índice Array #.

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

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

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


15
2017-10-02 17:22



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

8
2018-04-29 10:12



Hecho de la diversión,

Puedes usar * para verificar la membresía de la matriz en una case expresiones.

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

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

Se aplica todo el comportamiento mágico habitual del operador splat, por ejemplo, si array no es en realidad una matriz, sino un elemento único que coincidirá con ese elemento.


6
2017-12-25 23:48