Comment vérifier si une valeur existe dans un tableau dans Ruby

J'ai une valeur 'Dog'et un tableau ['Cat', 'Dog', 'Bird'].

Comment puis-je vérifier s'il existe dans le tableau sans le parcourir? Existe-t-il un moyen simple de vérifier si la valeur existe, rien de plus?

Vous recherchez include?:

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

Il existe une in?méthode dans ActiveSupport(partie de Rails) depuis la v3.1, comme l'a souligné @campaterson. Donc dans Rails, ou si vous require 'active_support', vous pouvez écrire:

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

OTOH, il n'y a aucun inopérateur ou #in?méthode dans Ruby lui-même, même s'il a été proposé auparavant, en particulier par Yusuke Endoh, un membre de premier ordre de ruby-core.

Comme l' a souligné par d' autres, la méthode inverse include?existe, pour tous Enumerables , y compris Array, Hash, Set, Range:

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

Notez que si vous avez plusieurs valeurs dans votre tableau, elles seront toutes vérifiées l'une après l'autre (ie O(n)), tandis que la recherche d'un hachage sera à temps constant (ie O(1)). Ainsi, si votre tableau est constant, par exemple, c'est une bonne idée d'utiliser un ensemble à la place. Par exemple:

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 test rapide révèle que l'appel include?à un élément 10 Setest environ 3,5 fois plus rapide que l'appel à l'équivalent Array(si l'élément n'est pas trouvé).

Une dernière note de clôture: méfiez-vous lors de l'utilisation include?sur un Range, il y a des subtilités, alors référez-vous au doc et comparez avec cover?...

Essayer

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

Utilisation Enumerable#include:

a = %w/Cat Dog Bird/

a.include? 'Dog'

Ou, si un certain nombre de tests sont effectués, ¹ vous pouvez vous débarrasser de la boucle (qui a même include?) et passer de O (n) à O (1) avec:

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

Si vous souhaitez vérifier par un bloc, vous pouvez essayer any?ou 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  

Voir Enumerable pour plus d'informations.

Mon inspiration est venue de " évaluer si le tableau contient des éléments en rubis "

Ruby a onze méthodes pour rechercher des éléments dans un tableau.

La préférence est include?ou, pour les accès répétés, créez un ensemble, puis appelez include?ou member?.

Voici tous:

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

Ils renvoient tous une truevaleur ish si l'élément est présent.

include?est la méthode préférée. Il utilise une forboucle de langage C en interne qui se casse lorsqu'un élément correspond aux rb_equal_opt/rb_equalfonctions internes . Il ne peut être beaucoup plus efficace que si vous créez un ensemble pour les vérifications d'appartenance répétées.

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?n'est pas redéfini dans la Arrayclasse et utilise une implémentation non optimisée du Enumerablemodule qui énumère littéralement tous les éléments:

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

Traduit en code Ruby, cela permet:

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

Les deux include?et member?ont une complexité temporelle O (n) car les deux recherchent dans le tableau la première occurrence de la valeur attendue.

Nous pouvons utiliser un ensemble pour obtenir le temps d'accès O (1) au prix d'avoir à créer d'abord une représentation de hachage du tableau. Si vous vérifiez à plusieurs reprises l'appartenance à la même gamme, cet investissement initial peut être rentable rapidement. Setn'est pas implémenté en C mais en tant que classe Ruby simple, le temps d'accès O (1) du sous-jacent en @hashvaut la peine.

Voici l'implémentation de la classe 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

Comme vous pouvez le voir, la classe Set crée simplement une @hashinstance interne , mappe tous les objets trueet vérifie ensuite l'appartenance en utilisant Hash#include?ce qui est implémenté avec le temps d'accès O (1) dans la classe Hash.

Je ne discuterai pas des sept autres méthodes car elles sont toutes moins efficaces.

Il existe en fait encore plus de méthodes avec une complexité O (n) au-delà des 11 énumérées ci-dessus, mais j'ai décidé de ne pas les répertorier car elles analysent l'intégralité du tableau plutôt que de les casser lors de la première correspondance.

Ne les utilisez pas:

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

Plusieurs réponses suggèrent Array#include?, mais il y a une mise en garde importante: En regardant la source, même Array#include?effectuer une boucle:

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 façon de tester la présence du mot sans boucle est de construire un trie pour votre tableau. Il existe de nombreuses implémentations de trie (google "ruby trie"). Je vais utiliser rambling-triedans cet exemple:

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 }

Et maintenant, nous sommes prêts à tester la présence de différents mots dans votre tableau sans boucler dessus, dans le O(log n)temps, avec la même simplicité syntaxique que Array#include?, en utilisant sublinéaire Trie#include?:

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

Si vous ne voulez pas faire de boucle, il n'y a aucun moyen de le faire avec des tableaux. Vous devez utiliser un ensemble à la place.

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

Les ensembles fonctionnent en interne comme Hashs, donc Ruby n'a pas besoin de parcourir la collection pour trouver des éléments, car comme son nom l'indique, il génère des hachages des clés et crée une carte mémoire afin que chaque hachage pointe vers un certain point en mémoire. L'exemple précédent fait avec un Hash:

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

L'inconvénient est que les ensembles et les touches de hachage ne peuvent inclure que des éléments uniques et si vous ajoutez beaucoup d'éléments, Ruby devra refaire le tout après un certain nombre d'éléments pour créer une nouvelle carte qui convient à un espace de touches plus grand. Pour en savoir plus, je vous recommande de regarder " MountainWest RubyConf 2014 - Big O in a Homemade Hash par Nathan Long ".

