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?
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
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:
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:
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?...
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
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/CatDogBird/
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.
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)){caseQundef:if(rb_equal(e, item))returnQtrue;break;caseQtrue:returnQtrue;}}returnQfalse;}
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();}returnQnil;}
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;}
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 .
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...
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)){returnQtrue;}}returnQfalse;}
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?:
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:
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 .
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.
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.
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 #=> true8.in? a #=> false
a.member?1#=> true
a.member?8#=> false
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
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:
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.
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
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/[,. ]/
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.
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.
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.
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 .
hash = arr.map {|x| [x,true]}.to_h
hash.has_key? 'Dog'
Antworten:
Sie suchen
include?
:quelle
%w(Cat Dog Bird).include? 'Dog'
#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.[ 'Dog', 'Bird', 'Cat' ].has? 'Dog'
In (Teil von Rails) gibt es seit Version 3.1 eine
in?
MethodeActiveSupport
, auf die @campaterson hingewiesen hat. Also innerhalb von Rails, oder wenn Sierequire 'active_support'
, können Sie schreiben:OTOH, es gibt keinen
in
Operator 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 alleEnumerable
s einschließlichArray
,Hash
,Set
,Range
: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 (dhO(1)
). Wenn Ihr Array beispielsweise konstant ist, ist es eine gute Idee, stattdessen ein Set zu verwenden. Z.B:Ein schneller Test zeigt, dass das Aufrufen
include?
eines 10-ElementsSet
etwa 3,5-mal schneller ist als das Aufrufen des entsprechendenArray
Elements (wenn das Element nicht gefunden wird).Ein letzter abschließender Hinweis: Seien Sie vorsichtig, wenn Sie
include?
ein verwendenRange
. Es gibt Feinheiten. Lesen Sie daher das Dokument und vergleichen Sie es mitcover?
...quelle
#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%3FVersuchen
quelle
Verwendung
Enumerable#include
: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: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.
quelle
Wenn Sie durch einen Block überprüfen möchten, können Sie versuchen
any?
oderall?
.Weitere Informationen finden Sie unter Aufzählbar .
Meine Inspiration kam von " bewerten, ob Array irgendwelche Elemente in Rubin hat "
quelle
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 danninclude?
oder aufrufenmember?
.Hier sind alle:
Sie alle geben einen
true
ish-Wert zurück, wenn das Element vorhanden ist.include?
ist die bevorzugte Methode. Es wirdfor
intern eine C-Sprachschleife verwendet , die unterbrochen wird, wenn ein Element mit den internenrb_equal_opt/rb_equal
Funktionen übereinstimmt . Es kann nicht viel effizienter werden, wenn Sie kein Set für wiederholte Mitgliedschaftsprüfungen erstellen.member?
wird in derArray
Klasse nicht neu definiert und verwendet eine nicht optimierte Implementierung aus demEnumerable
Modul, die buchstäblich alle Elemente auflistet :Übersetzt in Ruby-Code bewirkt dies Folgendes:
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.
Set
ist 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:
Wie Sie sehen, erstellt die Set-Klasse nur eine interne
@hash
Instanz, ordnet alle Objekte zutrue
und ü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:
quelle
11
Ihnen aufgezählten Wege in Frage stellen. Erstens können Sieindex
undfind_index
(oderfind
unddetect
) 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,> 0
falsch, was sicher ein Versehen war. (Fortsetzung)arr.index(e)
gibt beispielsweise0
if zurückarr[0] == e
. Sie werdenarr.index(e)
Rücksendungen zurückrufen,nil
wenn diesee
nicht vorhanden sind.index
kann jedoch nicht verwendet werden, wenn nachnil
in gesucht wirdarr
. (Gleiches Problem mitrindex
, 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)arr.count(e) > 0
,arr != arr.dup.delete(e)
,arr != arr - [e]
undarr & [e] == [e]
. Man könnte auchselect
und beschäftigenreject
.Mehrere Antworten deuten darauf hin
Array#include?
, aber es gibt eine wichtige Einschränkung: Wenn Sie sich die Quelle ansehen, wird sogarArray#include?
eine Schleife ausgeführt: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-trie
in diesem Beispiel verwenden: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 wieArray#include?
mit sublinear zu durchlaufenTrie#include?
:quelle
a.each do ... end
Ähm ... nicht sicher, wie das keine Schleife istSet#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.Set
Verwendungen Hashes indizieren ihre Mitglieder, also eigentlichSet#include?
sollte Komplexität O (1) für eine gut verteilteSet
(insbesondere O (Input-Größe) für das Hashing und O (log (N / bucket-Nummer)) für die Suche)Wenn Sie keine Schleife ausführen möchten, gibt es keine Möglichkeit, dies mit Arrays zu tun. Sie sollten stattdessen ein Set verwenden.
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:
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:
Und die Ergebnisse:
quelle
include?
beim ersten Treffer auf?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.Dies ist eine andere Möglichkeit, dies zu tun: Verwenden Sie die
Array#index
Methode.Es gibt den Index des ersten Auftretens des Elements im Array zurück.
Zum Beispiel:
index()
kann auch einen Block nehmen:Zum Beispiel:
Dies gibt den Index des ersten Wortes im Array zurück, das den Buchstaben 'o' enthält.
quelle
index
iteriert immer noch über das Array, es gibt nur den Wert des Elements zurück.Lustige Tatsache,
Sie können
*
damit die Array-Mitgliedschaft incase
Ausdrücken überprüfen .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
array
es sich also nicht um ein Array, sondern um ein einzelnes Element handelt, stimmt es mit diesem Element überein.quelle
when
letztmöglichen verwenden, damit andere, schnellere Überprüfungen schnell beseitigt werden.Es gibt mehrere Möglichkeiten, dies zu erreichen. Einige davon sind wie folgt:
quelle
Object#in?
nur zu Rails (dhActiveSupport
) v3.1 + hinzugefügt wurde . Es ist in Ruby nicht verfügbar.Wenn Sie mehrmals nach einem Schlüssel suchen müssen, konvertieren Sie
arr
inhash
und checken Sie jetzt O (1) ein.Leistung von Hash # has_key? versus Array # include?
Für die einmalige Überprüfung ist die Verwendung
include?
in Ordnungquelle
Dies zeigt Ihnen nicht nur, dass es existiert, sondern auch, wie oft es erscheint:
quelle
.any?
jedoch zurückkehren, sobald das erste übereinstimmende Element gefunden wird,.count
wird immer das gesamte Array verarbeitet.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
.quelle
<=>
, was nicht immer der Fall ist. Angenommen, die Elemente des Arrays waren beispielsweise Hashes.Du kannst es versuchen:
Beispiel: Wenn Katze und Hund im Array vorhanden sind:
Anstatt:
Hinweis:
member?
undinclude?
sind gleich.Dies kann die Arbeit in einer Zeile erledigen!
quelle
Wenn wir dies nicht verwenden möchten,
include?
funktioniert dies auch:quelle
quelle
['Cat', nil, 'Dog'].detect { |x| x == nil } #=> nil
. Wurdenil
gefunden?Wie wäre es auf diese Weise?
quelle
Wenn Sie dies in einem MiniTest-Komponententest versuchen , können Sie verwenden
assert_includes
. Beispiel:quelle
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:
Dann:
quelle
/[,|.| |]#{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}(,|\.| |$)/
/[,. ]/
Wenn Sie den Wert nicht nur wahr oder falsch zurückgeben möchten, verwenden Sie
Dies gibt 'Hund' zurück, wenn es in der Liste vorhanden ist, andernfalls null.
quelle
array.any?{|x| x == 'Dog'}
wenn Sie es möchten wahr / falsch (nicht der Wert), sondern auch gegen einen Block vergleichen wollen so.Hier ist noch eine Möglichkeit, dies zu tun:
quelle
arr != arr - [e]
.arr & [e] == [e]
ist ein anderer Weg in die gleiche Richtung.quelle
quelle
in?
erfordertActiveSupport
importiert werden:require active_support
.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.quelle
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:
Wenn Sie es auf meinem Mac OS-Laptop ausführen, erhalten Sie Folgendes:
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 / 2
undlast
fürARRAY
für das Sein Element gesucht. Dieses Element wird beim Suchen der VariablenARRAY
und verwendetSET
.Für die Methoden, mit denen verglichen wurde, wurden geringfügige Änderungen vorgenommen,
> 0
da der Test>= 0
fürindex
Typprüfungen durchgeführt werden sollte.Weitere Informationen zu Fruity und seiner Methodik finden Sie in der README-Datei .
quelle