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

Question

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

如何在没有循环的情况下检查数组中是否存在？是否有一种简单的方法来检查值是否存在,仅此而已？

Answer 1

您正在寻找include?:

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

Answer 2

正如@campaterson所指出的,自v3.1以来,在(Rails的一部分)中有一种in?方法ActiveSupport.所以在Rails中,或者如果你require 'active_support',你可以写:

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

OTOH,Ruby本身没有in运算符或#in?方法,尽管之前已经提出过,特别是Yusuke Endoh是ruby-core的顶级成员.

如其他人指出的那样,反向方法include?存在,对所有Enumerables ^包括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.5倍比调用它的等效快Array(如果未找到该元素).

最后的结束注释:include?在a上使用时要小心Range,有细微之处,所以请参阅文档并与cover?... 进行比较

Answer 3

尝试

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

Answer 4

用途Enumerable#include:

a = %w/Cat Dog Bird/

a.include? 'Dog'

或者,如果完成了许多测试,¹你可以摆脱循环(甚至include?有)并从O(n)转到O(1):

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

^{1.我希望这是显而易见的,但要避免反对意见:是的,对于一些查找,Hash []和转置操作支配配置文件并且每个都是O(n).}

Answer 5

如果你想通过街区检查,你可以试试吗？还是全部？

%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

Answer 6

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?是首选的方法.它在for内部使用C语言循环,当元素与内部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类,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

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

实际上甚至有更多的方法具有O(n)超出上面列出的11的复杂性,但我决定不扫描它们,因为扫描整个阵列而不是在第一场比赛时打破.

不要使用这些,

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

Answer 7

有几个答案表明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

Answer 8

如果您不想循环,则无法使用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不需要遍历集合来查找项目,因为顾名思义,它会生成键的哈希值并创建一个内存映射,以便每个哈希都指向内存中的某个点.前面的示例使用Hash完成:

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

缺点是集合和散列键只能包含唯一的项目,如果你添加了很多项目,Ruby必须在一定数量的项目之后重新整理整个事物,以构建适合更大键空间的新映射.有关这方面的更多信息,我建议您观看MountainWest RubyConf 2014 - 由Nathan Long自制哈希大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)

Answer 9

这是另一种方法:使用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'的数组中第一个单词的索引.

Answer 10

检查是否存在

使用include?

例子：

arr = [1, 2, 3]
arr.include?(1) -> true
arr.include?(4) -> false

检查不存在

使用exclude?

例子：

arr = %w(vietnam china japan)
arr.exclude?('usa') -> true
arr.exclude?('china') -> false

Answer 11

有趣的事实,

您可以使用*检查case表达式中的数组成员身份.

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

注意*when子句中的一点,这将检查数组中的成员资格.

splat运算符的所有常见魔术行为都适用,例如,如果array实际上不是数组而是单个元素,它将匹配该元素.

Answer 12

有多种方法可以实现这一目标.其中一些如下:

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

2.in? a  #=> true

8.in? a #=> false

a.member? 1 #=> true

a.member? 8 #=> false

Answer 13

你可以试试：

示例：如果数组中存在 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?是一样的。

这可以在一行中完成工作！

Answer 14

如果您需要多次检查任何键，请转换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 的性能？与数组#include相比？

参数哈希#has_key？数组#include

时间复杂度 O(1) 操作 O(n) 操作 

访问类型访问 Hash[key] 如果它遍历每个元素
                        返回数组的任何值 then 直到它
                        返回 true 以找到 Array 中的值
                        哈希#has_key？称呼
                        称呼    

对于单次检查使用include?很好

Answer 15

就其价值而言，Ruby 文档是解决此类问题的绝佳资源。

我还会记下您正在搜索的数组的长度。该include?方法将运行复杂度为 O(n) 的线性搜索，根据数组的大小，这可能会变得非常难看。

如果您正在使用大型（已排序）数组，我会考虑编写一个二进制搜索算法，该算法应该不会太难并且最坏情况为 O(log n)。

或者，如果您使用的是 Ruby 2.0，则可以利用bsearch.

Answer 16

这不仅会告诉您它存在,还会告诉您它出现的次数:

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