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

1315

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

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

user211662
quelle
5
Verwenden Sie die .include? Methode . Es gibt einen Booleschen Wert zurück, den Sie möchten. In Ihrem Fall geben Sie einfach Folgendes ein: ['Katze', 'Hund', 'Vogel']. Include ('Hund') und es sollte den Booleschen Wert true zurückgeben.
Jwan622
nicht verwenden enthalten? Methode, wenn Sie mehrmals überprüfen möchten, ob ein anderer Wert im Array vorhanden ist oder nicht, weil include? Jedes Mal wird über das Array iteriert, wobei jedes Mal eine O (n) hash = arr.map {|x| [x,true]}.to_hhash.has_key? 'Dog'
-Operation
3
Sie können es nicht wirklich vollständig tun, "ohne es zu durchlaufen". Es ist logisch unmöglich, der Computer kann einfach nicht sicher wissen, ob das Array das Element enthält, ohne die Elemente zu durchlaufen, um zu überprüfen, ob eines der Elemente das ist, nach dem es sucht. Es sei denn, es ist natürlich leer. Dann brauchst du wohl keine Schleife.
Tim M.
In den folgenden Benchmarks finden Sie Tests zum Unterschied der verschiedenen Möglichkeiten, ein Element in einem Array und einer Menge zu finden. stackoverflow.com/a/60404934/128421
der Blechmann

Antworten:

1945

Sie suchen include?:

>> ['Cat', 'Dog', 'Bird'].include? 'Dog'
=> true
Brian Campbell
quelle
73
Alternative Syntax:%w(Cat Dog Bird).include? 'Dog'
scarver2
184
Manchmal wünschte ich, es wäre "enthält" nicht enthalten. Ich verstehe es immer mit Includes.
Henley Chiu
19
Lassen Sie mich nur bemerken, dass intern #include?immer noch eine Schleife ausgeführt wird. Der Codierer wird jedoch davor bewahrt, die Schleife explizit zu schreiben. Ich habe eine Antwort hinzugefügt, die die Aufgabe wirklich ohne Schleifen ausführt.
Boris Stitnicky
8
@ HenleyChiu I, wie es genannt wurde[ 'Dog', 'Bird', 'Cat' ].has? 'Dog'
4
@AlfonsoVergara Ja, jede Lösung für ein Array muss intern eine Art Schleife ausführen. Es gibt keine Möglichkeit, die Mitgliedschaft in einem Array ohne Schleife zu testen. Wenn Sie auch intern keine Schleifen ausführen möchten, müssen Sie eine andere Datenstruktur verwenden, z. B. eine perfekte Hash-Tabelle mit Schlüsseln fester Größe. Da es keine Möglichkeit gibt, die Mitgliedschaft in einem Array zu testen, ohne eine interne Schleife durchzuführen, interpretierte ich die Frage als "ohne die Schleife explizit selbst schreiben zu müssen"
Brian Campbell,
250

In (Teil von Rails) gibt es seit Version 3.1 eine in?MethodeActiveSupport , auf die @campaterson hingewiesen hat. Also innerhalb von Rails, oder wenn Sie require 'active_support', können Sie schreiben:

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

OTOH, es gibt keinen inOperator oder keine #in?Methode in Ruby selbst, obwohl dies bereits zuvor vorgeschlagen wurde, insbesondere von Yusuke Endoh, einem erstklassigen Mitglied von Ruby-Core.

Wie von anderen darauf hingewiesen wird, 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, diese alle nacheinander überprüft werden (dh O(n)), während die Suche nach einem Hash eine konstante Zeit ist (dh O(1)). Wenn Ihr Array beispielsweise konstant ist, ist es eine gute Idee, stattdessen ein Set zu verwenden. 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 schneller Test zeigt, dass das Aufrufen include?eines 10-Elements Setetwa 3,5-mal schneller ist als das Aufrufen des entsprechenden ArrayElements (wenn das Element nicht gefunden wird).

Ein letzter abschließender Hinweis: Seien Sie vorsichtig, wenn Sie include?ein verwenden Range. Es gibt Feinheiten. Lesen Sie daher das Dokument und vergleichen Sie es mit cover?...

Marc-André Lafortune
quelle
2
Ruby ist zwar nicht #in?im Kern enthalten, aber wenn Sie Rails verwenden, ist es verfügbar. api.rubyonrails.org/classes/Object.html#method-i-in-3F (Ich weiß, dass dies eine Ruby-Frage ist, keine Rails-Frage, aber sie kann jedem helfen, der sie #in?in Rails verwenden möchte. Sieht so aus, als ob sie in Rails hinzugefügt wurde 3.1 apidock.com/rails/Object/in%3F
Campeterson
166

