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

user211662 1182 ruby arrays

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

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

Brian Campbe.. 1762

您正在寻找include?:

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

  • 有时我希望它是"包含"不包括在内.我总是把它与包括在一起. (171认同)
  • 替代语法:`%w(Cat Dog Bird).包括?"Dog'` (64认同)
  • 我要注意,在内部,`#include?`仍然执行循环.但是,编码器不会明确地编写循环.我添加了一个真正执行任务而没有循环的答案. (13认同)
  • @HenleyChiu我称它为'['狗','鸟','猫']."Dog'` (6认同)
  • @AlfonsoVergara是的,任何数组解决方案都必须在内部进行某种循环; 如果没有循环,就无法测试数组的成员资格.如果您不想在内部进行任何循环,则需要使用不同的数据结构,例如具有固定大小键的完美哈希表.鉴于在没有内部循环的情况下无法测试数组中的成员资格,我将问题解释为"无需自己明确地编写循环" (4认同)

Marc-André L.. 220

正如@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?... 进行比较

  • 'Set`的+1,经常被忽略. (11认同)

用户甲.. 159

尝试

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

  • @jahrichie你在这个答案中选择"老语法"究竟是什么,可选括号? (59认同)
  • 我同意@Dennis,这不是更老,括号是可选的,在大多数情况下是一个好的做法....尝试使用包括没有括号的一行如果句子,例如,我的意思是根据你的情况你应该还是必须使用括号(根本不与"旧的"ruby语法相关) (2认同)

DigitalRoss.. 47

用途Enumerable#include:

a = %w/Cat Dog Bird/

a.include? 'Dog'

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

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


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


Van.. 44

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

%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


Boris Stitni.. 29

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

  • 请注意,这实际上包括一个循环; 任何不是O(1)的东西都包含某种循环.它恰好是输入字符串字符的循环.另请注意,对于那些关心效率的人来说,已经提到了"Set #include?"的答案; 加上使用符号而不是字符串,它可以是O(1)平均大小写(如果你使用字符串,那么只计算散列是O(n),其中n是字符串的长度).或者,如果您想使用第三方库,您可以使用O(1)最坏情况的完美哈希. (26认同)
  • 创建和维护trie的成本同样如此.如果你在阵列上进行了很多搜索操作,那么填充trie并维护它的内存和时间成本是值得的,但是对于单个,甚至数百或数千个检查,O(n)是非常合适的.另一个不需要添加依赖项的选项是对数组进行排序或按排序顺序维护它,在这种情况下,可以使用二进制搜索O(lg n)操作来检查包含. (10认同)
  • `a.each do ... end`嗯......不确定那不是一个循环 (7认同)
  • AFAIK,`Set`使用散列来索引其成员,所以实际上`Set #include?`_should_是复杂的O(1),对于分布良好的`Set`(更具体地说是散列的O(输入大小)),以及O(log(n/bucket-number))用于搜索) (3认同)

akuhn.. 28

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
...


Kimmo Lehto.. 16

如果您不想循环,则无法使用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)


Zack Xu.. 15

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


用户甲.. 8

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

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

2.in? a  #=> true

8.in? a #=> false

a.member? 1 #=> true

a.member? 8 #=> false

  • 请注意,`Object#in?`仅添加到Rails(即`ActiveSupport`)v3.1 +.它不适用于核心Ruby. (6认同)

akuhn.. 7

有趣的事实,

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

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

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

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


user3245240.. 5

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

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

  • 使用它没有任何意义,除非你想知道它出现了多少次,因为`.any?`一旦找到第一个匹配元素就会返回,`.count`将始终处理整个数组. (11认同)