Voici une référence:

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

Et les résultats:

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

Voici une autre façon de procéder: utilisez la Array#indexméthode.

Il renvoie l'index de la première occurrence de l'élément dans le tableau.

Par exemple:

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

index() peut également prendre un bloc:

Par exemple:

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

Cela renvoie l'index du premier mot du tableau qui contient la lettre «o».

Fait amusant,

Vous pouvez utiliser *pour vérifier l'appartenance à un tableau dans une caseexpression.

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

Notez le peu *dans la clause when, cela vérifie l'appartenance au tableau.

Tout le comportement magique habituel de l'opérateur splat s'applique, donc par exemple, si ce arrayn'est pas réellement un tableau mais un seul élément, il correspondra à cet élément.

Il existe plusieurs façons d'accomplir cela. Certains d'entre eux sont les suivants:

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

2.in? a  #=> true

8.in? a #=> false

a.member? 1 #=> true

a.member? 8 #=> false

Si vous avez besoin de vérifier plusieurs fois pour n'importe quelle clé, convertissez arren hash, et vérifiez maintenant 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

Performances de Hash # has_key? contre Array # include?

Paramètre Hash # has_key? Array # include

Complexité temporelle Fonctionnement O (1) Fonctionnement O (n) 

Type d'accès Accède au hachage [clé] s'il parcourt chaque élément
                        retourne alors toute valeur du tableau jusqu'à ce qu'il
                        true est renvoyé à la recherche de la valeur dans Array
                        Hash # has_key? appel
                        appel    

Pour une vérification unique, l'utilisation include?est correcte

Cela vous dira non seulement qu'il existe mais aussi combien de fois il apparaît:

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

Pour ce que ça vaut, les documents Ruby sont une ressource incroyable pour ce genre de questions.

Je prendrais également note de la longueur du tableau que vous recherchez. La include?méthode exécutera une recherche linéaire avec une complexité O (n) qui peut devenir assez moche en fonction de la taille du tableau.

Si vous travaillez avec un grand tableau (trié), j'envisagerais d'écrire un algorithme de recherche binaire qui ne devrait pas être trop difficile et qui présente le pire cas de O (log n).

Ou si vous utilisez Ruby 2.0, vous pouvez en profiter bsearch.

Tu peux essayer:

Exemple: si Cat et Dog existent dans le tableau:

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

Au lieu de:

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

Remarque: member?et include?sont les mêmes.

Cela peut faire le travail en une seule ligne!

Si nous voulons ne pas utiliser include?cela fonctionne aussi:

['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

Et de cette façon?

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

Si vous essayez de le faire dans un test unitaire MiniTest , vous pouvez utiliser assert_includes. Exemple:

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

Il y a l'inverse.

Supposons que le tableau soit [ :edit, :update, :create, :show ], enfin peut-être l'ensemble des sept péchés capitaux / mortels .

Et un autre jouet avec l'idée de tirer une action valide d'une chaîne:

"my brother would like me to update his profile"

Alors:

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

Si vous souhaitez renvoyer la valeur non seulement vrai ou faux, utilisez

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

Cela renverra «Dog» s'il existe dans la liste, sinon nul.

Voici une autre façon de procéder:

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

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

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

il existe de nombreuses façons de trouver un élément dans n'importe quel tableau, mais la manière la plus simple est «in?» méthode.

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

si vous ne souhaitez pas l'utiliser, include?vous pouvez d'abord envelopper l'élément dans un tableau, puis vérifier si l'élément encapsulé est égal à l'intersection du tableau et de l'élément encapsulé. Cela renverra une valeur booléenne basée sur l'égalité.

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

Je trouve toujours intéressant de faire quelques benchmarks pour voir la vitesse relative des différentes façons de faire quelque chose.

La recherche d'un élément de tableau au début, au milieu ou à la fin affectera toutes les recherches linéaires mais affectera à peine une recherche sur un ensemble.

La conversion d'un tableau en ensemble va provoquer un hit dans le temps de traitement, alors créez le jeu à partir d'un tableau une fois, ou commencez par un ensemble depuis le tout début.

Voici le code de référence:

# 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

Ce qui, lorsqu'il est exécuté sur mon ordinateur portable Mac OS, se traduit par:

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

Fondamentalement, les résultats me disent d'utiliser un ensemble pour tout si je recherche l'inclusion, sauf si je peux garantir que le premier élément est celui que je veux, ce qui n'est pas très probable. Il y a des frais généraux lors de l'insertion d'éléments dans un hachage, mais les temps de recherche sont tellement plus rapides que je ne pense pas que cela devrait être pris en compte. Encore une fois, si vous devez le rechercher, n'utilisez pas de tableau, utilisez un ensemble. (Ou un hachage.)

Plus le tableau est petit, plus les méthodes du tableau s'exécuteront rapidement, mais elles ne vont toujours pas suivre, bien que dans les petits tableaux, la différence puisse être minime.

« D' abord », « Moyen » et « Dernier » reflètent l'utilisation de first, size / 2et lastpour ARRAYl'élément recherchée. Cet élément sera utilisé lors de la recherche des variables ARRAYet SET.

Des modifications mineures ont été apportées aux méthodes comparées, > 0car le test devrait être >= 0destiné aux indextests de type.

Plus d'informations sur Fruity et sa méthodologie sont disponibles dans son README .