Versuchen

['Cat', 'Dog', 'Bird'].include?('Dog')
schmitzelburger
quelle
Dies ist die ältere Syntax, siehe ^^^ @ brians Antwort
Jahrichie
62
@jahrichie was genau betrachtest du als "ältere Syntax" in dieser Antwort, den optionalen Klammern?
Dennis
3
Ich stimme @Dennis zu, dies ist nicht älter, Klammern sind optional und in den meisten Fällen eine GUTE PRAXIS sollte oder muss Klammern verwenden oder nicht (überhaupt nicht mit "alten" Ruby-Syntaxen verwandt)
d1jhoni1b
Dies ist die einzige Syntax, mit der ich innerhalb einer ternären Operation arbeiten kann.
Michael Cameron
49

Verwendung Enumerable#include:

a = %w/Cat Dog Bird/

a.include? 'Dog'

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

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


1. Ich hoffe, dass dies offensichtlich ist, aber um Einwände abzuwenden: Ja, für nur ein paar Suchvorgänge dominieren die Hash [] - und Transponierungsoperationen das Profil und sind jeweils O (n) für sich.

DigitalRoss
quelle
48

Wenn Sie durch einen Block überprüfen möchten, können Sie versuchen any?oder all?.

%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  

Weitere Informationen finden Sie unter Aufzählbar .

Meine Inspiration kam von " bewerten, ob Array irgendwelche Elemente in Rubin hat "

Van
quelle
1
Sehr nützlich, wenn Sie überprüfen möchten, ob eine oder alle dieser Zeichenfolgen in einer anderen Zeichenfolge / Konstante enthalten sind
thanikkal
43

Ruby verfügt über elf Methoden, um Elemente in einem Array zu finden.

Das bevorzugte ist include?oder für wiederholten Zugriff ein Set erstellen und dann include?oder aufrufen member?.

Hier sind 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

Sie alle geben einen trueish-Wert zurück, wenn das Element vorhanden ist.

include?ist die bevorzugte Methode. Es wird forintern eine C-Sprachschleife verwendet , die unterbrochen wird, wenn ein Element mit den internen rb_equal_opt/rb_equalFunktionen übereinstimmt . Es kann nicht viel effizienter werden, wenn Sie kein Set für wiederholte Mitgliedschaftsprü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 in der ArrayKlasse nicht neu definiert und verwendet eine nicht optimierte Implementierung aus dem EnumerableModul, die buchstäblich alle Elemente auflistet :

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

Übersetzt in Ruby-Code bewirkt 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?undmember? haben eine zeitliche Komplexität von O (n), da beide das Array nach dem ersten Auftreten des erwarteten Werts durchsuchen.

Wir können ein Set verwenden, um die O (1) -Zugriffszeit zu erhalten, wenn zuerst eine Hash-Darstellung des Arrays erstellt werden muss. Wenn Sie wiederholt die Mitgliedschaft in demselben Array überprüfen, kann sich diese anfängliche Investition schnell auszahlen. Setist nicht in C implementiert, sondern als einfache Ruby-Klasse immer noch die O (1) -Zugriffszeit des Basiswerts@hash lohnt sich .

Hier ist die Implementierung 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, erstellt die Set-Klasse nur eine interne @hashInstanz, ordnet alle Objekte zu trueund überprüft dann die Mitgliedschaft mitHash#include? der die O (1) -Zugriffszeit in der Hash-Klasse implementiert wird.

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

Es gibt sogar noch mehr Methoden mit O (n) -Komplexität, die über die oben aufgeführten 11 hinausgehen, aber ich habe beschlossen, sie nicht aufzulisten, da sie das gesamte Array scannen, anstatt beim ersten Match zu brechen.

Verwenden Sie diese nicht:

# bad examples
array.grep(element).any? 
array.select { |each| each == element }.size > 0
...
akuhn
quelle
Wie dreist zu sagen, dass Ruby genau 11 Möglichkeiten hat, etwas zu tun! Sobald Sie sagen, dass jemand darauf hinweist, dass Sie # 12, dann # 13 und so weiter verpasst haben. Um meinen Standpunkt zu verdeutlichen, werde ich andere Wege vorschlagen, aber lassen Sie mich zunächst die von 11Ihnen aufgezählten Wege in Frage stellen. Erstens können Sie indexund find_index(oder findund detect) kaum als separate Methoden zählen, da es sich nur um unterschiedliche Namen für dieselbe Methode handelt. Zweitens sind alle Ausdrücke, die mit enden, > 0falsch, was sicher ein Versehen war. (Fortsetzung)
Cary Swoveland
... arr.index(e)gibt beispielsweise 0if zurück arr[0] == e. Sie werden arr.index(e)Rücksendungen zurückrufen, nilwenn diese enicht vorhanden sind. indexkann jedoch nicht verwendet werden, wenn nach nilin gesucht wird arr. (Gleiches Problem mit rindex, das nicht aufgeführt ist.) Das Konvertieren des Arrays in eine Menge und das anschließende Anwenden von Mengenmethoden ist etwas langwierig. Warum nicht dann in einen Hash konvertieren (mit Schlüsseln aus dem Array und beliebigen Werten) und dann Hash-Methoden verwenden? Auch wenn die Konvertierung in eine Menge in Ordnung ist, können andere Mengenmethoden verwendet werden, z !arr.to_set.add?(e). (Fortsetzung)
Cary Swoveland
... Wie versprochen, hier sind noch ein paar Methoden , die verwendet werden könnten: arr.count(e) > 0, arr != arr.dup.delete(e) , arr != arr - [e]und arr & [e] == [e]. Man könnte auch selectund beschäftigen reject.
Cary Swoveland
Ich würde die Verwendung eines Sets dringend empfehlen, wenn das Kriterium lautet, dass keine Duplikate zulässig sind und Sie wissen, ob ein bestimmtes Element in der Liste vorhanden ist. Set ist soooo viel schneller. Arrays sollten wirklich nicht verwendet werden, wenn eine Suche erforderlich ist. Sie werden besser als Warteschlange verwendet, in der Dinge vorübergehend gespeichert werden, um in der richtigen Reihenfolge verarbeitet zu werden. Hash und Set sind besser geeignet, um festzustellen, ob etwas vorhanden ist.
Der Blechmann
30

Mehrere Antworten deuten darauf hin Array#include?, aber es gibt eine wichtige Einschränkung: Wenn Sie sich die Quelle ansehen, wird sogar Array#include?eine Schleife ausgeführt:

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

Sie können die Wortpräsenz ohne Schleifen testen, indem Sie einen Versuch für Ihr Array erstellen. Es gibt viele Trie-Implementierungen (Google "Ruby Trie"). Ich werde rambling-triein diesem Beispiel verwenden:

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 jetzt sind wir bereit, das Vorhandensein verschiedener Wörter in Ihrem Array zu testen, ohne es O(log n)rechtzeitig mit derselben syntaktischen Einfachheit wie Array#include?mit sublinear zu durchlaufen Trie#include?:

trie.include? 'bird' #=> true
trie.include? 'duck' #=> false
Boris Stitnicky
quelle
8
a.each do ... endÄhm ... nicht sicher, wie das keine Schleife ist
Türknauf
27
Beachten Sie, dass dies tatsächlich eine Schleife enthält. Alles, was nicht O (1) ist, enthält eine Art Schleife. Es ist einfach eine Schleife über die Zeichen der Eingabezeichenfolge. Beachten Sie auch eine bereits erwähnte Antwort Set#include?für Personen, die sich Sorgen um Effizienz machen. In Verbindung mit der Verwendung von Symbolen anstelle von Zeichenfolgen kann dies ein O (1) -Durchschnitt sein (wenn Sie Zeichenfolgen verwenden, ist die Berechnung des Hashs nur O (n), wobei n die Länge der Zeichenfolge ist). Wenn Sie Bibliotheken von Drittanbietern verwenden möchten, können Sie einen perfekten Hash verwenden, der O (1) Worst Case ist.
Brian Campbell
4
AFAIK, SetVerwendungen Hashes indizieren ihre Mitglieder, also eigentlich Set#include? sollte Komplexität O (1) für eine gut verteilte Set(insbesondere O (Input-Größe) für das Hashing und O (log (N / bucket-Nummer)) für die Suche)
Uri Agassi
11
Die Kosten für die Erstellung und Wartung des Versuchs sind ebenso hoch. Wenn Sie viele Suchvorgänge für das Array ausführen, lohnt sich der Speicher- und Zeitaufwand für das Auffüllen und Verwalten eines Versuchs, aber für einzelne oder sogar Hunderte oder Tausende von Überprüfungen ist O (n) perfekt geeignet. Eine andere Option, bei der keine Abhängigkeiten hinzugefügt werden müssen, besteht darin, das Array zu sortieren oder in sortierter Reihenfolge zu verwalten. In diesem Fall kann eine binäre Suchoperation O (lg n) verwendet werden, um die Aufnahme zu überprüfen.
Speakingcode
1
@speakingcode, Sie können aus pragmatischer Sicht richtig liegen. Das OP fordert jedoch auf, "zu überprüfen, ob der Wert vorhanden ist, nichts weiter, ohne eine Schleife zu erstellen". Als ich diese Antwort schrieb, gab es hier viele pragmatische Lösungen, aber keine, die tatsächlich die wörtliche Anforderung des Fragestellers erfüllen würden. Ihre Beobachtung, dass BSTs mit Versuchen zusammenhängen, ist richtig, aber für Zeichenfolgen ist trie das richtige Werkzeug für den Job, selbst Wikipedia weiß so viel . Die Komplexität des Aufbaus und der Wartung eines gut implementierten Versuchs ist überraschend günstig.
Boris Stitnicky
18

