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


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

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


1109
2017-12-31 17:49


起源


使用 。包括?方法。它返回一个你想要的布尔值。在你的情况下只需输入:['Cat','Dog','Bird'] .include('Dog')它应该返回布尔值true。 - Jwan622
不要用 包括?  方法,如果你想检查不同值的倍数是否存在于数组中,因为包含?每次都会迭代数组,每次都进行O(n)操作搜索,而不是进行哈希 hash = arr.map {|x| [x,true]}.to_h,现在检查是否 hash.has_key? 'Dog' 返回true或不返回 - aqfaridi
你不能真正做到“没有循环”。这在逻辑上是不可能的,计算机无法确定数组是否包含元素而不循环遍历元素以检查它们中的任何一个是否是它正在搜索的元素。当然,除非它是空的。然后我猜你不需要循环。 - tradeJmark


答案:


您正在寻找 include?

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

1664
2017-12-31 17:51



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


有一个 in? 方法 在 ActiveSupport (@ Rmp的一部分)自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))。因此,如果数组是常量,例如,使用a是个好主意  代替。例如:

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? 在...上 Range,有细微之处,所以参考 文件 并与之比较 cover?...


206
2018-05-15 12:50



而Ruby不包括 #in? 在它的核心,如果你使用Rails,它是可用的。 api.rubyonrails.org/classes/Object.html#method-i-in-3F (我知道这是一个Ruby,而不是一个Rails问题,但它可能会帮助任何想要使用的人 #in? 在Rails中。看起来它是在Rails 3.1中添加的 apidock.com/rails/Object/in%3F - campeterson
+1为 Set,经常被忽视。 - Jared Beck


尝试

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

157
2017-12-31 17:52



这是较旧的语法,看看^^^ @ brian的答案 - jahrichie
@jahrichie你在这个答案中可以考虑“老语法”,可选括号是什么? - Dennis
我同意@Dennis,这不是更老,括号是可选的,在大多数情况下是一个好的做法....尝试使用包括没有括号的一行如果句子,例如,我的意思是根据你的情况你是否应该使用括号(根本不与“旧”ruby语法相关) - d1jhoni1b


使用 Enumerable#include

a = %w/Cat Dog Bird/

a.include? 'Dog'

或者,如果进行了大量测试,1 你可以摆脱循环(甚至 include? 有)并且从 上) 至 O(1) 有:

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


1.我希望这是显而易见的,但是要避免反对意见:是的,对于一些查找,哈希[]和转置操作支配配置文件并且每个都是 上) 他们自己。


44
2017-12-31 17:52





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

%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


41
2018-05-20 09:08



如果你想检查任何/所有这些字符串包含在另一个字符串/常量中非常有用 - thanikkal


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

28
2018-06-10 16:23



a.each do ... end 嗯......不确定那不是一个循环 - Doorknob
请注意,这实际上包括一个循环;任何不是O(1)的东西都包含某种循环。它恰好是输入字符串字符的循环。还要注意比已经提到的答案 Set#include? 对于关注效率的人;加上使用符号代替字符串,它可以是O(1)平均大小写(如果你使用字符串,那么只计算散列是O(n),其中n是字符串的长度)。或者,如果您想使用第三方库,您可以使用O(1)最坏情况的完美哈希。 - Brian Campbell
据我所知, Set 实际上,使用哈希来为其成员编制索引 Set#include?  应该 具有良好分布的复杂度O(1) Set (更具体地说,用于散列的O(输入大小)和用于搜索的O(log(n / bucket-number)) - Uri Agassi
创建和维护trie的成本同样如此。如果你在阵列上进行很多搜索操作,那么填充trie并维护它的内存和时间成本是值得的,但对于单个,甚至数百或数千个检查,O(n)是完全合适的。另一个不需要添加依赖项的选项是对数组进行排序或按排序顺序维护它,在这种情况下,可以使用二进制搜索O(lg n)操作来检查包含。 - speakingcode
@speakingcode,你可能从务实的角度出发。但是OP要求“检查值是否存在,仅此而已,而不是循环”。当我写这个答案时,这里有许多实用的解决方案,但没有一个能真正满足提问者的字面要求。您对BST与尝试相关的观察是正确的,但对于字符串,trie是正确的工具, 甚至维基百科也知道这一点。构建和维护良好实施的特里的复杂性令人惊讶地有利。 - Boris Stitnicky


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类,仍然是 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 class只是创建一个内部 @hash 实例,将所有对象映射到 true 然后使用。检查成员资格 Hash#include? 这是用。实现的 O(1) 访问时间 Hash 类。

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

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

不要使用这些,

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

23
2017-12-25 23:40



多么无耻地说Ruby有11种方法可以做任何事情!只要你说有人会指出你错过了#12,然后是#13,依此类推。为了说明我的观点,我会建议其他方法,但首先让我质疑 11 你列举的方式。首先,你很难算数 index 和 find_index (要么 find 和 detect)作为单独的方法,因为它们只是同一方法的不同名称。其次,所有结束的表达方式 > 0 是不正确的,我确信这是一个疏忽。 (续) - Cary Swoveland
...arr.index(e)例如,返回 0 如果 arr[0] == e。你会记得 arr.index(e) 回报 nil 如果 e 不在场。 index 但是,如果有人正在搜索,则无法使用 nil 在 arr。 (同样的问题 rindex,未列出。)。将数组转换为集合然后使用set方法有点拉长。为什么不转换为哈希(使用数组中的键和任意值),然后使用哈希方法?即使转换为集合是正常的,也可以使用其他设置方法,例如 !arr.to_set.add?(e)。 (续) - Cary Swoveland
......正如所承诺的,这里有一些可以使用的方法: arr.count(e) > 0, arr != arr.dup.delete(e) , arr != arr - [e] 和 arr & [e] == [e]。人们也可以雇用 select 和 reject。 - Cary Swoveland


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

16
2018-05-29 19:58



如果使用detect,那么至少可以减少循环。检测将在第一个“检测到”项目处停止(为项目评估的块被评估为真)。此外,如果没有检测到任何内容,您可以告诉检测该怎么做(您可以传入lambda)。 - aenw
@aenw没有 include? 在第一次打? - Kimmo Lehto
你是绝对正确的。我已经习惯使用检测,我忘记了包含。感谢您的评论 - 这确保我更新了我的知识。 - aenw


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


15
2017-10-02 17:22



index 仍然遍历数组,它只返回元素的值。 - the Tin Man