with - ruby select




检查Ruby中数组是否存在值 (16)

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

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


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值。

include? 是首选的方法。 它在内部使用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类,底层@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类只是创建一个内部@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
...

你可以在你的数组中找到:

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

要么

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


使用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)


几个答案建议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?相同的语法简单性Array#include? ,使用sublinear Trie#include?

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

如果你不想循环,那么无法用数组来完成。 您应该使用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将不得不在一定数量的项目之后重新散布整个项目,以构建适合更大键空间的新映射。 有关这方面的更多信息,我建议您观看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)


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

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

对于它的价值, Ruby文档对于这些问题来说是一个惊人的资源。

我还会注意到你正在搜索的数组的长度。 include? 方法将运行O(n)复杂度的线性搜索,根据数组的大小可能会变得非常难看。

如果你正在处理一个大的(排序的)数组,我会考虑编写一个二进制搜索算法 ,这个算法不应该太难,并且最坏的情况是O(log n)。

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


尝试

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

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

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

OTOH,没有in运营商或#in? 方法,尽管之前已经提出过, 特别是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? ...


有趣的事实,

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

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

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

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


还有其他的方法!

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

并进一步玩弄从一些字符串中拉出有效动作的想法 - 比如说

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

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

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

arr = ['Cat', 'Dog', 'Bird']
e = 'Dog'

present = arr.size != (arr - [e]).size

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

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

例:

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'的第一个单词的索引。


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

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




arrays