Wenn Sie keine Schleife ausführen möchten, 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

Sets funktionieren intern wie Hashes, sodass Ruby die Sammlung nicht durchlaufen muss, um Elemente zu finden, da, wie der Name schon sagt, Hashes der Schlüssel generiert und eine Speicherzuordnung erstellt wird, sodass jeder Hash auf einen bestimmten Punkt im Speicher verweist. 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. Wenn Sie viele Elemente hinzufügen, muss Ruby das Ganze nach einer bestimmten Anzahl von Elementen erneut aufbereiten, um eine neue Karte zu erstellen, die für einen größeren Schlüsselbereich geeignet ist. Um mehr darüber zu erfahren , empfehle ich Ihnen, " MountainWest RubyConf 2014 - Big O in einem hausgemachten Hash von Nathan Long " anzusehen .

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)
Kimmo Lehto
quelle
Wenn Sie erkennen verwenden, können Sie die Schleife zumindest reduzieren. Die Erkennung stoppt beim ersten Element 'erkannt' (der für das Element übergebene Block wird als wahr ausgewertet). Außerdem können Sie erkennen, was zu tun ist, wenn nichts erkannt wird (Sie können ein Lambda übergeben).
Aenw
1
@aenw hört nicht include?beim ersten Treffer auf?
Kimmo Lehto
Du hast absolut recht. Ich bin es so gewohnt, zu erkennen, dass ich das über include vergessen hatte. Vielen Dank für Ihren Kommentar - er hat dafür gesorgt, dass ich mein Wissen auffrischte.
Aenw
include?stoppt beim ersten Treffer, aber wenn dieser Treffer am Ende der Liste steht ... Jede Lösung, die für die Speicherung auf ein Array angewiesen ist, hat mit zunehmender Liste eine abnehmende Leistung, insbesondere wenn am Ende der Liste ein Element gefunden werden muss Liste. Hash und Set haben dieses Problem nicht, ebenso wenig wie eine geordnete Liste und eine binäre Suche.
Der Blechmann
Genau darum ging es in dieser Antwort an erster Stelle :)
Kimmo Lehto
17

Dies ist eine andere Möglichkeit, dies zu tun: Verwenden Sie die Array#indexMethode.

Es gibt den Index des ersten Auftretens des Elements im Array zurück.

Zum Beispiel:

a = ['cat','dog','horse']
if a.index('dog')
    puts "dog exists in the array"
end

index() kann auch einen Block nehmen:

Zum Beispiel:

a = ['cat','dog','horse']
puts a.index {|x| x.match /o/}

Dies gibt den Index des ersten Wortes im Array zurück, das den Buchstaben 'o' enthält.

Zack Xu
quelle
indexiteriert immer noch über das Array, es gibt nur den Wert des Elements zurück.
der Blechmann
13

Lustige Tatsache,

Sie können *damit die Array-Mitgliedschaft in caseAusdrücken überprüfen .

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

Beachten Sie das kleine Element *in der when-Klausel, das die Mitgliedschaft im Array überprüft.

Es gilt das übliche magische Verhalten des Splat-Operators. Wenn arrayes sich also nicht um ein Array, sondern um ein einzelnes Element handelt, stimmt es mit diesem Element überein.

akuhn
quelle
Gut zu wissen..!
Cary Swoveland
Es wäre auch eine langsame erste Überprüfung in einer case-Anweisung, also würde ich sie in der whenletztmöglichen verwenden, damit andere, schnellere Überprüfungen schnell beseitigt werden.
Der Blechmann
9

Es gibt mehrere Möglichkeiten, dies zu erreichen. Einige davon sind wie folgt:

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

2.in? a  #=> true

