Как проверить, существует ли значение в массиве в Ruby

У меня есть значение 'Dog'и массив['Cat', 'Dog', 'Bird'] .

Как проверить, существует ли он в массиве, не проходя через него? Есть ли простой способ проверить, существует ли значение, не более того?

Вы ищете include?:

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

Существует in?метод в ActiveSupport(часть Rails) , так как v3.1, как отметил @campaterson. Так что в Rails, или если вы require 'active_support', вы можете написать:

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

OTOH, в самом Ruby нет inоператора или #in?метода, хотя он был предложен ранее, в частности Юсуке Эндо, высококлассным участником ruby-core.

Как указывалось другими, обратный метод include?существует, то для всех Enumerableх в том числе Array,Hash , Set, Range:

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

Обратите внимание, что если в вашем массиве много значений, все они будут проверяться одно за другим (т.е. O(n) ), В то время как поиск хеша будет иметь постоянное время (т O(1). Е. ). Так, например, если ваш массив является константой, лучше использовать вместо него Set . Например:

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

Быстрый тест показывает , что вызов include?на 10 элемента Setсоставляет около 3.5x быстрее , чем вызов его эквивалентArray (если элемент не найден).

Заключительное примечание: будьте осторожны при использовании include?на Range, есть тонкости, поэтому обратитесь к документу и сравните сcover? ...

Пытаться

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

Используйте Enumerable#include:

a = %w/Cat Dog Bird/

a.include? 'Dog'

Или, если выполнено несколько тестов, ¹ вы можете избавиться от цикла (который даже include?имеет) и перейти от O (n) к O (1) с помощью:

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

Если вы хотите проверить блок, вы можете попробовать any?или 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  

Смотри Enumerable для получения дополнительной информации.

Мое вдохновение пришло от " оценить, есть ли в массиве какие-либо элементы в ruby "

В Ruby есть одиннадцать методов поиска элементов в массиве.

Предпочтительным является include?или, для повторного доступа, создать набор, а затем вызвать include?илиmember? .

Вот все из них:

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

Все они возвращают trueзначение ish, если элемент присутствует.

include?является предпочтительным методом. Он использует forвнутренний цикл языка Си, который прерывается, когда элемент соответствует внутренним rb_equal_opt/rb_equalфункциям. Он не может стать намного более эффективным, если вы не создадите Набор для повторных проверок членства.

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?не переопределяется в Arrayклассе и использует неоптимизированную реализацию из Enumerableмодуля, который буквально перечисляет все элементы:

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

В переводе на код Ruby это касается следующего:

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

Оба include?иmember? имеют O (n) временную сложность, поскольку оба ищут в массиве первое вхождение ожидаемого значения.

Мы можем использовать Set, чтобы получить O (1) время доступа за счет необходимости сначала создать хеш-представление массива. Если вы неоднократно проверяете членство в одном и том же массиве, первоначальные инвестиции могут быстро окупиться. Setне реализован в C, но является простым классом Ruby, однако время доступа O (1) базового@hash делает это полезным.

Вот реализация класса 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

Как вы можете видеть, класс Set просто создает внутренний @hashэкземпляр, сопоставляет все объекты trueи затем проверяет членство, используяHash#include? который реализован с временем доступа O (1) в классе Hash.

Я не буду обсуждать другие семь методов, поскольку они все менее эффективны.

На самом деле существует еще больше методов со сложностью O (n), кроме перечисленных выше 11, но я решил не перечислять их, так как они сканируют весь массив, а не разбиваются при первом совпадении.

Не используйте это:

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

Несколько ответов предполагают Array#include?, но есть одно важное предостережение: глядя на источник, даже Array#include?выполняет циклы:

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

Чтобы проверить наличие слова без зацикливания, нужно создать дерево для вашего массива. Существует множество реализаций trie (google "ruby trie"). Я буду использовать rambling-trieв этом примере:

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 }

И теперь мы готовы проверить наличие различных слов в вашем массиве, не зацикливаясь на нем, со O(log n)временем, с той же синтаксической простотой, что Array#include?и с использованием сублинейного выражения Trie#include?:

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

Если вы не хотите зацикливаться, нет способа сделать это с массивами. Вы должны использовать набор вместо этого.

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

Наборы работают внутренне, как хеши, поэтому Ruby не нужно перебирать коллекцию для поиска элементов, поскольку, как следует из названия, он генерирует хеши ключей и создает карту памяти, так что каждый хеш указывает на определенную точку в памяти. Предыдущий пример сделан с Hash:

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

Недостатком является то, что наборы и хэш-ключи могут включать только уникальные элементы, и если вы добавите много элементов, Ruby придется перефразировать все это после определенного количества элементов, чтобы построить новую карту, которая соответствует большему пространству клавиш. Чтобы узнать больше об этом, я рекомендую вам посмотреть " MountainWest RubyConf 2014 - Big O in Homemade Hash" от Натана Лонга ".

