Diese Funktion verhält sich genauso wie exists mit Hashes.
Ich plane es viel zu benutzen.
Kann es in irgendeiner Weise optimiert werden?
%Vor%Sie können das intelligente Abgleich verwenden, das ab Perl 5.10 verfügbar ist:
%Vor%Dies sollte viel schneller sein als ein Funktionsaufruf.
Wenn Sie dies in einem festen Array oft tun müssen, verwenden Sie stattdessen einen Hash:
%Vor% Manche Leute greifen nach dem Smart-Match-Operator, aber das ist eine der Funktionen, die wir aus Perl entfernen müssen. Sie müssen entscheiden, ob dies übereinstimmen soll, wobei das Array eine Array-Referenz enthält, die eine Hash-Referenz mit dem Schlüssel b :
Da die intelligente Übereinstimmung rekursiv ist, geht sie weiter in Datenstrukturen. Ich schreibe über einige davon in Smart Matching neu denken .
>Da es bei StackOverflow viele ähnliche Fragen gibt, bei denen verschiedene "richtige Antworten" zu unterschiedlichen Ergebnissen führen, habe ich versucht, sie zu vergleichen. Diese Frage scheint ein guter Ort zu sein, um meine kleine Benchmark zu teilen.
Für meine Tests habe ich einen Testsatz ( @test_set ) von 1.000 Elementen (Strings) der Länge 10 verwendet, wobei nur ein Element ( $search_value ) mit einer bestimmten Zeichenfolge übereinstimmt.
Ich habe die folgenden Aussagen gemacht, um die Existenz dieses Elements in einer Schleife von 100.000 Umdrehungen zu bestätigen.
_grep
%Vor%_hash
%Vor%_hash_prapped
%Vor%$mapping , die als $mapping = { map { $_ => 1 } @test_set } vorberechnet wird (was in der endgültigen Messung enthalten ist) _ regex
%Vor%_ regex_prejoined
%Vor%$rx , der als $rx = join "|", map quotemeta, @test_set; vorberechnet wird (was in der endgültigen Messung enthalten ist) _manual_first
%Vor%_first
%Vor%List::Util (Version 1.38) _smart
%Vor%_any
%Vor%List::MoreUtils (Version 0.33) Auf meinem Rechner (Ubuntu, 3.2.0-60-generic, x86_64, Perl v5.14.2) habe ich folgende Ergebnisse erhalten. Die angezeigten Werte sind Sekunden und werden von gettimeofday und tv_interval von Time::HiRes (Version 1.9726) zurückgegeben.
Das Element $search_value befindet sich an der Position 0 im Array @test_set
Das Element $search_value befindet sich an der Position 500 im Array @test_set
Das Element $search_value befindet sich an der Position 999 im Array @test_set
Fazit
Die schnellste Methode, um das Vorhandensein eines Elements in einem Array zu überprüfen, sind vorbereitete Hashes. Sie kaufen das natürlich durch einen proportionalen Speicherverbrauch und es macht nur Sinn, wenn Sie im Set mehrmals nach Elementen suchen. Wenn Ihre Aufgabe kleine Datenmengen und nur eine oder wenige Suchvorgänge umfasst, können Hashes sogar die schlechteste Lösung sein. Nicht so schnell, aber eine ähnliche Idee wäre es, vorbereitete reguläre Ausdrücke zu verwenden, die eine kleinere Vorbereitungszeit zu haben scheinen.
In vielen Fällen ist eine vorbereitete Umgebung keine Option.
Überraschenderweise hat List::Util::first sehr gute Ergebnisse, wenn es um den Vergleich von Anweisungen geht, die keine vorbereitete Umgebung haben. Während der Suchwert am Anfang steht (was vielleicht auch als Ergebnis in kleineren Mengen interpretiert werden könnte), liegt er sehr nahe bei den Favoriten ~~ und any (und könnte sogar im Bereich der Messungenauigkeit liegen). Für Objekte in der Mitte oder am Ende meines größeren Testsets ist first definitiv die schnellste.
brian d foy schlug vor, einen Hash zu verwenden, der O (1) Lookups auf Kosten einer etwas teureren Hash-Erstellung liefert. Es gibt eine Technik, die Marc Jason Dominus in seinem Buch "Higher Order Perl" beschreibt, bei dem ein Hash verwendet wird, um Ergebnisse eines Subs für einen gegebenen Parameter zu memoisieren (oder zwischenzuspeichern). Wenn also zum Beispiel findit(1000) für den gegebenen Parameter immer dasselbe Ergebnis liefert, muss das Ergebnis nicht jedes Mal neu berechnet werden. Die Technik ist im Memoize-Modul (Teil des Perl-Kerns) implementiert.
Memo ist nicht immer ein Gewinn. Manchmal ist der Overhead des Memo-Wrappers größer als die Kosten für die Berechnung eines Ergebnisses. Manchmal ist es unwahrscheinlich, dass ein bestimmter Parameter mehr als einmal oder relativ oft überprüft wird. Und manchmal kann nicht garantiert werden, dass das Ergebnis einer Funktion für einen bestimmten Parameter immer gleich ist (dh der Cache kann veraltet sein). Aber wenn Sie eine teure Funktion mit stabilen Rückgabewerten pro Parameter haben, kann die Memotisierung ein großer Gewinn sein.
Genau wie brian d foy's Antwort einen Hash verwendet, verwendet Memoize intern einen Hash. In der Memoize-Implementierung gibt es einen zusätzlichen Overhead, aber der Vorteil von Memoize besteht darin, dass die ursprüngliche Subroutine nicht neu strukturiert werden muss. Sie haben nur use Memoize; und dann memoize( 'expensive_function' ); , vorausgesetzt, es erfüllt die Kriterien für die Nutzung der Memo-Funktion.
Ich nahm Ihre ursprüngliche Subroutine und konvertierte sie um mit Ganzzahlen zu arbeiten (nur zur Vereinfachung beim Testen). Dann fügte ich eine zweite Version hinzu, die einen Verweis auf das ursprüngliche Array übergab, anstatt das Array zu kopieren. Mit diesen beiden Versionen habe ich zwei weitere Subs erstellt, die ich aufgezeichnet habe. Ich bewertete dann die vier Subs.
Beim Benchmarking musste ich einige Entscheidungen treffen. Erstens, wie viele Iterationen getestet werden sollen. Je mehr Iterationen wir testen, desto wahrscheinlicher sind gute Cache-Treffer für die Memo-Versionen. Dann musste ich auch entscheiden, wie viele Gegenstände ich in das Probenfeld legen sollte. Je mehr Elemente vorhanden sind, desto weniger wahrscheinlich sind Cache-Treffer, aber desto signifikanter sind die Einsparungen, wenn ein Cache-Treffer auftritt. Ich entschied mich schließlich für ein zu durchsuchendes Array mit 8000 Elementen und entschied mich für die Suche in 24000 Iterationen. Das bedeutet, dass pro Memo-Aufruf im Durchschnitt zwei Cache-Treffer auftreten sollten. (Der erste Aufruf mit einem gegebenen Parameter schreibt in den Cache, während der zweite und dritte Aufruf aus dem Cache lesen, also im Durchschnitt zwei gute Treffer).
Hier ist der Testcode:
%Vor%Und hier sind die Ergebnisse:
%Vor%Wie Sie sehen können, war die Memo-Version Ihrer ursprünglichen Funktion tatsächlich langsamer. Das liegt daran, dass ein Großteil der Kosten Ihrer ursprünglichen Subroutine für das Erstellen von Kopien des Array mit 8.000 Elementen aufgewendet wurde, und zwar in Verbindung mit der Tatsache, dass die memoisierte Version zusätzlichen Aufruf- und Buchhaltungsaufwand aufweist.
Aber sobald wir eine Array-Referenz anstelle einer Kopie übergeben, entfernen wir die Kosten für die Weitergabe des gesamten Arrays. Deine Geschwindigkeit springt beträchtlich. Aber der klare Gewinner ist die optimierte Version (dh die Weitergabe der Referenz), die wir gespeichert haben (im Cache), und zwar um 1483% schneller als Ihre ursprüngliche Funktion. Bei der Memoisierung erfolgt die Suche nach O (n) nur beim ersten Mal, wenn ein bestimmter Parameter überprüft wird. Nachfolgende Suchvorgänge finden in O (1) -Zeit statt.
Nun müssten Sie (durch Benchmarking) entscheiden, ob memoization Ihnen hilft. Sicherlich passiert ein Array ref. Und wenn Memoisierung Ihnen nicht hilft, ist vielleicht Brians Hash-Methode am besten. Aber in Bezug auf die Notwendigkeit, nicht viel Code neu schreiben zu müssen, könnte die Kombination von Memo-Elementen mit der Übergabe eines Array-Ref eine hervorragende Alternative sein.
Ihre aktuelle Lösung durchläuft das Array, bevor das gesuchte Element gefunden wird. Als solches ist es ein linearer Algorithmus.
Wenn Sie das Array zuerst mit einem relationalen Operator ( > für numerische Elemente, gt für Strings) sortieren, können Sie verwenden binäre Suche , um die Elemente zu finden. Es ist ein logarithmischer Algorithmus, viel schneller als linear.
Natürlich muss man die Strafe für das Sortieren des Arrays an erster Stelle berücksichtigen, was eine ziemlich langsame Operation ist ( n log n ). Wenn sich der Inhalt des Arrays, mit dem Sie übereinstimmen, häufig ändert, müssen Sie nach jeder Änderung sortieren, und es wird sehr langsam. Wenn der Inhalt gleich bleibt, nachdem Sie sie zuerst sortiert haben, wird die binäre Suche praktisch schneller.
Sie können grep verwenden:
%Vor% Überraschenderweise ist die Geschwindigkeit nicht zu weit von List :: MoreUtils any() entfernt. Es ist schneller, wenn sich Ihr Artikel am Ende der Liste befindet, um etwa 25% und langsamer um etwa 50%, wenn sich Ihr Artikel am Anfang der Liste befindet.
Sie können es bei Bedarf auch inline einfügen, ohne es in ein Unterprogramm zu verschieben. d. h.
%Vor%