8.in? a #=> false

a.member? 1 #=> true

a.member? 8 #=> false
sumit
quelle
6
Beachten Sie, dass dies Object#in?nur zu Rails (dh ActiveSupport) v3.1 + hinzugefügt wurde . Es ist in Ruby nicht verfügbar.
Tom Lord
5

Wenn Sie mehrmals nach einem Schlüssel suchen müssen, konvertieren Sie arrin hashund checken Sie jetzt O (1) ein.

arr = ['Cat', 'Dog', 'Bird']
hash = arr.map {|x| [x,true]}.to_h
 => {"Cat"=>true, "Dog"=>true, "Bird"=>true}
hash["Dog"]
 => true
hash["Insect"]
 => false

Leistung von Hash # has_key? versus Array # include?

Parameter Hash # has_key? Array # include

Zeitkomplexität O (1) -Operation O (n) -Operation 

Zugriffstyp Zugriff auf Hash [Schlüssel], wenn er durch jedes Element iteriert
                        Gibt dann einen beliebigen Wert des Arrays zurück
                        true wird zurückgegeben, um den Wert in Array zu finden
                        Hash # has_key? Anruf
                        Anruf    

Für die einmalige Überprüfung ist die Verwendung include?in Ordnung

aqfaridi
quelle
Durchlaufen Sie das Array nicht noch, um es in einen Hash zu konvertieren?
Chrisjacob
2
Ja, ich habe es getan, aber jetzt habe ich eine vorberechnete Antwort, um zu überprüfen, ob ein Element im Array vorhanden ist oder nicht. Wenn ich das nächste Mal nach einem anderen Wort suche, wird O (1) für die Abfrage benötigt, obwohl die Vorberechnung O (n) benötigt. Eigentlich habe ich include verwendet? in meiner Anwendung innerhalb der Schleife, um zu überprüfen, ob ein bestimmtes Element im Array vorhanden ist oder nicht, ruiniert es die Leistung, es prüfte in Ruby-Prof, das war der Engpass
aqfaridi
1
.... aber O (n) Raum und auch nein, es ist O (n) Zeit, denn wie @ chris72205 zu Recht hervorhebt, müssen Sie zuerst Ihr Array durchlaufen. O (1) + O (n) = O (n). Also in der Tat ist dies viel schlimmer als einzuschließen?
Rambatino
Alter, ich habe nur gesagt, verwenden Sie nicht include inside loop, für die einmalige Überprüfung mit include ist in Ordnung. Bitte lesen Sie zuerst den Anwendungsfall. Es ist besser, wenn Sie die Schleife mehrmals überprüfen müssen.
Aqfaridi
Das Konvertieren eines Arrays in einen Hash ist kostspielig, aber die Verwendung eines Arrays für die Suche ist die falsche Struktur. Arrays eignen sich besser als Warteschlangen, in denen die Reihenfolge wichtig sein kann. Hashes und Sets sind besser, wenn Inklusion / Existenz / Einzigartigkeit wichtig sind. Beginnen Sie mit dem richtigen Behälter und das Problem ist strittig.
Der Blechmann
4

Dies zeigt Ihnen nicht nur, dass es existiert, sondern auch, wie oft es erscheint:

 a = ['Cat', 'Dog', 'Bird']
 a.count("Dog")
 #=> 1
user3245240
quelle
12
Es macht keinen Sinn, dies zu verwenden, es sei denn, Sie möchten wissen, wie oft es angezeigt wird. Wenn Sie .any?jedoch zurückkehren, sobald das erste übereinstimmende Element gefunden wird, .countwird immer das gesamte Array verarbeitet.
Zaz
Dies zeigt zwar technisch, ob etwas vorhanden ist, ist aber auch NICHT der richtige Weg, wenn Sie Wert auf Geschwindigkeit legen.
Der Blechmann
4

Für das, was es wert ist, sind die Ruby-Dokumente eine erstaunliche Ressource für diese Art von Fragen.

Ich würde auch die Länge des Arrays zur Kenntnis nehmen, das Sie durchsuchen. Die include?Methode führt eine lineare Suche mit O (n) -Komplexität durch, die je nach Größe des Arrays ziemlich hässlich werden kann.

Wenn Sie mit einem großen (sortierten) Array arbeiten, würde ich in Betracht ziehen, einen binären Suchalgorithmus zu schreiben, der nicht zu schwierig sein sollte und den schlimmsten Fall von O (log n) aufweist.

Oder wenn Sie Ruby 2.0 verwenden, können Sie davon profitieren bsearch.

