要素 - ruby 配列 追加




Rubyの配列に値が存在するかどうかを調べる (15)

私は値'Dog'と配列['Cat', 'Dog', 'Bird']を持っています。

それをループせずにアレイに存在するかどうかを確認するにはどうすればよいですか? 値が存在するかどうかを確認する簡単な方法はありますか?


Rubyには、配列内の要素を見つけるための11のメソッドがあります。

好ましいものはinclude?

繰り返しアクセスするには、セットを作成してから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値を返しtrue

include? 好ましい方法です。 要素が内部のrb_equal_opt/rb_equal関数と一致するときにブレークするC言語forループを内部的に使用します。 繰り返しのメンバーシップチェックのセットを作成しない限り、はるかに効率的になることはありません。

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モジュールの最適化されてEnumerableない実装を使用し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の@hashクラスでは、引き続き基になる@hashO(1)アクセスタイムがこれを価値あるものにします。

Setクラスの実装は次の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を使用してメンバーシップをチェックしHash#include? これはHashクラスのO(1)アクセス時間で実装されています。

他の7つの方法については、あまり効率的ではないので、私は議論しません。

実際には上記の11よりも複雑なO(n)複雑な方法がありますが、最初のマッチではなく、配列全体をスキャンしてからリストにしないことにしました。

これらを使用しないでください。

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

Enumerable#include使用する:

a = %w/Cat Dog Bird/

a.include? 'Dog'

あるいは、いくつかのテストが行​​われた場合、 1つのループを取り除くことができます(これにinclude? hasもinclude? )。そして、 O(n)からO(1)

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

私はこれが明らかであるが異論を避けることを望む:はい、ほんの数回の検索のために、ハッシュ[]と転置オプションはプロファイルを支配し、それぞれO(n)です。


あなたがインクルードを使いたくない場合は? 配列内の要素を最初にラップして、ラップされた要素が配列とラップされた要素の共通部分と等しいかどうかを確認できます。 これは、等価性に基づくブール値を返します。

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

あなたがブロックでチェックしたい場合は、何かを試すことができますか? またはすべて?

%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 : http://ruby-doc.org/core-1.9.3/Enumerable.html
私のインスピレーションはここから来ます: https://.com/a/10342734/576497 : https://.com/a/10342734/576497


いくつかの答えはArray#include? しかし、重要な注意点が1つあり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;
}

ルーピングなしで存在をテストする方法は、配列のトライを作成することです。 そこには多くのトライの実装があります(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 }

そして今、あなたはArray#include?と同じ構文上の単純さで、 O(log n)時間で、ループすることなく配列内のさまざまな単語の存在をテストする準備が整いましたArray#include? サブラインのTrie#include?を使用していTrie#include?

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

この方法はどうですか?

['Cat', 'Dog', 'Bird'].index('Dog')

これは、それが存在するだけでなく、何回出現するかを伝えます。

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

これを行うもう1つの方法があります:

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

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

そこin? メソッドActiveSupportによって指摘されているように、v3.1からActiveSupport (Railsの一部)に追加しました。 だから、Railsの中で、あるいはrequire 'active_support'require 'active_support'場合は、次のように書くことができます:

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

OTOH、 in演算子または#in?はありません#in? Ruby自体のトップノッチメンバーであるEndo Yusuke氏によって以前に提案されていたにもかかわらず、Ruby自体のメソッドである。

他の人によって指摘されているように、逆の方法にinclude? ArrayHashSetRangeを含むすべてのEnumerableに対して存在する:

['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?ことを明らかinclude? (要素が見つからない場合)同等のArray呼び出すよりも約3.5倍高速です。

最後の最後の注意: include?を使用するときは注意してくださいinclude? Rangeには微妙な点がありますので、文書を参照してcover?と比較してくださいcover? ...


それが価値あるものであるためには、 Rubyのドキュメントは、これらの種類の質問のための素晴らしいリソースです。

私はまたあなたが検索している配列の長さに注意します。 include? メソッドは、配列のサイズに応じてかなり醜いO(n)の複雑さを持つ線形検索を実行します。

大規模な(ソートされた)配列で作業している場合、私はバイナリ検索アルゴリズムを書くことを検討します。これはあまり難しくなく、最悪の場合はO(log n)です。

Ruby 2.0を使用している場合は、 bsearchを利用できます。


ループしたくない場合は、配列で行う方法はありません。 代わりにセットを使用する必要があります。

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はハッシュのように内部的に動作するので、コレクションをループする必要はありません。 前の例ではハッシュを使っています:

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

欠点は、セットとハッシュキーにはユニークなアイテムしか含めることができないことです。アイテムをたくさん追加すると、ルビは特定の数のアイテムの後にすべてを再ハッシュして、より大きなキースペースに適した新しいマップを作成する必要があります。 これについての詳細は、 MountainWest RubyConf 2014 - Nathan Longの自家製ハッシュの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)

楽しい事実、

*を使用して、 case式の配列メンバシップをチェックすることができます。

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

when節のlittle *に注目して、これは配列のメンバシップをチェックします。

splat演算子の通常の魔法の振る舞いはすべて適用されます。たとえば、 arrayが実際にはarrayはなく単一の要素であれば、その要素に一致します。


複数のキーをチェックする必要がある場合は、 arrhashに変換して、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?パフォーマンスHash#has_key? 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?を使用して1回チェックするにinclude? 結構です


試す

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

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




arrays