Advertisement
Advertisement


How to check if a value exists in an array in Ruby


Question

I have a value 'Dog' and an array ['Cat', 'Dog', 'Bird'].

How do I check if it exists in the array without looping through it? Is there a simple way of checking if the value exists, nothing more?

2020/02/06
1
1327
2/6/2020 5:16:31 AM

Accepted Answer

You're looking for include?:

>> ['Cat', 'Dog', 'Bird'].include? 'Dog'
=> true
2016/04/29
1969
4/29/2016 12:02:04 PM

There is an in? method in ActiveSupport (part of Rails) since v3.1, as pointed out by @campaterson. So within Rails, or if you require 'active_support', you can write:

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

OTOH, there is no in operator or #in? method in Ruby itself, even though it has been proposed before, in particular by Yusuke Endoh a top notch member of ruby-core.

As pointed out by others, the reverse method include? exists, for all Enumerables including Array, Hash, Set, Range:

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

Note that if you have many values in your array, they will all be checked one after the other (i.e. O(n)), while that lookup for a hash will be constant time (i.e O(1)). So if you array is constant, for example, it is a good idea to use a Set instead. E.g:

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

A quick test reveals that calling include? on a 10 element Set is about 3.5x faster than calling it on the equivalent Array (if the element is not found).

A final closing note: be wary when using include? on a Range, there are subtleties, so refer to the doc and compare with cover?...


Try

['Cat', 'Dog', 'Bird'].include?('Dog')
2009/12/31

Use Enumerable#include:

a = %w/Cat Dog Bird/

a.include? 'Dog'

Or, if a number of tests are done,1 you can get rid of the loop (that even include? has) and go from O(n) to O(1) with:

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


1. I hope this is obvious but to head off objections: yes, for just a few lookups, the Hash[] and transpose ops dominate the profile and are each O(n) themselves.

2016/02/06

If you want to check by a block, you could try any? or 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  

See Enumerable for more information.

My inspiration came from "evaluate if array has any items in ruby"

2020/02/06

Ruby has eleven methods to find elements in an array.

The preferred one is include? or, for repeated access, creat a Set and then call include? or member?.

Here are all of them:

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

They all return a trueish value if the element is present.

include? is the preferred method. It uses a C-language for loop internally that breaks when an element matches the internal rb_equal_opt/rb_equal functions. It cannot get much more efficient unless you create a Set for repeated membership checks.

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? is not redefined in the Array class and uses an unoptimized implementation from the Enumerable module that literally enumerates through all elements:

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

Translated to Ruby code this does about the following:

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

Both include? and member? have O(n) time complexity since the both search the array for the first occurrence of the expected value.

We can use a Set to get O(1) access time at the cost of having to create a Hash representation of the array first. If you repeatedly check membership on the same array this initial investment can pay off quickly. Set is not implemented in C but as plain Ruby class, still the O(1) access time of the underlying @hash makes this worthwhile.

Here is the implementation of the Set class:

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

As you can see the Set class just creates an internal @hash instance, maps all objects to true and then checks membership using Hash#include? which is implemented with O(1) access time in the Hash class.

I won't discuss the other seven methods as they are all less efficient.

There are actually even more methods with O(n) complexity beyond the 11 listed above, but I decided to not list them since they scan the entire array rather than breaking at the first match.

Don't use these:

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