davissp14
quelle
3
Bei einer binären Suche wird davon ausgegangen, dass das Array sortiert (oder in irgendeiner Form angeordnet) ist, was für große Arrays kostspielig sein kann und häufig den Vorteil zunichte macht.
der Blechmann
Eine binäre Suche erfordert auch, dass alle Elementpaare mit vergleichbar sind <=>, was nicht immer der Fall ist. Angenommen, die Elemente des Arrays waren beispielsweise Hashes.
Cary Swoveland
1
@CarySwoveland sollte mehr oder weniger impliziert sein, dass die Elemente innerhalb eines sortierten Arrays vergleichbar sind.
Davissp14
4

Du kannst es versuchen:

Beispiel: Wenn Katze und Hund im Array vorhanden sind:

(['Cat','Dog','Bird'] & ['Cat','Dog'] ).size == 2   #or replace 2 with ['Cat','Dog].size

Anstatt:

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

Hinweis: member?und include?sind gleich.

Dies kann die Arbeit in einer Zeile erledigen!

Daniel Antonio Nuñez Carhuayo
quelle
3

Wenn wir dies nicht verwenden möchten, include?funktioniert dies auch:

['cat','dog','horse'].select{ |x| x == 'dog' }.any?
xlembouras
quelle
3
irgendein? akzeptiert auch Blöcke: ['Katze', 'Hund', 'Pferd']. {| x | x == 'Hund'}
Maikonas
3
['Cat', 'Dog', 'Bird'].detect { |x| x == 'Dog'}
=> "Dog"
!['Cat', 'Dog', 'Bird'].detect { |x| x == 'Dog'}.nil?
=> true
Rahul Patel
quelle
['Cat', nil, 'Dog'].detect { |x| x == nil } #=> nil. Wurde nilgefunden?
Cary Swoveland
2

Wie wäre es auf diese Weise?

['Cat', 'Dog', 'Bird'].index('Dog')
Ajahongir
quelle
Es wird immer noch über das Array iterieren, nur um das Element zu finden. Dann muss der Index dieses Elements zurückgegeben werden.
der Blechmann
2

Wenn Sie dies in einem MiniTest-Komponententest versuchen , können Sie verwenden assert_includes. Beispiel:

pets = ['Cat', 'Dog', 'Bird']
assert_includes(pets, 'Dog')      # -> passes
assert_includes(pets, 'Zebra')    # -> fails 
Jon Schneider
quelle
2

Es gibt den umgekehrten Weg.

Angenommen, das Array besteht aus [ :edit, :update, :create, :show ]den gesamten sieben tödlichen / erholsamen Sünden .

Und weiter mit der Idee , eine gültige Aktion aus einer Schnur zu ziehen:

"my brother would like me to update his profile"

Dann:

[ :edit, :update, :create, :show ].select{|v| v if "my brother would like me to update his profile".downcase =~ /[,|.| |]#{v.to_s}[,|.| |]/}
walt_die
quelle
1
Ihre Regex /[,|.| |]#{v.to_s}[,|.| |]/lässt mich denken, dass Sie "den Namen der Aktion finden wollten, die von einem der folgenden Elemente umgeben ist: Komma, Punkt, Leerzeichen oder gar nichts", aber es gibt einige subtile Fehler. "|update|"würde zurückkehren [:update]und "update"würde zurückkehren []. Zeichenklassen ( [...]) verwenden keine Pipes ( |), um Zeichen zu trennen. Selbst wenn wir sie in Gruppen ( (...)) ändern , können Sie keinem leeren Zeichen entsprechen. Also der Regex, den Sie wahrscheinlich wollten, ist/(,|\.| |^)#{v.to_s}(,|\.| |$)/
bkDJ
Die Regex ist in Ordnung (überprüft auf rubular.com) - und @Rambatino: das Warum wäre zum Beispiel wie Amazon Echo;) Man könnte sagen: "Bitte fügen Sie Hühnchen zu meiner Einkaufsliste hinzu" (und - na ja - dann müssten Sie füge das hinzu: füge dem Array hinzu, aber ich denke, du bekommst den Kern davon;)
walt_die
1
"Die Regex ist in Ordnung (überprüft auf rubular.com)". Es ist nicht in Ordnung. Ihre Regex stimmt nicht mit einem Schlüsselwort am Anfang oder Ende einer Zeichenfolge überein (z. B. "Profil meines Bruders aktualisieren"). Wenn Sie nicht mit dem Anfang oder Ende übereinstimmen möchten, ist Ihre Regex immer noch nicht in Ordnung, da die Zeichenklasse auf beiden Seiten des Schlüsselworts lauten sollte/[,. ]/
bkDJ
Wie @bkDJ sagt, ist der reguläre Ausdruck falsch. rubular.com/r/4EG04rANz6KET6
der Blechmann
1

