检查一个数组是否存在于Ruby中的一个数组中

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

如何检查它是否存在于数组中而不循环? 有一个简单的方法来检查值是否存在,仅此而已?

你正在寻找include?

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

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

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

OTOH,没有in运营商或#in? 方法,尽pipe之前已经提出过, 尤其是由远藤裕辅为ruby核心的顶尖成员。

正如其他人所指出的,相反的方法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 

一个快速testing显示,调用include? 在一个10元素Set上的速度比在等价Array上调用速度快3.5倍(如果没有find该元素)。

最后的结尾注意:使用include?时要小心include? 在一个Range ,有微妙之处,所以参考文档,并与cover?比较cover?

尝试

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

使用Enumerable#include

 a = %w/Cat Dog Bird/ a.include? 'Dog' 

或者,如果一些testing完成了,你可以摆脱循环(甚至include? ),并从O(n)O(1)

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

1.我希望这是显而易见的,但要避免反对意见:是的,只有less数查找,Hash []和转置操作主宰了configuration文件,并且都是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

几个答案build议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; } 

在没有循环的情况下testing单词存在的方法是通过为您的数组构build一个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)时间内testing数组中各种单词的存在而不用循环它,与Array#include? #include具有相同的语法简单性Array#include? ,使用次线Trie#include?

 trie.include? 'bird' #=> true trie.include? 'duck' #=> false 

这是另一种方法:使用Array#索引方法。

它返回数组中第一次出现元素的索引。

例:

 a = ['cat','dog','horse'] if a.index('dog') puts "dog exists in the array" end 

index()也可以占用一个block

例如

 a = ['cat','dog','horse'] puts a.index {|x| x.match /o/} 

在这里,返回数组中包含字母“o”的第一个单词的索引。

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

首选的是include?

或者对于重复访问,创build一个集合然后调用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值。

include? 是首选的方法。 它在内部使用循环的C语言for当元素匹配内部rb_equal_opt/rb_equal函数时会中断循环。 除非您创build一个重复的成员资格检查集合,否则它不会更有效率。

 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)时间复杂度,因为它们都在数组中search期望值的第一次出现。

我们可以使用一个集合来获得O(1)访问时间,但必须首先创build一个数组的散列表示。 如果您重复检查同一arrays上的成员资格,这个初始投资可以很快得到回报。 Set不是在C中实现,而是作为普通的Ruby类,底层的@hashO(1)访问时间仍然值得。

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

我不会讨论其他7种方法,因为效率不高。

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

不要使用这些,

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

如果你不想循环,就没办法用数组来完成。 你应该使用一个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不需要遍历集合来查找项目,因为顾名思义,它会生成密钥的哈希值,并创build一个内存映射,以便每个哈希指向内存中的某个点。 前面的例子用一个Hash完成:

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

缺点是集合和散列键只能包含唯一的项目,如果添加了很多项目,Ruby将不得不在一定数量的项目之后重新散布整个事物,以构build适合更大键空间的新映射。 有关这方面的更多信息,我build议你在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) 

有多种方法可以做到这一点。 其中一些如下:

 a = [1,2,3,4,5] 2.in? a #=> true 8.in? a #=> false a.member? 1 #=> true a.member? 8 #=> false 

这不仅会告诉你它是否存在,而且会告诉你出现了多less次:

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

对于什么是值得的, Ruby文档是这些types的问题的一个惊人的资源。

我也会注意到你正在search的数组的长度。 include? 方法将运行一个线性search与O(N)的复杂性,可以变得相当丑陋根据数组的大小。

如果你正在处理一个大的(sorting的)数组,我会考虑编写一个二进制searchalgorithm ,这个algorithm不应该太难,而且最坏的情况是O(log n)。

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

有趣的事实,

您可以使用*来检查一个caseexpression式中的数组成员。

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

注意when子句中的little * ,这将检查数组中的成员。

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

如果你想要更多的价值…你可以尝试:

例如:如果猫和狗存在于数组中:

 (['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') 

注:会员? 并包括? 是相同的。

这可以做一行工作!

还有其他的方法!

假设数组是[:edit,:update,:create,:show] – 也许整个七个致命/安宁的罪恶 🙂

并进一步玩弄从一些string一个有效的行动的想法 – 说

我的兄弟会希望我更新他的个人资料

 [ :edit, :update, :create, :show ].select{|v| v if "my brother would like me to update his profile".downcase =~ /[,|.| |]#{v.to_s}[,|.| |]/} 

如果我们不想使用include? 这也适用:

 ['cat','dog','horse'].select{ |x| x == 'dog' }.any? 

这样呢?

 ['Cat', 'Dog', 'Bird'].index('Dog') 
 ['Cat', 'Dog', 'Bird'].detect { |x| x == 'Dog'} => "Dog" !['Cat', 'Dog', 'Bird'].detect { |x| x == 'Dog'}.nil? => true 

如果你不想使用include? 你可以先把这个元素包装在一个数组中,然后检查这个被包装的元素是否等于数组和被包装的元素的交集。 这将基于相等返回一个布尔值。

 def in_array?(array, item) item = [item] unless item.is_a?(Array) item == array & item end 

这是另一种方法来做到这一点:

 arr = ['Cat', 'Dog', 'Bird'] e = 'Dog' present = arr.size != (arr - [e]).size 
 array = [ 'Cat', 'Dog', 'Bird' ] array.include?("Dog") 

arr转换为hash ,现在检查O(1)倍数的任意键: hash = arr.map {|x| [x,true]}.to_h hash = arr.map {|x| [x,true]}.to_h

 arr = ['Cat', 'Dog', 'Bird'] hash = arr.map {|x| [x,true]}.to_h => {"Cat"=>true, "Dog"=>true, "Bird"=>true} hash["Dog"] => true hash["Insect"] => false 

性能的哈希#has_key? 与Array#include?

参数哈希#has_key? arrays#包括 

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

访问types访问散列[键],如果它遍历每个元素
                        返回数组的任何值直到它
                        返回true以查找Array中的值
                        哈希#对象的has_key? 呼叫
                        呼叫