我有一个值“狗”和一个数组[“猫”、“狗”、“鸟”]。

如何在不循环的情况下检查数组中是否存在它?是否有一种简单的方法来检查该值是否存在?


当前回答

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

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

2.in? a  #=> true

8.in? a #=> false

a.member? 1 #=> true

a.member? 8 #=> false

其他回答

在下面尝试

(['Cat', 'Dog', 'Bird'] & ['Dog']).any?

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

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

使用Enumerable#include:

a = %w/Cat Dog Bird/

a.include? 'Dog'

或者,如果完成了大量测试,1您可以摆脱循环(甚至包括?has),并通过以下方式从O(n)变为O(1):

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

1.我希望这是显而易见的,但为了避免反对意见:是的,对于几个查找,Hash[]和转置操作占据了配置文件的主导地位,并且每个操作本身都是O(n)。

如果需要多次检查任何键,请将arr转换为哈希,然后检查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的性能?与Array#include相比?

Parameter              Hash#has_key?                 Array#include 

Time Complexity         O(1) operation                O(n) operation 

Access Type             Accesses Hash[key] if it      Iterates through each element
                        returns any value then        of the array till it
                        true is returned to the       finds the value in Array
                        Hash#has_key? call
                        call    

对于一次性检查,使用include?很好

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

首选项包括?或者,对于重复访问,创建一个Set,然后调用include?或成员?。

以下是所有这些:

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

如果元素存在,它们都会返回真实值。

包括是优选的方法。它在内部使用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;
}

成员未在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

两者都包括?和成员?因为两者都在阵列中搜索期望值的第一次出现,所以具有O(n)时间复杂度。

我们可以使用Set来获得O(1)访问时间,代价是必须首先创建数组的Hash表示。如果您重复检查同一阵列的成员资格,那么最初的投资可以很快得到回报。Set没有在C中实现,而是作为一个普通的Ruby类实现,但底层@hash的O(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类中以O(1)访问时间实现。

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

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

不要使用这些:

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