Wenn Sie den Wert nicht nur wahr oder falsch zurückgeben möchten, verwenden Sie

array.find{|x| x == 'Dog'}

Dies gibt 'Hund' zurück, wenn es in der Liste vorhanden ist, andernfalls null.

gitb
quelle
Oder nutzen Sie, array.any?{|x| x == 'Dog'}wenn Sie es möchten wahr / falsch (nicht der Wert), sondern auch gegen einen Block vergleichen wollen so.
Mahemoff
0

Hier ist noch eine Möglichkeit, dies zu tun:

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

present = arr.size != (arr - [e]).size
Zauberstabmacher
quelle
1
Dies ist ein schrecklich ineffizienter Weg, dies zu tun! Ich stimme nicht ab, weil es technisch nicht falsch ist und jemand durch das Lesen etwas über Ruby lernen könnte, aber oben gibt es viele bessere Antworten.
Jibberia
Conehead können Sie vereinfachen arr != arr - [e]. arr & [e] == [e]ist ein anderer Weg in die gleiche Richtung.
Cary Swoveland
@CarySwoveland Mach dich nicht über einen Zaubererhut lustig ;-)
Wand Maker
Ich bezog mich mit größtem Respekt auf den Kopf des Zauberers, nicht auf den Hut.
Cary Swoveland
0
array = [ 'Cat', 'Dog', 'Bird' ]
array.include?("Dog")
Matthew Maurice
quelle
0

Es gibt viele Möglichkeiten, ein Element in einem Array zu finden, aber der einfachste Weg ist 'in?' Methode.

example:
arr = [1,2,3,4]
number = 1
puts "yes #{number} is present in arr" if number.in? arr
Abhishek Kumar
quelle
2
Hinweis: Wie in beschrieben dieser Antwort , wobei das Verfahren in?erfordert ActiveSupportimportiert werden: require active_support.
Patrick
Es werden nicht alle von Active benötigen , wenn Sie die Verwendung Kernerweiterungen .
Der Blechmann
0

Wenn Sie nicht verwenden möchten, können include?Sie das Element zuerst in ein Array einschließen und dann prüfen, ob das umschlossene Element dem Schnittpunkt des Arrays und des umschlossenen Elements entspricht. Dies gibt einen booleschen Wert zurück, der auf Gleichheit basiert.

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

Ich finde es immer interessant, einige Benchmarks durchzuführen, um die relative Geschwindigkeit der verschiedenen Arten zu sehen, etwas zu tun.

Das Suchen eines Array-Elements am Anfang, in der Mitte oder am Ende wirkt sich auf alle linearen Suchvorgänge aus, wirkt sich jedoch kaum auf die Suche nach einem Set aus.

Das Konvertieren eines Arrays in ein Set führt zu einer Beeinträchtigung der Verarbeitungszeit. Erstellen Sie das Set also einmal aus einem Array oder beginnen Sie von Anfang an mit einem Set.

Hier ist der Benchmark-Code:

# frozen_string_literal: true

require 'fruity'
require 'set'

ARRAY = (1..20_000).to_a
SET = ARRAY.to_set

DIVIDER = '-' * 20

def array_include?(elem)
  ARRAY.include?(elem)
end

def array_member?(elem)
  ARRAY.member?(elem)
end

def array_index(elem)
  ARRAY.index(elem) >= 0
end

def array_find_index(elem)
  ARRAY.find_index(elem) >= 0
end

def array_index_each(elem)
  ARRAY.index { |each| each == elem } >= 0
end

def array_find_index_each(elem)
  ARRAY.find_index { |each| each == elem } >= 0
end

def array_any_each(elem)
  ARRAY.any? { |each| each == elem }
end

def array_find_each(elem)
  ARRAY.find { |each| each == elem } != nil
end

def array_detect_each(elem)
  ARRAY.detect { |each| each == elem } != nil
end

def set_include?(elem)
  SET.include?(elem)
end

def set_member?(elem)
  SET.member?(elem)
end

puts format('Ruby v.%s', RUBY_VERSION)