Вот эталон:

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

И результаты:

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

Это еще один способ сделать это: использовать Array#index метод.

Возвращает индекс первого вхождения элемента в массиве.

Например:

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

index() также можно взять блок:

Например:

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

Это возвращает индекс первого слова в массиве, который содержит букву 'o'.

Интересный факт,

Вы можете использовать *для проверки членства в массиве в caseвыражениях.

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

Обратите внимание на маленький * в предложении when это проверяет членство в массиве.

Применяется все обычное магическое поведение оператора splat, поэтому, например, если на arrayсамом деле это не массив, а отдельный элемент, он будет соответствовать этому элементу.

Есть несколько способов сделать это. Вот некоторые из них:

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

2.in? a  #=> true

8.in? a #=> false

a.member? 1 #=> true

a.member? 8 #=> false

Если вам нужно проверить кратность для любого ключа, преобразуйте arrв hash, и теперь отметьте 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

Производительность Hash # has_key? по сравнению с массивом # включить?

Параметр Hash # has_key? Массив # включают

Сложность времени O (1) операция O (n) операция 

Тип доступа Получает доступ к Hash [key], если он проходит через каждый элемент
                        возвращает любое значение массива до
                        true возвращается к находкам, значение в массиве
                        Hash # has_key? вызов
                        вызов    

Для одной проверки времени , используя include?отлично

Это скажет вам не только, что он существует, но и сколько раз он появляется:

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

Что бы это ни стоило, документы Ruby - удивительный ресурс для таких вопросов.

Я бы также принял к сведению длину массива, который вы просматриваете. include?Метод будет работать линейный поиск с O (N) сложности , которые могут получить довольно уродливые в зависимости от размера массива.

Если вы работаете с большим (отсортированным) массивом, я бы подумал написать алгоритм двоичного поиска, который не должен быть слишком сложным и имеет наихудший случай O (log n).

Или, если вы используете Ruby 2.0, вы можете воспользоваться bsearch.

Ты можешь попробовать:

Пример: если Cat и Dog существуют в массиве:

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

Вместо:

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

Замечания: member? иinclude? так же.

Это может сделать работу в одну строку!

Если мы хотим не использовать include?это также работает:

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

Как насчет этого?

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

Если вы пытаетесь сделать это в модульном тесте MiniTest , вы можете использовать assert_includes. Пример:

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

Есть и другой способ обойти это.

Предположим, что массив [ :edit, :update, :create, :show ], ну, может быть, все семь смертных / успокоительных грехов .

А дальше игрушка с идеей вытянуть действительное действие из какой-то строки:

"my brother would like me to update his profile"

Затем:

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

Если вы хотите вернуть значение не просто true или false, используйте

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

Это вернет «Собаку», если она существует в списке, в противном случае ноль.

Вот еще один способ сделать это:

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

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

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

у него есть много способов найти элемент в любом массиве, но самый простой способ - «в?» метод.

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

если вы не хотите использовать, include?вы можете сначала обернуть элемент в массив, а затем проверить, равен ли обернутый элемент пересечению массива и обернутого элемента. Это вернет логическое значение, основанное на равенстве.

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

Мне всегда интересно запускать некоторые тесты, чтобы увидеть относительную скорость различных способов сделать что-то.

Поиск элемента массива в начале, середине или конце повлияет на любые линейные поиски, но едва повлияет на поиск по множеству.

Преобразование массива в набор приведет к потере времени обработки, поэтому создайте набор из массива один раз или начните с набора с самого начала.

Вот эталонный код:

# 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

Что, при запуске на моем ноутбуке Mac OS, приводит к:

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

В основном результаты говорят мне, чтобы я использовал Set для всего, если я собираюсь искать включение, если я не могу гарантировать, что первый элемент - тот, который я хочу, что не очень вероятно. При вставке элементов в хеш есть некоторые издержки, но время поиска намного быстрее, я не думаю, что это когда-либо стоит учитывать. Опять же, если вам нужно найти его, не используйте массив, используйте набор. (Или хэш.)

Чем меньше Array, тем быстрее будут работать методы Array, но они все равно не будут отставать, хотя в небольших массивах разница может быть крошечной.

«Первый», «Средний» и «Last» отражают использование first, size / 2и lastдля ARRAYдля элемента разыскивается. Этот элемент будет использоваться при поиске ARRAYи SETпеременных.

Незначительные изменения были внесены в методы, с которыми сравнивались, > 0потому что тест должен быть >= 0для indexтиповых тестов.

Более подробная информация о Fruity и его методологии доступна в README .