[ruby] Ruby에서 배열에 값이 있는지 확인하는 방법

루비에는 배열에서 요소를 찾는 11 가지 방법이 있습니다.

바람직한 하나는 include?반복 된 액세스에 대해 호출 후 creat에 세트하고, 또는 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)은 시간 복잡도가 모두 기대 값의 첫번째 발생의 배열을 검색.

Set을 사용하여 배열의 해시 표현을 먼저 생성해야하는 비용으로 O (1) 액세스 시간을 얻을 수 있습니다. 동일한 어레이에서 멤버십을 반복해서 확인하면이 초기 투자가 빠르게 보상받을 수 있습니다. SetC에서는 구현되지 않지만 일반 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) 액세스 시간으로 구현 된 .

다른 7 가지 방법은 모두 덜 효율적이므로 다루지 않습니다.

실제로 위에 나열된 11 이상의 O (n) 복잡도를 가진 훨씬 더 많은 메소드가 있지만 첫 번째 일치를 깨지 않고 전체 배열을 스캔하기 때문에 나열하지 않기로 결정했습니다.

이것을 사용하지 마십시오 :

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

답변

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;
}

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 }

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