{
  'First' => ARRAY.first,
  'Middle' => (ARRAY.size / 2).to_i,
  'Last' => ARRAY.last
}.each do |k, element|
  puts DIVIDER, k, DIVIDER

  compare do
    _array_include?        { array_include?(element)        }
    _array_member?         { array_member?(element)         }
    _array_index           { array_index(element)           }
    _array_find_index      { array_find_index(element)      }
    _array_index_each      { array_index_each(element)      }
    _array_find_index_each { array_find_index_each(element) }
    _array_any_each        { array_any_each(element)        }
    _array_find_each       { array_find_each(element)       }
    _array_detect_each     { array_detect_each(element)     }
  end
end

puts '', DIVIDER, 'Sets vs. Array.include?', DIVIDER
{
  'First' => ARRAY.first,
  'Middle' => (ARRAY.size / 2).to_i,
  'Last' => ARRAY.last
}.each do |k, element|
  puts DIVIDER, k, DIVIDER

  compare do
    _array_include? { array_include?(element) }
    _set_include?   { set_include?(element)   }
    _set_member?    { set_member?(element)    }
  end
end

Wenn Sie es auf meinem Mac OS-Laptop ausführen, erhalten Sie Folgendes:

Ruby v.2.7.0
--------------------
First
--------------------
Running each test 65536 times. Test will take about 5 seconds.
_array_include? is similar to _array_index
_array_index is similar to _array_find_index
_array_find_index is faster than _array_any_each by 2x ± 1.0
_array_any_each is similar to _array_index_each
_array_index_each is similar to _array_find_index_each
_array_find_index_each is faster than _array_member? by 4x ± 1.0
_array_member? is faster than _array_detect_each by 2x ± 1.0
_array_detect_each is similar to _array_find_each
--------------------
Middle
--------------------
Running each test 32 times. Test will take about 2 seconds.
_array_include? is similar to _array_find_index
_array_find_index is similar to _array_index
_array_index is faster than _array_member? by 2x ± 0.1
_array_member? is faster than _array_index_each by 2x ± 0.1
_array_index_each is similar to _array_find_index_each
_array_find_index_each is similar to _array_any_each
_array_any_each is faster than _array_detect_each by 30.000000000000004% ± 10.0%
_array_detect_each is similar to _array_find_each
--------------------
Last
--------------------
Running each test 16 times. Test will take about 2 seconds.
_array_include? is faster than _array_find_index by 10.000000000000009% ± 10.0%
_array_find_index is similar to _array_index
_array_index is faster than _array_member? by 3x ± 0.1
_array_member? is faster than _array_find_index_each by 2x ± 0.1
_array_find_index_each is similar to _array_index_each
_array_index_each is similar to _array_any_each
_array_any_each is faster than _array_detect_each by 30.000000000000004% ± 10.0%
_array_detect_each is similar to _array_find_each

--------------------
Sets vs. Array.include?
--------------------
--------------------
First
--------------------
Running each test 65536 times. Test will take about 1 second.
_array_include? is similar to _set_include?
_set_include? is similar to _set_member?
--------------------
Middle
--------------------
Running each test 65536 times. Test will take about 2 minutes.
_set_member? is similar to _set_include?
_set_include? is faster than _array_include? by 1400x ± 1000.0
--------------------
Last
--------------------
Running each test 65536 times. Test will take about 4 minutes.
_set_member? is similar to _set_include?
_set_include? is faster than _array_include? by 3000x ± 1000.0

Grundsätzlich sagen mir die Ergebnisse, dass ich für alles ein Set verwenden soll, wenn ich nach Inklusion suchen möchte, es sei denn, ich kann garantieren, dass das erste Element das gewünschte ist, was nicht sehr wahrscheinlich ist. Das Einfügen von Elementen in einen Hash ist mit einem gewissen Aufwand verbunden, aber die Suchzeiten sind so viel schneller, dass ich nicht denke, dass dies jemals in Betracht gezogen werden sollte. Wenn Sie danach suchen müssen, verwenden Sie kein Array, sondern ein Set. (Oder ein Hash.)

Je kleiner das Array ist, desto schneller werden die Array-Methoden ausgeführt, aber sie werden immer noch nicht mithalten können, obwohl in kleinen Arrays der Unterschied möglicherweise gering ist.

„First“, „Mitte“ und „Last“ spiegeln die Verwendung von first, size / 2und lastfür ARRAYfür das Sein Element gesucht. Dieses Element wird beim Suchen der Variablen ARRAYund verwendet SET.

Für die Methoden, mit denen verglichen wurde, wurden geringfügige Änderungen vorgenommen, > 0da der Test >= 0für indexTypprüfungen durchgeführt werden sollte.

Weitere Informationen zu Fruity und seiner Methodik finden Sie in der README-Datei .

den Blechmann
quelle