检查 Ruby 中的数组中是否存在值

我有一个值'Dog'和一个数组['Cat', 'Dog', 'Bird']

如何检查它是否存在于数组中而不遍历它?有没有简单的方法检查值是否存在,仅此而已?

答案

您要寻找include?

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

有一个in?方法ActiveSupport因为 V3.1(滑轨的一部分),如通过 @campaterson 指出。因此,在 Rails 中,或者如果您require 'active_support' ,您可以编写:

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

OTOH,没有in运算符或#in?即使以前已经提出过 Ruby 本身的方法, 尤其是由 Yusuke Endoh提出的红宝石核心的顶级成员。

正如其他人指出的,反向方法include?对于所有Enumerable都存在,包括ArrayHashSetRange

['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速度比在等效Array上调用它快 3.5 倍(如果找不到该元素)。

最后的结束语:使用include?时要小心include?Range ,有一些微妙之处,因此请参考文档并与cover?比较cover? ...

尝试

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

使用Enumerable#include

a = %w/Cat Dog Bird/

a.include? 'Dog'

或者,如果完成了许多测试,则1可以摆脱循环(甚至include? has),并通过以下方式从O(n)变为O(1)

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


1. 我希望这很明显,但是可以避免异议:是的,仅需进行几次查找,Hash [] 和转置操作就可以控制配置文件,并且它们各自都是O(n)

如果要按块检查,可以尝试任何方法吗?还是全部?

%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

详细信息在这里: http : //ruby-doc.org/core-1.9.3/Enumerable.html
我的灵感来自这里: https : //stackoverflow.com/a/10342734/576497

Ruby 有 11 种方法来查找数组中的元素。

首选的是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?是首选方法。它在内部使用 C 语言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)时间复杂度。

我们可以使用一个集合来获取O(1)访问时间,但必须首先创建数组的哈希表示。如果您反复检查同一阵列上的成员资格,则此初始投资可以很快得到回报。 Set不是用 C 实现的,但作为普通的 Ruby 类,底层@hashO(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?检查成员资格Hash#include?Hash类中使用O(1)访问时间实现。

我不会讨论其他 7 种方法,因为它们效率都较低。

实际上,除了上面列出的 11 种方法外,还有更多具有O(n)复杂度的方法,但是我决定不列出它们,因为扫描整个数组而不是在第一次匹配时中断。

不要用这些

# 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 。那里有许多 Trie 实现(谷歌 “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

如果您不想循环,则无法使用 Arrays 进行循环。您应该改用 Set。

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 不需要遍历集合就可以查找项目,因为顾名思义,它会生成键的哈希并创建内存映射,从而每个哈希都指向内存中的特定点。前面的示例使用哈希完成:

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

缺点是 Set 和 hash 键只能包含唯一项,如果添加很多项,Ruby 将必须在一定数量的项后重新哈希整个对象,以构建适合较大键空间的新映射。有关此的更多信息,我建议您观看Nathan Long 制作的《 MountainWest RubyConf 2014 - 自制哈希中的 Big O》

这是一个基准:

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实际上不是数组而是单个元素,它将与该元素匹配。