Frage Überprüfen Sie, ob in einem Array in Ruby ein Wert vorhanden ist


Ich habe einen Wert 'Dog' und ein Array ['Cat', 'Dog', 'Bird'].

Wie überprüfe ich, ob es im Array existiert, ohne es zu durchlaufen? Gibt es eine einfache Möglichkeit zu überprüfen, ob der Wert existiert, nicht mehr?


1106
2017-12-31 17:49


Ursprung


Antworten:


Du schaust nach include?:

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

1659
2017-12-31 17:51



Da ist ein in? Methode im ActiveSupport (Teil von Rails) seit v3.1, wie von @campaterson gezeigt. Also in Rails, oder wenn Sie require 'active_support', Du kannst schreiben:

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

OTOH, es gibt keine in Betreiber oder #in? Methode in Ruby selbst, obwohl es zuvor vorgeschlagen wurde, insbesondere von Yusuke Endoh ein erstklassiges Mitglied des Rubinkerns.

Wie von anderen gesagt, die umgekehrte Methode include? existiert für alle Enumerables einschließlich Array, Hash, Set, Range:

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

Beachten Sie, dass, wenn Sie viele Werte in Ihrem Array haben, alle nacheinander überprüft werden (d. H. O(n)), während diese Suche nach einem Hash eine konstante Zeit ist (d. h O(1)). Wenn Sie zum Beispiel ein Array konstant haben, ist es eine gute Idee, a zu verwenden einstellen stattdessen. Z.B:

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

EIN schnell Test enthüllt diese Berufung include? auf einem 10 Element Set ist etwa 3,5x schneller als das Aufrufen des Äquivalents Array (wenn das Element nicht gefunden wird).

Eine abschließende Schlussnotiz: Vorsicht bei der Verwendung include? auf einen Range, es gibt Feinheiten, so beziehen Sie sich auf der Arzt und vergleichen mit cover?...


205
2018-05-15 12:50



Versuchen

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

157
2017-12-31 17:52



Benutzen Enumerable#include:

a = %w/Cat Dog Bird/

a.include? 'Dog'

Oder, wenn eine Reihe von Tests durchgeführt werden,1 Sie können die Schleife loswerden (dass sogar include? hat) und gehen von Auf) zu O (1) mit:

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


1. Ich hoffe, dass dies offensichtlich ist, um Einwände abzuwenden: Ja, für nur ein paar Nachschlagewerke dominieren die Hash- und Transponier-Ops das Profil und sind jeder Auf) sich.


44
2017-12-31 17:52



Wenn Sie nach einem Block suchen möchten, können Sie es versuchen? oder alle ?.

%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  

Details sind hier: http://ruby-doc.org/core-1.9.3/Enumerable.html
Meine Inspiration kommt von hier: https://stackoverflow.com/a/10342734/576497


41
2018-05-20 09:08



Mehrere Antworten deuten darauf hin Array#include?, aber es gibt eine wichtige Einschränkung: Die Quelle selbst betrachten Array#include? macht Looping:

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

Die Art, das Wort Präsenz ohne Schleifen zu testen, besteht darin, a zu konstruieren Trie für dein Array. Es gibt viele Trie-Implementierungen (google "ruby trie"). ich werde benützen rambling-trie in diesem Beispiel:

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 }

Und nun sind wir bereit, das Vorhandensein verschiedener Wörter in Ihrem Array zu testen, ohne es zu überfliegen O(log n) Zeit, mit der gleichen syntaktischen Einfachheit wie Array#include?, unter Verwendung von Sublinear Trie#include?:

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

28
2018-06-10 16:23



Ruby hat 11 Methoden, um Elemente in einem Array zu finden.

Das bevorzugte ist include?

Oder für wiederholten Zugriff, Erstellen eines Satzes und dann aufrufen include? oder member?

Hier sind sie alle,

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

Alle von ihnen geben ein trueish-Wert, wenn das Element vorhanden ist.

include? ist die bevorzugte Methode. Es verwendet eine C-Sprache for Schleife intern, die bricht, wenn ein Element mit dem internen übereinstimmt rb_equal_opt/rb_equalFunktionen. Es kann nicht viel effizienter werden, wenn Sie nicht einen Satz für wiederholte Mitgliedsprüfungen erstellen.

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? wird nicht neu definiert Array Klasse und verwendet eine nicht optimierte Implementierung aus der Enumerable Modul, die buchstäblich durch alle Elemente aufzählen.

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

In Ruby-Code übersetzt, tut dies Folgendes

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

Beide include? und member? haben O(n) Zeitkomplexität, da beide das Array nach dem ersten Auftreten des erwarteten Wertes durchsuchen.

Wir können ein Set verwenden, um zu bekommen O(1) Zugriffszeit auf Kosten der Erstellung einer Hash-Darstellung des Arrays zuerst. Wenn Sie wiederholt die Mitgliedschaft auf dem gleichen Array überprüfen, kann sich diese Anfangsinvestition schnell auszahlen. Set ist nicht in C implementiert, sondern als einfache Ruby-Klasse, immer noch die O(1) Zugriffszeit des Basiswerts @hash macht es sich gelohnt.

Hier ist die Umsetzung der Set Klasse,

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

Wie Sie sehen können Set Klasse erstellt nur ein internes @hash Instanz, ordnet alle Objekte zu true und überprüft dann die Mitgliedschaft mit Hash#include? was mit implementiert wird O(1) Zugriffszeit in der Hash Klasse.

Ich werde die anderen 7 Methoden nicht diskutieren, da sie alle weniger effizient sind.

Es gibt tatsächlich noch mehr Methoden mit O(n) Komplexität über die 11 oben aufgeführten hinaus, aber ich beschloss, sie nicht aufzulisten, da das gesamte Array scannen, anstatt beim ersten Spiel zu brechen.

Benutze diese nicht,

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

23
2017-12-25 23:40



Wenn Sie keine Schleife machen wollen, gibt es keine Möglichkeit, dies mit Arrays zu tun. Sie sollten stattdessen ein Set verwenden.

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

Sätze arbeiten intern wie Hashes, also muss Ruby nicht durch die Sammlung laufen, um Elemente zu finden, da, wie der Name andeutet, es Hashes der Schlüssel generiert und eine Speicherzuordnung erstellt, so dass jeder Hash auf einen bestimmten Punkt im Speicher zeigt. Das vorherige Beispiel mit einem Hash:

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

Der Nachteil ist, dass Sets und Hash-Schlüssel nur eindeutige Elemente enthalten können und wenn Sie viele Elemente hinzufügen, muss Ruby das Ganze nach einer bestimmten Anzahl von Elementen erneut zusammenstellen, um eine neue Map zu erstellen, die zu einem größeren Schlüsselbereich passt. Für mehr darüber empfehle ich Ihnen zu sehen MountainWest RubyConf 2014 - Big O in einem selbstgemachten Hash von Nathan Long 

Hier ist ein Benchmark:

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

Und die Ergebnisse:

      user     system      total        real
array  7.020000   0.000000   7.020000 (  7.031525)
set    0.010000   0.000000   0.010000 (  0.004816)

16
2018-05-29 19:58