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?
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?
Estas buscando include?
:
>> ['Cat', 'Dog', 'Bird'].include? 'Dog'
=> true
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 Enumerable
s 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?
...
Tratar
['Cat', 'Dog', 'Bird'].include?('Dog')
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']
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
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
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 true
ish 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_equal
funciones. 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
...
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)
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'.
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
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.